Shortest Path Finding Problem in Stochastic Time-Dependent Road Networks With Stochastic First-In-First-Out Property
- 15 July 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Transportation Systems
- Vol. 14 (4) , 1907-1917
Abstract
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 A* 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.Keywords
This publication has 37 references indexed in Scilit:
- Reliable Space–Time Prisms Under Travel Time UncertaintyAnnals of the American Association of Geographers, 2013
- Reformulation and Solution Algorithms for Absolute and Percentile Robust Shortest Path ProblemsIEEE Transactions on Intelligent Transportation Systems, 2013
- Time-dependent Hyperstar algorithm for robust vehicle navigationTransportation Research Part A: Policy and Practice, 2012
- Reliable shortest path finding in stochastic networks with spatial correlated link travel timesInternational Journal of Geographical Information Science, 2012
- Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approachTransportation Research Part B: Methodological, 2011
- Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approachTransportation Research Part A: Policy and Practice, 2011
- Reaching a destination earlier by starting later: RevisitedTransportation Research Part E: Logistics and Transportation Review, 2011
- Prediction Intervals to Account for Uncertainties in Travel Time PredictionIEEE Transactions on Intelligent Transportation Systems, 2011
- Reliable Pretrip Multipath Planning and Dynamic Adaptation for a Centralized Road Navigation SystemIEEE Transactions on Intelligent Transportation Systems, 2007
- Path finding under uncertaintyJournal of Advanced Transportation, 2005