TY - JOUR

T1 - An exact algorithm for the mean-standard deviation shortest path problem

AU - Khani, Alireza

AU - Boyles, Stephen D.

PY - 2014/11/25

Y1 - 2014/11/25

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

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

KW - Mean-standard deviation

KW - Non-additive shortest path

KW - Path efficient frontier

KW - Reliability

UR - http://www.scopus.com/inward/record.url?scp=84956629417&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84956629417&partnerID=8YFLogxK

U2 - 10.1016/j.trb.2015.04.002

DO - 10.1016/j.trb.2015.04.002

M3 - Article

AN - SCOPUS:84956629417

VL - 81

SP - 252

EP - 266

JO - Transportation Research, Series B: Methodological

JF - Transportation Research, Series B: Methodological

SN - 0191-2615

ER -