Reformulation and solution algorithms for absolute and percentile robust shortest path problems

Tao Xing, Xuesong Zhou

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


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 α-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.

Original languageEnglish (US)
Article number6490060
Pages (from-to)943-954
Number of pages12
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number2
StatePublished - 2013
Externally publishedYes


  • Algorithms
  • route guidance
  • traffic information systems
  • traffic planning

ASJC Scopus subject areas

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications


Dive into the research topics of 'Reformulation and solution algorithms for absolute and percentile robust shortest path problems'. Together they form a unique fingerprint.

Cite this