Shortest Paths in Stochastic Time-Dependent Networks with Link Travel Time Correlation

This paper develops a simple, robust framework for the problem of finding the route with the least expected travel time from any node to any given destination in a stochastic and time-dependent network. Spatial and temporal link travel time correlations are both considered in the proposed solution, which is based on a dynamic programming approach. In particular, the spatial correlation is represented by a Markovian property of the link states, in which each link is assumed to experience congested or uncongested conditions. The temporal correlation is manifested through the time-dependent expected link travel time given the condition of the link traversed. The framework enables the use of a route guidance system, in which at any decision node within a network, a decision can be made on the basis of current traffic information about which node to take next to achieve the shortest expected travel time to the destination. Numerical examples are presented to illustrate the computational steps involved in the framework to make route choices and to demonstrate the effectiveness of the proposed solution.

• Record URL:
  https://doi.org/10.3141/2338-07
• Summary URL:
  http://scholar.google.com/scholar_lookup?title=Shortest+Paths+in+Stochastic+Time-Dependent+Networks+with+Link+Travel+Time+Correlation&author=W.+Dong&author=H.+Vu&author=Y.+Nazarathy&author=B.+Vo&author=M.+Li&author=S.+Hoogendoorn&publication_year=2013
• Availability:
  • Find a library where document is available. Order URL: http://www.trb.org/Main/Blurbs/169517.aspx
• Authors:
  • Dong, Wei
  • Vu, Hai L
  • Nazarathy, Yoni
  • Vo, Bao Quoc
  • Li, Minyi
  • Hoogendoorn, Serge Paul
• Publication Date: 2013

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 58–66
• Monograph Title: Urban and Traffic Data Systems 2013, Volume 1
• Serial:
  • Transportation Research Record: Journal of the Transportation Research Board
  • Issue Number: 2338
  • Publisher: Transportation Research Board
  • ISSN: 0361-1981

Subject/Index Terms

• TRT Terms: Advanced driver information systems; Network links; Route choice; Shortest path algorithms; Stochastic processes; Travel time
• Subject Areas: Administration and Management; Data and Information Technology; Highways; Operations and Traffic Management; I70: Traffic and Transport;

Filing Info

• Accession Number: 01475104
• Record Type: Publication
• ISBN: 9780309263368
• Report/Paper Numbers: 13-4872
• Files: TRIS, TRB, ATRI
• Created Date: Mar 12 2013 5:02PM