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, the authors consider the following optimality criterion: maximizing the probability of arriving on time at a destination given a departure time and a time budget. The authors 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.

• Record URL:
  http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B9853-52X1TRD-F-1&_cdi=59087&_user=10&_pii=S1877042811010809&_origin=browse&_zone=rslt_list_item&_coverDate=12%2F31%2F2011&_sk=999829999&wchp=dGLzVlb-zSkWW&md5=15ad9e77d9e157cb5ba579437cadb5fd&ie=/sdarticle.pdf
• 
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/18770428
• Supplemental Notes:
  • Abstract reprinted with permission from Elsevier.
• Authors:
  • Samaranayake, S
  • Blandin, Sebastien
  • Bayen, Alexandre M
  • 0000-0002-6697-222X
• Conference:
  • 19th International Symposium on Transportation and Traffic Theory
  • Location: Berkeley CA, United States
  • Date: 2011-7-18 to 2011-7-20
• Publication Date: 2011

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; Maps;
• Pagination: pp 341-363
• Monograph Title: International Symposium on Transportation and Traffic Theory, 19th
• Serial:
  • Procedia - Social and Behavioral Sciences
  • Volume: 17
  • Publisher: Elsevier
  • ISSN: 1877-0428
  • Serial URL: http://www.sciencedirect.com/science/journal/18770428/53
• Publication flags:

  Open Access (libre)

Subject/Index Terms

• TRT Terms: Algorithms; Cellular telephones; Dynamic programming; Mobile communication systems; Real time information; Routing; Stochastic programming; Travel time
• Uncontrolled Terms: Adaptive routing; On-time arrival; Spatiotemporal analysis; Traffic conditions; Travel time reliability
• Geographic Terms: California
• Subject Areas: Data and Information Technology; Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01345382
• Record Type: Publication
• Files: TRIS
• Created Date: Jul 21 2011 10:08AM