Если они отправились вовремя, они должны были уже прибыть.
Assuming they departed on schedule, they should have gotten there by now.
If they left on time, they should already have arrived.
