Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time

Abstract

A solution is provided for what appears to be a 30-year-old problem dealing with the discovery of the most efficient algorithms possible to compute all-to-one shortest paths in discrete dynamic networks. This problem lies at the heart of efficient solution approaches to dynamic network models that arise in dynamic transportation systems, such as intelligent transportation systems (ITS) applications. The all-to-one dynamic shortest paths problem and the one-to-all fastest paths problems are studied. Early results are revisited and new properties are established. The complexity of these problems is established, and solution algorithms optimal for run time are developed. A new and simple solution algorithm is proposed for all-to-one, all departure time intervals, shortest paths problems. It is proved, theoretically, that the new solution algorithm has an optimal run time complexity that equals the complexity of the problem. Computer implementations and experimental evaluations of various solution algorithms support the theoretical findings and demonstrate the efficiency of the proposed solution algorithm. The findings should be of major benefit to research and development activities in the field of dynamic management, in particular real-time management, and to control of large-scale ITSs.

Get full access to this article

View all access options for this article.

References

Deo

, and Pang

C. Y.

. Shortest Path Algorithms: Taxonomy and Annotation. Networks, Vol. 14, 1984, pp. 275–323.

Chabini

A New Short Paths Algorithm for Discrete Dynamic Networks. Proc., 8th IF AC Symposium on Transport Systems, 1997, pp. 551–556.

Orda

, and Rom

. Minimum Wait Paths in Time-Dependent Networks. Networks, Vol. 21, 1991, pp. 295–319.

Cooke

K. L.

, and Halsey

. The Shortest Route Through a Network with Time-Dependent Internodal Transit Times. Journal of Mathematical Analysis Applications, Vol. 14, 1966, pp. 493–498.

Kaufman

D. E.

, and Smith

R. L.

. Fastest Paths in Time-Dependent Networks for Intelligent Vehicle-Highway Systems Application. IVHS Journal, Vol. 1, 1993, pp. 1–11.

Ziliaskopoulos

A. K.

, and Mahmassani

H. S.

. Time-Dependent Shortest Path Algorithm for Real-Time Intelligent Vehicle/Highway System. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 94–104.

Dreyfus

S. E.

An Appraisal of Some Shortest-Path Algorithms. Operations Research, Vol. 17, 1969, pp. 395–412.

Dijkstra

E. W.

A Note on Two Problems in Connection with Graphs. Numerische Mathematik, Vol. 1, 1959, pp. 269–271.

Ahn

B. H.

, and Shin

J. Y.

. Vehicle Routing with Time Windows and Time-Varying Congestion. Journal of the Operational Research Society, Vol. 42, 1991, pp. 393–400.

10.

Pape

Implementation and Efficiency of Moore-Algorithms for the Shortest Route Problem. Mathematical Programming, Vol. 7, 1974, pp. 212–222.

11.

Gallo

, and Pallotino

. Shortest Paths Algorithms. Annals of Operations Research, Vol. 13, 1988, pp. 3–79.

12.

Chabini

Fastest Paths in Dynamic Networks. Transportation Science (in press).

13.

Chabini

, and He

. An Analytical Approach to Dynamic Traffic Assignment with Applications to Intelligent Transportation Systems. Presented at Optimization Days, Montreal, May 1997.

14.

A Flow-Based Approach to Dynamic Traffic Assignment Problem: Formulations, Algorithms and Computer Implementations. M.S. thesis. Massachusetts Institute of Technology, Cambridge, 1997.