Reformulation and Solution Algorithms for Absolute and Percentile Robust Shortest Path Problems

To model a driver's route choice behavior under inherent traffic system stochasticity and to further provide better route guidance with travel-time reliability guarantees, this paper examines two models to evaluate the travel-time robustness: absolute robust shortest path (ARSP) and alpha-percentile robust shortest path (PRSP) problems. A Lagrangian relaxation approach and a scenario-based representation scheme are integrated to reformulate the minimax and percentile criteria under day-dependent random travel times. The complex problem structure is decomposed into several subproblems that can be efficiently solved as standard shortest path problems or univariate linear programming problems. Large-scale numerical experiments with real-world data are provided to demonstrate the efficiency of the proposed algorithms.

• Record URL:
  • https://doi.org/10.1109/TITS.2013.2250966
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/41297384
• Supplemental Notes:
  • Abstract reprinted with permission of IEEE.
• Authors:
  • Xing, Tao
  • Zhou, Xuesong
• Publication Date: 2013-6

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References; Tables;
• Pagination: pp 943-954
• Serial:
  • IEEE Transactions on Intelligent Transportation Systems
  • Volume: 14
  • Issue Number: 2
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • ISSN: 1524-9050
  • Serial URL: http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6979

Subject/Index Terms

• TRT Terms: Lagrangian functions; Linear programming; Networks; Shortest path algorithms; Travel time
• Subject Areas: Data and Information Technology; Highways; I71: Traffic Theory; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01524686
• Record Type: Publication
• Files: TLIB, TRIS
• Created Date: May 1 2014 4:36PM