Reliable shortest path problems in stochastic time-dependent networks

Bi Yu Chen, Hing Keung William Lam, Agachai Sumalee, Qingquan Li, Mei Lam Tam

Research output: Journal article publicationJournal articleAcademic researchpeer-review

64 Citations (Scopus)

Abstract

This study investigates the time-dependent reliable shortest path problem (TD-RSPP), which is commonly encountered in congested urban road networks. Two variants of TD-RSPP are considered in this study. The first variant is to determine the earliest arrival time and associated reliable shortest path for a given departure time, referred to as the "forward" TD-RSPP. The second problem is to determine the latest departure time and associated reliable shortest path for a given preferred arrival time, referred as the "backward" TD-RSPP. It is shown in this article that TD-RSPP is not reversible. The backward TD-RSPP cannot be solved by the algorithms designed for the forward problem using the reverse search from destination to origin. In this study, two efficient solution algorithms are proposed to solve the forward and backward TD-RSPP exactly and the optimality of proposed algorithms is rigorously proved. The proposed solution algorithms have potential applications in both advanced traveler information systems and stochastic dynamic traffic assignment models.
Original languageEnglish
Pages (from-to)177-189
Number of pages13
JournalJournal of Intelligent Transportation Systems: Technology, Planning, and Operations
Volume18
Issue number2
DOIs
Publication statusPublished - 3 Apr 2014

Keywords

  • Dynamic Traffic Assignment Models

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Science Applications
  • Applied Mathematics

Cite this