Between Dec 19, 2024 and Jan 2, 2025, datasets can be submitted to DRUM but will not be processed until after the break. Staff will not be available to answer email during this period, and will not be able to provide DOIs until after Jan 2. If you are in need of a DOI during this period, consider Dryad or OpenICPSR. Submission responses to the UDC may also be delayed during this time.
 

An Algorithm for Reliable Shortest Path Problem with Travel Time Correlations

Loading...
Thumbnail Image

Persistent link to this item

Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

An Algorithm for Reliable Shortest Path Problem with Travel Time Correlations

Published Date

2019-02

Publisher

Type

Thesis or Dissertation

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 thesis 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 efficiency 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 proposed algorithm outperforms the existing one-to-one Lagrangian relaxation-based RSP algorithms and the exact Outer Approximation method in the literature.

Description

University of Minnesota M.S. thesis. February 2019. Major: Civil Engineering. Advisor: Alireza Khani. 1 computer file (PDF); vi, 54 pages.

Related to

Replaces

License

Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Other identifiers

Suggested citation

Zhang, Yufeng. (2019). An Algorithm for Reliable Shortest Path Problem with Travel Time Correlations. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/202406.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.