Finding the k reliable shortest paths under travel time uncertainty

Bi Yu Chen, Qingquan Li, Hing Keung William Lam

Research output: Journal article publicationJournal articleAcademic researchpeer-review

56 Citations (Scopus)


The KRSP problem extends the classical K loopless shortest paths problem to the stochastic networks by explicitly considering travel time reliability. In this study, a deviation path approach is established for finding K α-reliable paths in stochastic networks. A deviation path algorithm is proposed to exactly solve the KRSP problem in large-scale networks. The A*technique is introduced to further improve the KRSP finding performance. A case study using real traffic information is performed to validate the proposed algorithm. The results indicate that the proposed algorithm can determine KRSP under various travel time reliability values within reasonable computational times. The introduced A*technique can significantly improve KRSP finding performance.
Original languageEnglish
Pages (from-to)189-203
Number of pages15
JournalTransportation Research Part B: Methodological
Publication statusPublished - 1 Dec 2016


  • K reliable shortest paths problem
  • Reliability
  • Travel time uncertainty

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'Finding the k reliable shortest paths under travel time uncertainty'. Together they form a unique fingerprint.

Cite this