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.
Shortest Path Finding Problem in Stochastic Time-Dependent Road Networks With Stochastic First-In-First-Out Property
IEEE Transactions on Intelligent Transportation Systems ; 14 , 4 ; 1907-1917
2013-12-01
737696 byte
Article (Journal)
Electronic Resource
English
Reliable Shortest Path Problems in Stochastic Time-Dependent Networks
Online Contents | 2014
|Reliable Shortest Path Problems in Stochastic Time-Dependent Networks
Taylor & Francis Verlag | 2014
|Time-Constrained Shortest-Path Problem in Stochastic Dynamic Networks
British Library Conference Proceedings | 2005
|