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

Alireza Khani, Stephen D. Boyles

Research output: Contribution to journalArticlepeer-review

57 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)252-266
Number of pages15
JournalTransportation Research Part B: Methodological
StatePublished - Nov 25 2014

Bibliographical note

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

Publisher Copyright:
© 2015 Elsevier Ltd. All rights reserved.

Copyright 2017 Elsevier B.V., All rights reserved.


  • Mean-standard deviation
  • Non-additive shortest path
  • Path efficient frontier
  • Reliability


Dive into the research topics of 'An exact algorithm for the mean-standard deviation shortest path problem'. Together they form a unique fingerprint.

Cite this