A dynamic single-source single-destination shortest path problem on a directed graph is considered. The edge lengths are not constant, but they change as a function of time in a random way. The problem is modeled as a multi-stage decision process and solved by using a re-optimization method that solves the /spl iota/.th stage using the results of the solution of the (/spl iota/-1).th one. An algorithm, called the dynamical shortest path algorithm, is proposed for solving the global problem either finding a solution or detecting that the problem is infeasible and an upper bound on its running time is found. Numerical examples are reported in order to show the effectiveness of the method.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Shortest paths in randomly time varying networks


    Beteiligte:
    Cerulli, R. (Autor:in) / Festa, P. (Autor:in) / Raiconi, G. (Autor:in)


    Erscheinungsdatum :

    01.01.2001


    Format / Umfang :

    624743 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Shortest Paths in Randomly Time Varying Networks

    Cerulli, R. / Festa, P. / Raiconi, G. et al. | British Library Conference Proceedings | 2001


    Shortest paths in traffic-light networks

    Chen, Yen-Liang | Online Contents | 2000


    On Universal Shortest Paths

    Turner, L. / Hamacher, H.W. / Gesellschaft fur Operations Research | British Library Conference Proceedings | 2011


    Fuzzy Dissimilar Shortest Paths in Urban Traffic Networks

    He, R. / Li, Y. / Beijing jiao tong da xue; Guo jia zi ran ke xue ji jin wei yuan hui (China); Wang Kuancheng jiao yu ji jin hui | British Library Conference Proceedings | 2006