Finding Reliable Shortest Paths in Road Networks Under Uncertainty

Bi Yu Chen, Hing Keung William Lam, Agachai Sumalee, Qingquan Li, Hu Shao, Zhixiang Fang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

111 Citations (Scopus)

Abstract

The aim of this study is to investigate the solution algorithm for solving the problem of determining reliable shortest paths in road networks with stochastic travel times. The availability of reliable shortest paths enables travelers, in the face of travel time uncertainty, to plan their trips with a pre-specified on-time arrival probability. In this study, the reliable shortest path between origin and destination nodes is determined using a multiple-criteria shortest path approach when link travel times follow normal distributions. The dominance conditions involved in such problems are established, thereby reducing the number of generated non-dominated paths during the search processes. Two solution algorithms, multi-criteria label-setting and A* algorithms, are proposed and their complexities analyzed. Computational results using large scale networks are presented. Numerical examples using data from a real-world advanced traveller information system is also given to illustrate the applicability of the solution algorithms in practice.
Original languageEnglish
Pages (from-to)123-148
Number of pages26
JournalNetworks and Spatial Economics
Volume13
Issue number2
DOIs
Publication statusPublished - 1 Jun 2013

Keywords

  • Advanced traveller information system
  • Pre-trip planning application
  • Reliable shortest path problem
  • Travel time reliability

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this