An algorithm for reliable shortest path problem with travel time correlations

Yufeng Zhang, Alireza Khani

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Reliable shortest path (RSP) problem reflects the variability of travel time and is more realistic than standard shortest path problem which considers only the average travel time. This paper describes an algorithm for solving the mean-standard deviation RSP problem considering link travel time correlations. The proposed algorithm adopts the Lagrangian substitution and covariance matrix decomposition technique to deal with the difficulty resulting from non-linearity and non-additivity of the Mixed Integer Non-Linear Program (MINLP). The problem is decomposed into a standard shortest path problem and a convex optimization problem whose optimal solution is proved and the Lagrangian multipliers ranges are related to the eigenvalues of the covariance matrix to further speed up the algorithm. The complexity of the original problem is notably reduced by the proposed algorithm such that it can be scaled to large networks. In addition to the sub-gradient Lagrangian multiplier updating strategy integrated with projection, a novel one based on the deep-cut ellipsoid method is proposed as well. Numerical experiments on large-scale networks show the efficacy of the algorithm in terms of relative duality gap and computational time. Besides, there is evidence showing that, though having longer computational time, the ellipsoid updating method tends to obtain better solutions compared with the sub-gradient method. The algorithm outperforms the existing one-to-one Lagrangian relaxation-based RSP algorithms and the exact Outer Approximation method in the literature.

Original languageEnglish (US)
Pages (from-to)92-113
Number of pages22
JournalTransportation Research Part B: Methodological
Volume121
DOIs
StatePublished - Mar 1 2019

Fingerprint

Travel time
travel
multiplier
Covariance matrix
Gradient methods
Convex optimization
time
substitution
projection
Substitution reactions
Decomposition
experiment
evidence
Experiments

Keywords

  • Deep-cut ellipsoid
  • Eigen-decomposition
  • Lagrangian substitution(relaxation)
  • Reliable shortest path
  • Sub-gradient
  • Travel time correlations

Cite this

An algorithm for reliable shortest path problem with travel time correlations. / Zhang, Yufeng; Khani, Alireza.

In: Transportation Research Part B: Methodological, Vol. 121, 01.03.2019, p. 92-113.

Research output: Contribution to journalArticle

@article{b8681f188c80481dbcf4d4bd88c832c7,
title = "An algorithm for reliable shortest path problem with travel time correlations",
abstract = "Reliable shortest path (RSP) problem reflects the variability of travel time and is more realistic than standard shortest path problem which considers only the average travel time. This paper describes an algorithm for solving the mean-standard deviation RSP problem considering link travel time correlations. The proposed algorithm adopts the Lagrangian substitution and covariance matrix decomposition technique to deal with the difficulty resulting from non-linearity and non-additivity of the Mixed Integer Non-Linear Program (MINLP). The problem is decomposed into a standard shortest path problem and a convex optimization problem whose optimal solution is proved and the Lagrangian multipliers ranges are related to the eigenvalues of the covariance matrix to further speed up the algorithm. The complexity of the original problem is notably reduced by the proposed algorithm such that it can be scaled to large networks. In addition to the sub-gradient Lagrangian multiplier updating strategy integrated with projection, a novel one based on the deep-cut ellipsoid method is proposed as well. Numerical experiments on large-scale networks show the efficacy of the algorithm in terms of relative duality gap and computational time. Besides, there is evidence showing that, though having longer computational time, the ellipsoid updating method tends to obtain better solutions compared with the sub-gradient method. The algorithm outperforms the existing one-to-one Lagrangian relaxation-based RSP algorithms and the exact Outer Approximation method in the literature.",
keywords = "Deep-cut ellipsoid, Eigen-decomposition, Lagrangian substitution(relaxation), Reliable shortest path, Sub-gradient, Travel time correlations",
author = "Yufeng Zhang and Alireza Khani",
year = "2019",
month = "3",
day = "1",
doi = "10.1016/j.trb.2018.12.011",
language = "English (US)",
volume = "121",
pages = "92--113",
journal = "Transportation Research, Series B: Methodological",
issn = "0191-2615",
publisher = "Elsevier Limited",

}

TY - JOUR

T1 - An algorithm for reliable shortest path problem with travel time correlations

AU - Zhang, Yufeng

AU - Khani, Alireza

PY - 2019/3/1

Y1 - 2019/3/1

N2 - Reliable shortest path (RSP) problem reflects the variability of travel time and is more realistic than standard shortest path problem which considers only the average travel time. This paper describes an algorithm for solving the mean-standard deviation RSP problem considering link travel time correlations. The proposed algorithm adopts the Lagrangian substitution and covariance matrix decomposition technique to deal with the difficulty resulting from non-linearity and non-additivity of the Mixed Integer Non-Linear Program (MINLP). The problem is decomposed into a standard shortest path problem and a convex optimization problem whose optimal solution is proved and the Lagrangian multipliers ranges are related to the eigenvalues of the covariance matrix to further speed up the algorithm. The complexity of the original problem is notably reduced by the proposed algorithm such that it can be scaled to large networks. In addition to the sub-gradient Lagrangian multiplier updating strategy integrated with projection, a novel one based on the deep-cut ellipsoid method is proposed as well. Numerical experiments on large-scale networks show the efficacy of the algorithm in terms of relative duality gap and computational time. Besides, there is evidence showing that, though having longer computational time, the ellipsoid updating method tends to obtain better solutions compared with the sub-gradient method. The algorithm outperforms the existing one-to-one Lagrangian relaxation-based RSP algorithms and the exact Outer Approximation method in the literature.

AB - Reliable shortest path (RSP) problem reflects the variability of travel time and is more realistic than standard shortest path problem which considers only the average travel time. This paper describes an algorithm for solving the mean-standard deviation RSP problem considering link travel time correlations. The proposed algorithm adopts the Lagrangian substitution and covariance matrix decomposition technique to deal with the difficulty resulting from non-linearity and non-additivity of the Mixed Integer Non-Linear Program (MINLP). The problem is decomposed into a standard shortest path problem and a convex optimization problem whose optimal solution is proved and the Lagrangian multipliers ranges are related to the eigenvalues of the covariance matrix to further speed up the algorithm. The complexity of the original problem is notably reduced by the proposed algorithm such that it can be scaled to large networks. In addition to the sub-gradient Lagrangian multiplier updating strategy integrated with projection, a novel one based on the deep-cut ellipsoid method is proposed as well. Numerical experiments on large-scale networks show the efficacy of the algorithm in terms of relative duality gap and computational time. Besides, there is evidence showing that, though having longer computational time, the ellipsoid updating method tends to obtain better solutions compared with the sub-gradient method. The algorithm outperforms the existing one-to-one Lagrangian relaxation-based RSP algorithms and the exact Outer Approximation method in the literature.

KW - Deep-cut ellipsoid

KW - Eigen-decomposition

KW - Lagrangian substitution(relaxation)

KW - Reliable shortest path

KW - Sub-gradient

KW - Travel time correlations

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

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

U2 - 10.1016/j.trb.2018.12.011

DO - 10.1016/j.trb.2018.12.011

M3 - Article

VL - 121

SP - 92

EP - 113

JO - Transportation Research, Series B: Methodological

JF - Transportation Research, Series B: Methodological

SN - 0191-2615

ER -