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 path-finding 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.
Arriving-on-Time Problem
Discrete Algorithm That Ensures Convergence
Transportation Research Record: Journal of the Transportation Research Board
Transportation Research Record: Journal of the Transportation Research Board ; 1964 , 1 ; 193-200
01.01.2006
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Arriving-on-Time Problem: Discrete Algorithm That Ensures Convergence
Online Contents | 2006
|Arriving-on-Time Problem: Discrete Algorithm That Ensures Convergence
Transportation Research Record | 2006
|Arriving-on-Time Problem: Discrete Algorithm That Ensures Convergence
British Library Conference Proceedings | 2006
|Online Contents | 1998
British Library Online Contents | 2007
|