Ranking paths in stochastic time-dependent networks

In this paper we address optimal routing problems in networks where travel times are both stochastic and time-dependent. In these networks, the best route choice is not necessarily a path, but rather a time-adaptive strategy that assigns successors to nodes as a function of time. Nevertheless, in some particular cases an origin–destination path must be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NP-hard problem.