Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach

Path travel time reliability is an essential measure of the quality of service for transportation systems and an important attribute in travelers' route and departure time scheduling. This paper investigates a fundamental problem of finding the most reliable path under different spatial correlation assumptions, where the path travel time variability is represented by its standard deviation. To handle the non-linear and non-additive cost functions introduced by the quadratic forms of the standard deviation term, a Lagrangian substitution approach is adopted to estimate the lower bound of the most reliable path solution through solving a sequence of standard shortest path problems. A subgradient algorithm is used to iteratively improve the solution quality by reducing the optimality gap. To characterize the link travel time correlation structure associated with the end-to-end trip time reliability measure, this research develops a sampling-based method to dynamically construct a proxy objective function in terms of travel time observations from multiple days. The proposed algorithms are evaluated under a large-scale Bay Area, California network with real-world measurements.

• Record URL:
  http://www.sciencedirect.com/science/article/pii/S0191261511000919
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • Abstract reprinted with permission from Elsevier.
• Authors:
  • Xing, Tao
  • Zhou, Xuesong
• Publication Date: 2011-12

Language

• English

Media Info

• Media Type: Print
• Features: Figures; Tables;
• Pagination: pp 1660-1679
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 45
  • Issue Number: 10
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Departure time; Evaluation; Lagrangian functions; Mathematical models; Measurement; Networks; Quality of service; Route choice; Scheduling; Shortest path algorithms; Travel time
• Geographic Terms: San Francisco Bay Area
• Subject Areas: Highways; Planning and Forecasting; Public Transportation; I71: Traffic Theory;

Filing Info

• Accession Number: 01359497
• Record Type: Publication
• Files: TRIS
• Created Date: Dec 22 2011 2:08PM