Efficient solution algorithm for finding spatially dependent reliable shortest path in road networks

Bi Yu Chen, Hing Keung William Lam, Qingquan Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

25 Citations (Scopus)


Travel times are generally stochastic and spatially correlated in congested road networks. However, very few existing route guidance systems (RGS) can provide reliable guidance services to aid travellers planning their trips with taking account explicitly travel time reliability constraint. This study aims to develop such a RGS with particular consideration of travellers' concern on travel time reliability in congested road networks with uncertainty. In this study, the spatially dependent reliable shortest path problem (SD-RSPP) is formulated as a multi-criteria shortest path-finding problem in road networks with correlated link travel times. Three effective dominance conditions are established for links with different levels of travel time correlations. An efficient algorithm is proposed to solve SD-RSPP by adaptively using three established dominance conditions. The complexities of road networks in reality are also explicitly considered. To demonstrate the applicability of proposed algorithm, a comprehensive case study is carried out in Hong Kong. The results of case study show that the proposed solution algorithm is robust to take account of travellers' multiple routing criteria. Computational results demonstrate that the proposed solution algorithm can determine the reliable shortest path on real-time basis for large-scale road networks.
Original languageEnglish
Pages (from-to)1413-1431
Number of pages19
JournalJournal of Advanced Transportation
Issue number7
Publication statusPublished - 1 Nov 2016


  • reliable shortest path
  • route guidance systems
  • spatial correlation
  • travel time reliability

ASJC Scopus subject areas

  • Automotive Engineering
  • Economics and Econometrics
  • Mechanical Engineering
  • Computer Science Applications
  • Strategy and Management


Dive into the research topics of 'Efficient solution algorithm for finding spatially dependent reliable shortest path in road networks'. Together they form a unique fingerprint.

Cite this