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



    Shortest Paths in Stochastic Time-Dependent Networks with Link Travel Time Correlation

    Dong, Wei / Vu, Hai L. / Nazarathy, Yoni et al. | Transportation Research Record | 2013