This paper studies the reliable path problem in the form of minimizing the sum of mean and standard deviation of path travel time. For the case of independent link travel times, we show that the problem can be solved exactly by repeatedly solving a subproblem minimizing the sum of mean and variance of path travel time. The latter is an additive shortest path problem, and can be solved using a standard labeling algorithm. While these subproblems are similar in form to those obtained from Lagrangian relaxation, this formulation admits proof of finite convergence to the optimal solution. An iterative labeling algorithm is developed that solves the non-additive reliable path problem from a single origin to all destinations. Moreover, a labeling technique is employed to further reduce the computational time of the proposed algorithm by partially updating the network in each iteration. As an alternative, a bisection-type search algorithm is developed that solves the problem for the single-origin and single-destination case. Numerical tests are presented, indicating that the proposed algorithm outperform others recently proposed in the literature: Unlike Lagrangian relaxation, two of the proposed algorithms find solutions exactly, and the computation time is an order of magnitude faster than outer approximation methods.
Bibliographical noteFunding Information:
This study was partially funded by the National Science Foundation under grant No. 1157294, and by the U.S. Department of Transportation through the Data-Supported Transportation Operations and Planning (D-STOP) Tier 1 University Transportation Center.
© 2015 Elsevier Ltd. All rights reserved.
Copyright 2017 Elsevier B.V., All rights reserved.
- Mean-standard deviation
- Non-additive shortest path
- Path efficient frontier