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.
Original language | English |
---|---|
Article number | 6558783 |
Pages (from-to) | 1907-1917 |
Number of pages | 11 |
Journal | IEEE Transactions on Intelligent Transportation Systems |
Volume | 14 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Dec 2013 |
Keywords
- Least expected time path
- Shortest path problem
- Stochastic first-in-first-out (S-FIFO)
- Stochastic time-dependent (STD) network
ASJC Scopus subject areas
- Automotive Engineering
- Mechanical Engineering
- Computer Science Applications