Shortest path problem considering on-time arrival probability

Yu Nie*, Xing Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

194 Scopus citations

Abstract

This paper studies the problem of finding a priori shortest paths to guarantee a given likelihood of arriving on-time in a stochastic network. Such "reliable" paths help travelers better plan their trips to prepare for the risk of running late in the face of stochastic travel times. Optimal solutions to the problem can be obtained from local-reliable paths, which are a set of non-dominated paths under first-order stochastic dominance. We show that Bellman's principle of optimality can be applied to construct local-reliable paths. Acyclicity of local-reliable paths is established and used for proving finite convergence of solution procedures. The connection between the a priori path problem and the corresponding adaptive routing problem is also revealed. A label-correcting algorithm is proposed and its complexity is analyzed. A pseudo-polynomial approximation is proposed based on extreme-dominance. An extension that allows travel time distribution functions to vary over time is also discussed. We show that the time-dependent problem is decomposable with respect to arrival times and therefore can be solved as easily as its static counterpart. Numerical results are provided using typical transportation networks.

Original languageEnglish (US)
Pages (from-to)597-613
Number of pages17
JournalTransportation Research Part B: Methodological
Volume43
Issue number6
DOIs
StatePublished - Jan 1 2009

Keywords

  • A priori shortest path
  • Arriving on-time
  • Bellman's principle of optimality
  • First-order stochastic dominance
  • Label-correcting

ASJC Scopus subject areas

  • Transportation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Shortest path problem considering on-time arrival probability'. Together they form a unique fingerprint.

Cite this