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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Shortest paths in randomly time varying networks


    Contributors:
    Cerulli, R. (author) / Festa, P. (author) / Raiconi, G. (author)


    Publication date :

    2001-01-01


    Size :

    624743 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    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