Shortest paths in stochastic networks with correlated link costs

被引：89

作者：

Fan, YY ^{[1
]}

Kalaba, RE

Moore, JE

机构：

[1] Univ Calif Davis, Dept Civil & Environm Engn, Davis, CA 95616 USA

[2] Univ So Calif, Dept Biomed Engn, Los Angeles, CA 90089 USA

[3] Univ So Calif, Dept Econ, Los Angeles, CA 90089 USA

[4] Univ So Calif, Dept Elect Engn Syst, Los Angeles, CA 90089 USA

[5] Univ So Calif, Daniel J Epstein Dept Ind & Syst & Engn, Los Angeles, CA 90089 USA

[6] Univ So Calif, Dept Civil & Environm Engn, Los Angeles, CA 90089 USA

[7] Univ So Calif, Sch Policy Planning & Dev, Los Angeles, CA 90089 USA

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 2005年 / 49卷 / 9-10期

关键词：

shortest path; stochastic networks; dynamic programming; adaptive feedback control; correlated link costs;

D O I：

10.1016/j.camwa.2004.07.028

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The objective is to minimize expected travel time from any origin to a specific destination in a congestible network with correlated link costs. Each link is assumed to be in one of two possible conditions. Conditional probability density functions for link travel times are assumed known for each condition. Conditions over the traversed links are taken into account for determining the optimal routing strategy for the remaining trip. This problem is treated as a multistage adaptive feedback control process. Each stage is described by the physical state (the location of the current decision point) and the information state (the service level of the previously traversed links). Proof of existence and uniqueness of the solution to the basic dynamic programming equations and a solution procedure are provided. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：1549 / 1564

页数：16

共 16 条

[1]

Bellman R., 1965, DYNAMIC PROGRAMMING, V81

[2]

Bellman R., 1958, Quarterly of Applied Mathematics, V16, P87, DOI [10.1090/qam/102435, DOI 10.1090/QAM/102435]

[3] ON THE USE OF AN INVERSE SHORTEST PATHS ALGORITHM FOR RECOVERING LINEARLY CORRELATED COSTS [J].

BURTON, D ;

TOINT, PL .

MATHEMATICAL PROGRAMMING, 1994, 63 (01) :1-22

[4]

BURTON D, 1993, THESIS FACULTES U NO

[5]

Dijkstra E.W., 1959, Numerische mathematik, V1, P269, DOI DOI 10.1007/BF01386390

[6] AN APPRAISAL OF SOME SHORTEST-PATH ALGORITHMS [J].

DREYFUS, SE .

OPERATIONS RESEARCH, 1969, 17 (03) :395-&

[7] PATH PREFERENCES AND OPTIMAL PATHS IN PROBABILISTIC NETWORKS [J].

EIGER, A ;

MIRCHANDANI, PB ;

SOROUSH, H .

TRANSPORTATION SCIENCE, 1985, 19 (01) :75-84

[8] Expected shortest paths in dynamic and stochastic traffic networks [J].

Fu, LP ;

Rilett, LR .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 1998, 32 (07) :499-516

[9] An adaptive routing algorithm for in-vehicle route guidance systems with real-time information [J].

Fu, LP .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2001, 35 (08) :749-765

[10] THE FASTEST PATH THROUGH A NETWORK WITH RANDOM TIME-DEPENDENT TRAVEL-TIMES [J].

HALL, RW .

TRANSPORTATION SCIENCE, 1986, 20 (03) :182-188

← 1 2 →