HighlightsThis study explores the general multi-criteria constrained shortest path (MCCSP) problem.An exact method for finding all the Pareto optimal paths for MCCSP is proposed.A theoretical bound for MCCSP is shown for understanding the relationship between the complexity and the number of criteria.Performance analysis demonstrates that our algorithm is highly efficient and robust.

    AbstractIn this study, we propose an exact method for finding all the Pareto-optimal paths for a multi-criteria constrained shortest path problem. We show that solving the special bi-criteria problem is equivalent to generating at most | P | constrained shortest paths with successive tightened constraints, where | P | is the total number of all Pareto-optimal paths. For the general multi-criteria case, we propose a decomposition procedure and theoretically prove that this method can identify all the Pareto-optimal paths from at most ( u - 1 ) ! | P | candidate paths, where u is the number of criteria. Numerical studies demonstrate that our algorithm is highly efficient and robust.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    The multi-criteria constrained shortest path problem


    Contributors:
    Shi, Ning (author) / Zhou, Shaorui (author) / Wang, Fan (author) / Tao, Yi (author) / Liu, Liming (author)


    Publication date :

    2017-02-13


    Size :

    17 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    The Variance-Constrained Shortest Path Problem

    Sivakumar, Raj A. | Online Contents | 1994


    An improved solution algorithm for the constrained shortest path problem

    Santos, Luis / Coutinho-Rodrigues, João / Current, John R. | Elsevier | 2006



    ERCA*: A New Approach for the Resource Constrained Shortest Path Problem

    Ren, Zhongqiang / Rubinstein, Zachary B. / Smith, Stephen F. et al. | IEEE | 2023


    Multi-Constrained Shortest Path Model and Solution with Improved Ant Colony Algorithm

    Hu, Y. / Liu, Y. / Liu, W. | British Library Conference Proceedings | 2010