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.