A tractable class of algorithms for reliable routing in stochastic networks

The goal of this article is to provide the theoretical basis for enabling tractable solutions to the “arriving on time” problem and enabling its use in real-time mobile phone applications. Optimal routing in transportation networks with highly varying traffic conditions is a challenging problem due to the stochastic nature of travel-times on links of the network. The definition of optimality criteria and the design of solution methods must account for the random nature of the travel-time on each link. Most common routing algorithms consider the expected value of link travel-time as a sufficient statistic for the problem and produce least expected travel-time paths without consideration of travel-time variability. However, in numerous practical settings the reliability of the route is also an important decision factor. In this article, we consider the following optimality criterion: maximizing the probability of arriving on time at a destination given a departure time and a time budget. We present an efficient algorithm for finding an optimal routing policy with a well bounded computational complexity, improving on an existing solution that takes an unbounded number of iterations to converge to the optimal solution. A routing policy is an adaptive algorithm that determines the optimal solution based on en route travel-times and therefore provides better reliability guarantees than an a priori solution. Novel speed-up techniques to efficiently compute the adaptive optimal strategy and methods to prune the search space of the problem are also investigated. Finally, an extension of this algorithm which allows for both time-varying traffic conditions and spatio-temporal correlations of link travel-time distributions is presented. The dramatic runtime improvements provided by the algorithm are demonstrated for practical scenarios in California.

► We consider the stochastic on time arrival problem for reliable vehicle routing. ► Finite iteration convergence obtained via existence of a minimum link travel-time. ► Stochastic dynamic program solved in a provably optimal order to minimize runtime. ► Analysis of necessary conditions for extension to dynamic travel-time distributions. ► Tractability for real-time routing illustrated in Mobile Millennium traffic system.