Reliable shortest path finding in stochastic networks with spatial correlated link travel times

Bi Yu Chen, Hing Keung William Lam, Agachai Sumalee, Zhilin Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

77 Citations (Scopus)

Abstract

This article proposes an efficient solution algorithm to aid travelers' route choice decisions in road network with travel time uncertainty, in the context of advanced traveler information systems (ATIS). In this article, the travel time of a link is assumed to be spatially correlated only to the neighboring links within a local 'impact area.' Based on this assumption, the spatially dependent reliable shortest path problem (SD-RSPP) is formulated as a multicriteria shortest path-finding problem. The dominant conditions for the SD-RSPP are established in this article. A new multicriteria A* algorithm is proposed to solve the SD-RSPP in an equivalent two-level hierarchical network. A case study using real-world data shows that link travel times are, indeed, only strongly correlated within the local impact areas; and the proposed limited spatial dependence assumption can well approximate path travel time variance when the size of the impact area is sufficiently large. Computational results demonstrate that the size of the impact area would have a significant impact on both accuracy and computational performance of the proposed solution algorithm.
Original languageEnglish
Pages (from-to)365-386
Number of pages22
JournalInternational Journal of Geographical Information Science
Volume26
Issue number2
DOIs
Publication statusPublished - 1 Feb 2012

Keywords

  • reliable shortest path problem
  • spatial correlation
  • travel time reliability
  • travel time uncertainty

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Information Systems
  • Library and Information Sciences

Cite this