Optimal paths in dynamic networks with dependent random link travel times

被引:88
作者
Huang, He [2 ]
Gao, Song [1 ]
机构
[1] Univ Massachusetts Amherst, Dept Civil & Environm Engn, Amherst, MA 01003 USA
[2] Future Urban Mobil, Singapore MIT Alliance Res & Technol, Singapore 117543, Singapore
关键词
Optimal path; Non-dominated path; Correlation; Stochastic dependency; Risk aversion; SHORTEST PATHS; ROUTE;
D O I
10.1016/j.trb.2012.01.005
中图分类号
F [经济];
学科分类号
02 ;
摘要
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. (C) 2012 Elsevier Ltd. All rights reserved.
引用
收藏
页码:579 / 598
页数:20
相关论文
共 35 条
[11]   PATH PREFERENCES AND OPTIMAL PATHS IN PROBABILISTIC NETWORKS [J].
EIGER, A ;
MIRCHANDANI, PB ;
SOROUSH, H .
TRANSPORTATION SCIENCE, 1985, 19 (01) :75-84
[12]   Shortest paths in stochastic networks with correlated link costs [J].
Fan, YY ;
Kalaba, RE ;
Moore, JE .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2005, 49 (9-10) :1549-1564
[13]   SHORTEST PATHS IN PROBABILISTIC GRAPHS [J].
FRANK, H .
OPERATIONS RESEARCH, 1969, 17 (04) :583-&
[14]   Optimal routing policy problems in stochastic time-dependent networks [J].
Gao, S ;
Chabini, I .
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2006, 40 (02) :93-122
[15]  
Gao S, 2002, TRANSPORT RES REC, P188
[16]  
Gao S, 2005, THESIS MIT CAMBRIDGE
[17]   Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks [J].
Gao, Song ;
Huang, He .
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2012, 21 (01) :196-213
[18]  
HADAR J, 1969, AM ECON REV, V59, P25
[19]   THE FASTEST PATH THROUGH A NETWORK WITH RANDOM TIME-DEPENDENT TRAVEL-TIMES [J].
HALL, RW .
TRANSPORTATION SCIENCE, 1986, 20 (03) :182-188
[20]   OPTIMAL PATHS IN GRAPHS WITH STOCHASTIC OR MULTIDIMENSIONAL WEIGHTS [J].
LOUI, RP .
COMMUNICATIONS OF THE ACM, 1983, 26 (09) :670-676