As travel times in road networks are dynamic and uncertain, it is difficult and time-consuming to search for the least expected time path in large-scale networks. This paper addresses the problem of finding the least expected time path in stochastic time-dependent (STD) road networks. A stochastic travel speed model is proposed to represent STD link travel times. It is proved that the link travel times in STD networks satisfy the stochastic first-in-first-out (S-FIFO) property. Based on this S-FIFO property, an efficient multicriteria $\hbox{A}^{\ast}$ algorithm is proposed to exactly determine the least expected time path in STD networks. Computational results using several large-scale road networks show that the proposed algorithm has a significant computational advantage over existing solution algorithms without the S-FIFO property.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Shortest Path Finding Problem in Stochastic Time-Dependent Road Networks With Stochastic First-In-First-Out Property


    Contributors:


    Publication date :

    2013-12-01


    Size :

    737696 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English






    Reliable Shortest Path Problems in Stochastic Time-Dependent Networks

    Chen, Bi Yu / Lam, William H. K. / Sumalee, Agachai et al. | Taylor & Francis Verlag | 2014


    Time-Constrained Shortest-Path Problem in Stochastic Dynamic Networks

    National Research Council (U.S.) | British Library Conference Proceedings | 2005