Most reliable path-finding algorithm for maximizing on-time arrival probability

Bi Yu Chen, Chaoyang Shi, Junlong Zhang, Hing Keung William Lam, Qingquan Li, Shujin Xiang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

29 Citations (Scopus)


Finding the most reliable path that maximizes the probability of on-time arrival is commonly encountered by travelers facing travel time uncertainties. However, few exact solution algorithms have been proposed in the literature to efficiently determine the most reliable path in large-scale road networks. In this study, a two-stage solution algorithm is proposed to exactly solve the most reliable path problem. In the first stage, the upper and lower bounds of on-time arrival probability are estimated. Dominance conditions and the monotonic property of the most reliable path problem are then established. In the second stage, the multi-criteria label-setting approach is utilized to efficiently determine the most reliable path. To illustrate the applicability of the proposed solution algorithm, a comprehensive case study is carried out using a real road network with stochastic travel times. The results of case study show that the proposed solution algorithm has a remarkable computational advantage over the existing multi-criteria label-correcting algorithm.
Original languageEnglish
Pages (from-to)253-269
Number of pages17
JournalTransportmetrica B
Issue number3
Publication statusPublished - 3 Jul 2017


  • multi-criteria optimization
  • The most reliable path problem
  • travel time reliability

ASJC Scopus subject areas

  • Software
  • Modelling and Simulation
  • Transportation

Cite this