Highlights Reliable shortest problem with link travel time correlation is studied. Covariance matrix is decomposed to alleviate the complexity of the problem. A Lagrangian relaxation solution algorithm is proposed. Subgradient and deep-cut ellipsoid methods are proposed for updating Lagrangian multipliers. Large-scale real test results show the algorithm is computationally efficient.

    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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An algorithm for reliable shortest path problem with travel time correlations


    Beteiligte:
    Zhang, Yufeng (Autor:in) / Khani, Alireza (Autor:in)


    Erscheinungsdatum :

    2018-12-28


    Format / Umfang :

    22 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Impacts of Correlations on Reliable Shortest Path Finding

    Zockaie, Ali / Nie, Yu (Marco) / Wu, Xing et al. | Transportation Research Record | 2013


    Lagrangian relaxation for the reliable shortest path problem with correlated link travel times

    Zhang, Yuli / Max Shen, Zuo-Jun / Song, Shiji | Elsevier | 2017


    Shortest Travel Path Searching System Based on Dijkstra Algorithm

    Sun, Ya-Qi / Liu, Yu / Xiao, Kuo-Hua | Tema Archiv | 2012


    Dynamic Shortest-Path Algorithm for Continuous Arc Travel Times

    Hu, Jian / Chan, Yupo | Transportation Research Record | 2008