Optimal routing policy problems in stochastic time-dependent networks

Song Gao and Ismail Chabini

Transportation Research Part B: Methodological, 2006, vol. 40, issue 2, 93-122

Abstract: We study optimal routing policy problems in stochastic time-dependent networks, where link travel times are modeled as random variables with time-dependent distributions. These are fundamental network optimization problems for a wide variety of applications, such as transportation and telecommunication systems. The routing problems studied can be viewed as counterparts of shortest path problems in deterministic networks. A routing policy is defined as a decision rule that specifies what node to take next at each decision node based on realized link travel times and the current time. We establish a framework for optimal routing policy problems in stochastic time-dependent networks, which we believe is the first in the literature. We give a comprehensive taxonomy and an in-depth discussion of variants of the problem. We then study in detail one variant that is particularly pertinent in traffic networks, where both link-wise and time-wise stochastic dependencies of link travel times are considered and online information is represented. We give an exact algorithm to this variant, analyze its complexity and point out the importance of finding good approximations to the exact solution. We then overview several approximations, and present a summary of a theoretical and computational analysis of their effectiveness against the exact algorithm.

Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(05)00039-1
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:40:y:2006:i:2:p:93-122

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().