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

Alireza Khani, Stephen D. Boyles

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

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
Volume81
DOIs
StatePublished - Nov 25 2014

Keywords

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

Fingerprint 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