AbstractThis paper deals with algorithms for finding the constrained K-shortest paths (CKSP) and their application to the path enumeration problem. An attractive property of using Constrained Shortest Paths for path enumeration is that paths can be selected based on objective criteria. The conventional way of finding these paths is to compute a sufficiently large number of overall shortest paths, and deleting the ones that do not satisfy the constraints. However for realistically sized networks, combined with restrictive constraints this method becomes unfeasible because of CPU time restrictions. A new method is proposed that finds the feasible shortest paths directly and can be applied in combination with a wide class of constraints. The paper explains how this CKSP algorithm can be implemented using the ordinary shortest path computation as its elementary operation. An example is provided in which the method is used to enumerate paths while avoiding strongly overlapping and overly circuitous paths. In this context the computational performance of the CKSP method is compared with that of the conventional method. On a network consisting of 200 nodes a speed-up factor exceeding 62 has been demonstrated on a problem that involves finding the 200 constrained shortest paths. The speed-up factor increases sharply with the size of the network and the level of restriction of the constraints. As opposed to the conventional method, the proposed implementation of the CKSP method displays only a limited sensitivity to the level of restriction of the constraints. While the conventional method could only deal with small networks, the proposed method can also enumerate paths for more realistically sized networks.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Path enumeration by finding the constrained K-shortest paths


    Beteiligte:

    Erschienen in:

    Erscheinungsdatum :

    2004-07-21


    Format / Umfang :

    19 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Path enumeration by finding the constrained K-shortest paths

    van der Zijpp, N.J. | Online Contents | 2005


    Finding k Simple Shortest Paths and Cycles

    Agarwal, Udit / Ramachandran, Vijaya | BASE | 2016

    Freier Zugriff

    Finding Reliable Shortest Paths in Dynamic Stochastic Networks

    Wu, Xing | Transportation Research Record | 2013



    The Variance-Constrained Shortest Path Problem

    Sivakumar, Raj A. | Online Contents | 1994