Shortest paths in stochastic time-dependent networks with link travel time correlation

Wei Dong, Hai L. Vu, Yoni Nazarathy, Bao Quoc Vo, Minyi Li, Serge Paul Hoogendoorn

Research output: Contribution to journalArticleResearchpeer-review

Abstract

This paper develops a simple, robust framework for the problem of finding the route with the least expected travel time from any node to any given destination in a stochastic and time-dependent network. Spatial and temporal link travel time correlations are both considered in the proposed solution, which is based on a dynamic programming approach. In particular, the spatial correlation is represented by a Markovian property of the link states, in which each link is assumed to experience congested or uncongested conditions. The temporal correlation is manifested through the time-dependent expected link travel time given the condition of the link traversed. The framework enables the use of a route guidance system, in which at any decision node within a network, a decision can be made on the basis of current traffic information about which node to take next to achieve the shortest expected travel time to the destination. Numerical examples are presented to illustrate the computational steps involved in the framework to make route choices and to demonstrate the effectiveness of the proposed solution.
Original languageEnglish
Pages (from-to)58-66
Number of pages9
JournalTransportation Research Record-Series
Volume2338
DOIs
Publication statusPublished - 12 Jan 2013
Externally publishedYes

Cite this

Dong, Wei ; Vu, Hai L. ; Nazarathy, Yoni ; Vo, Bao Quoc ; Li, Minyi ; Hoogendoorn, Serge Paul. / Shortest paths in stochastic time-dependent networks with link travel time correlation. In: Transportation Research Record-Series. 2013 ; Vol. 2338. pp. 58-66.
@article{01d3ca3924a644408559baab1d39caf8,
title = "Shortest paths in stochastic time-dependent networks with link travel time correlation",
abstract = "This paper develops a simple, robust framework for the problem of finding the route with the least expected travel time from any node to any given destination in a stochastic and time-dependent network. Spatial and temporal link travel time correlations are both considered in the proposed solution, which is based on a dynamic programming approach. In particular, the spatial correlation is represented by a Markovian property of the link states, in which each link is assumed to experience congested or uncongested conditions. The temporal correlation is manifested through the time-dependent expected link travel time given the condition of the link traversed. The framework enables the use of a route guidance system, in which at any decision node within a network, a decision can be made on the basis of current traffic information about which node to take next to achieve the shortest expected travel time to the destination. Numerical examples are presented to illustrate the computational steps involved in the framework to make route choices and to demonstrate the effectiveness of the proposed solution.",
author = "Wei Dong and Vu, {Hai L.} and Yoni Nazarathy and Vo, {Bao Quoc} and Minyi Li and Hoogendoorn, {Serge Paul}",
year = "2013",
month = "1",
day = "12",
doi = "10.3141/2338-07",
language = "English",
volume = "2338",
pages = "58--66",
journal = "Transportation Research Record-Series",
issn = "0361-1981",
publisher = "SAGE Publications Ltd",

}

Shortest paths in stochastic time-dependent networks with link travel time correlation. / Dong, Wei; Vu, Hai L.; Nazarathy, Yoni; Vo, Bao Quoc; Li, Minyi; Hoogendoorn, Serge Paul.

In: Transportation Research Record-Series, Vol. 2338, 12.01.2013, p. 58-66.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Shortest paths in stochastic time-dependent networks with link travel time correlation

AU - Dong, Wei

AU - Vu, Hai L.

AU - Nazarathy, Yoni

AU - Vo, Bao Quoc

AU - Li, Minyi

AU - Hoogendoorn, Serge Paul

PY - 2013/1/12

Y1 - 2013/1/12

N2 - This paper develops a simple, robust framework for the problem of finding the route with the least expected travel time from any node to any given destination in a stochastic and time-dependent network. Spatial and temporal link travel time correlations are both considered in the proposed solution, which is based on a dynamic programming approach. In particular, the spatial correlation is represented by a Markovian property of the link states, in which each link is assumed to experience congested or uncongested conditions. The temporal correlation is manifested through the time-dependent expected link travel time given the condition of the link traversed. The framework enables the use of a route guidance system, in which at any decision node within a network, a decision can be made on the basis of current traffic information about which node to take next to achieve the shortest expected travel time to the destination. Numerical examples are presented to illustrate the computational steps involved in the framework to make route choices and to demonstrate the effectiveness of the proposed solution.

AB - This paper develops a simple, robust framework for the problem of finding the route with the least expected travel time from any node to any given destination in a stochastic and time-dependent network. Spatial and temporal link travel time correlations are both considered in the proposed solution, which is based on a dynamic programming approach. In particular, the spatial correlation is represented by a Markovian property of the link states, in which each link is assumed to experience congested or uncongested conditions. The temporal correlation is manifested through the time-dependent expected link travel time given the condition of the link traversed. The framework enables the use of a route guidance system, in which at any decision node within a network, a decision can be made on the basis of current traffic information about which node to take next to achieve the shortest expected travel time to the destination. Numerical examples are presented to illustrate the computational steps involved in the framework to make route choices and to demonstrate the effectiveness of the proposed solution.

UR - http://www.scopus.com/inward/record.url?scp=84884252568&partnerID=8YFLogxK

U2 - 10.3141/2338-07

DO - 10.3141/2338-07

M3 - Article

VL - 2338

SP - 58

EP - 66

JO - Transportation Research Record-Series

JF - Transportation Research Record-Series

SN - 0361-1981

ER -