Optimal paths in dynamic networks with dependent random link travel times

He Huang and Song Gao

Transportation Research Part B: Methodological, 2012, vol. 46, issue 5, 579-598

Abstract: This paper addresses the problem of finding optimal paths in a network where all link travel times are stochastic and time-dependent, and correlated over time and space. A disutility function of travel time is defined to evaluate the paths, and those with the minimum expected disutility are defined as the optimal paths. Bellman’s Principle (Bellman, 1958) is shown to be invalid if the optimality or non-dominance of a path and its sub-paths is defined with respect to the complete set of departure times and joint realizations of link travel time. An exact label-correcting algorithm is designed to find optimal paths based on a new property for which Bellman’s Principle holds. The algorithm has exponential worst-case computational complexity. Computational tests are conducted on three types of networks. Although the average running time is exponential, the number of the optimal path candidates is polynomial on two networks and grows exponentially in the third one. Computational results in large networks and analytical results in a small network show that stochastic dependencies affect optimal path finding in a stochastic network, and that the impact is closely related to the levels of correlation and risk attitude.

Keywords: Optimal path; Non-dominated path; Correlation; Stochastic dependency; Risk aversion (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261512000069
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:46:y:2012:i:5:p:579-598

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

DOI: 10.1016/j.trb.2012.01.005

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 ().