  Due to recurrent (e.g. daily or weekly) patterns and non-recurrent
disruptions (e.g. caused by incidents), travel times in road networks are
time-dependent and inherently random. This is challenging for travelers
planning a future trip, aiming to ensure on-time arrival at the destination,
while also trying to limit the total travel-time budget spent. The focus of
this paper lies on determining their optimal departure time: the latest time of
departure for which a chosen on-time arrival probability can be guaranteed. To
model the uncertainties in the network, a Markovian background process is used,
tracking events affecting the driveable vehicle speeds on the links, thus
enabling us to incorporate both recurrent and non-recurrent effects. It allows
the evaluation of the travel-time distribution, given the state of this process
at departure, on each single link. Then, a computationally efficient algorithm
is devised that uses these individual link travel-time distributions to obtain
the optimal departure time for a given path or origin-destination pair. Since
the conditions in the road network, and thus the state of the background
process, may change between the time of request and the advised time of
departure, we consider an online version of this procedure as well, in which
the traveler receives departure time updates while still at the origin.
Finally, numerical experiments are conducted to exemplify a selection of
properties of the optimal departure time and, moreover, quantify the
performance of the presented algorithms in an existing road network -- the
Dutch highway network.
