Finding the k reliable shortest paths under travel time uncertainty

This paper investigates the problem of finding the K reliable shortest paths (KRSP) in stochastic networks under travel time uncertainty. The KRSP problem extends the classical K loopless shortest paths problem to the stochastic networks by explicitly considering travel time reliability. In this study, a deviation path approach is established for finding K a-reliable paths in stochastic networks. A deviation path algorithm is proposed to exactly solve the KRSP problem in large-scale networks. The A* technique is introduced to further improve the KRSP finding performance. A case study using real traffic information is performed to validate the proposed algorithm. The results indicate that the proposed algorithm can determine KRSP under various travel time reliability values within reasonable computational times. The introduced A* technique can significantly improve KRSP finding performance.

• Record URL:
  • https://doi.org/10.1016/j.trb.2016.09.013
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0191261516302521
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • Abstract reprinted with permission of Elsevier.
• Authors:
  • Chen, Bi Yu
  • Li, Qingquan
  • Lam, William H K
• Publication Date: 2016-12

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: pp 189-203
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 94
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Shortest path algorithms; Stochastic processes; Travel time; Uncertainty
• Subject Areas: Highways; Planning and Forecasting;

Filing Info

• Accession Number: 01619173
• Record Type: Publication
• Files: TRIS
• Created Date: Dec 21 2016 11:29AM