Arriving-on-time problem: Discrete algorithm that ensures convergence

Yu Nie*, Yueyue Fan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

60 Scopus citations


Finding optimal paths in stochastic networks is an important topic in many scientific and engineering fields. To cope with uncertainty, various performance measures, including expected travel time, reliability, value at risk, and expectation with chance constraint, have been introduced. The literature has shown that adaptive strategies that incorporate both anticipation and real-time information are more efficient than a preplanned strategy in a stochastic environment. Most adaptive optimal-path algorithms focus on least-expected travel time. Recently, an adaptive pathfinding strategy, named the stochastic on-time arrival (SOTA) algorithm, was proposed to maximize the travel time reliability for any given time threshold. However, the originally proposed SOTA algorithm is based on the classic successive approximation. Whether this algorithm converges within a finite number of successive approximation steps is an open question. In this study, the proposed discrete SOTA algorithm runs in an optimal polynomial time and thus improves the computational efficiency significantly. Numerical examples are provided, and future extensions are proposed.

Original languageEnglish (US)
Title of host publicationNetwork Modeling 2006
PublisherNational Research Council
Number of pages8
ISBN (Print)0309099730, 9780309099738
StatePublished - 2006

Publication series

NameTransportation Research Record
ISSN (Print)0361-1981

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering


Dive into the research topics of 'Arriving-on-time problem: Discrete algorithm that ensures convergence'. Together they form a unique fingerprint.

Cite this