Abstract Despite measures to reduce congestion, occurrences of both recurrent and non-recurrent congestion cause large delays in road networks with important economic implications. Educated use of Intelligent Transportation Systems (ITS) can significantly reduce travel times. We focus on a dynamic stochastic shortest path problem: our objective is to minimize the expected travel time of a vehicle, assuming the vehicle may adapt the chosen route while driving. We introduce a new stochastic process that incorporates ITS information to model the uncertainties affecting congestion in road networks. A Markov-modulated background process tracks traffic events that affect the speed of travelers. The resulting continuous-time routing model allows for correlation between velocities on the arcs and incorporates both recurrent and non-recurrent congestion. Obtaining the optimal routing policy in the resulting semi-Markov decision process using dynamic programming is computationally intractable for realistic network sizes. To overcome this, we present the  edsger algorithm, a Dijkstra-like shortest path algorithm that can be used dynamically with real-time response. We develop additional speed-up techniques that reduce the size of the network model. We quantify the performance of the algorithms by providing numerical examples that use road network detector data for The Netherlands.

    Highlights A continuous-time Markov process to model the random dynamics of vehicle velocities. Model accounts for correlation and congestion by recurrent and non-recurrent events. Infeasibility of DP-based algorithms to find expectation–minimization routing policy. Dijkstra-like routing algorithm that updates route advice every intersection. Extensive experiments show algorithm is near-optimal and offers real-time response.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A framework for efficient dynamic routing under stochastically varying conditions


    Beteiligte:


    Erscheinungsdatum :

    2022-04-01


    Format / Umfang :

    28 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch