Shortest path finding problem in stochastic time-dependent road networks with stochastic first-in-first-out property

Bi Yu Chen, Hing Keung William Lam, Qingquan Li, Agachai Sumalee, Ke Yan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

43 Citations (Scopus)


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 languageEnglish
Article number6558783
Pages (from-to)1907-1917
Number of pages11
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number4
Publication statusPublished - 1 Dec 2013


  • 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

Cite this