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.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Arriving-on-Time Problem


    Subtitle :

    Discrete Algorithm That Ensures Convergence


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:
    Nie, Yu (author) / Fan, Yueyue (author)


    Publication date :

    2006-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Arriving-on-Time Problem: Discrete Algorithm That Ensures Convergence

    Nie, Yu / Fan, Yueyue | Transportation Research Record | 2006


    Arriving-on-Time Problem: Discrete Algorithm That Ensures Convergence

    Nie, Y. / Fan, Y. / National Research Council (U.S.) | British Library Conference Proceedings | 2006


    Small jets arriving

    Online Contents | 1998


    SMS, Arriving for Keeps

    Huntzinger, D. | British Library Online Contents | 2007