Publication Detail

Shortest Paths in Stochastic Networks with Correlated Link Costs



Suggested Citation:
Fan, Yueyue, Robert E. Kalaba, James E. Moore, II (2005) Shortest Paths in Stochastic Networks with Correlated Link Costs. Computers & Mathematics with Applications 49 (10), 1549 - 1564

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.