Bitwise Algorithm for Fastest Paths in Time-Dependent Networks

Abstract

An algorithm operating on a new and compact representation of link exit times to solve the one-to-all fastest path problem in dynamic networks is presented. The new space-efficient representation that exploits the first-in, first-out property of link travel times in dynamic networks is developed. The algorithm is described, and its working on a simple network is presented. The algorithm directly operates on bit streams of data representing time-dependent link travel times and performs logical operations on 0 and 1 bits only. Computational results are presented for large dynamic networks. The ideas behind the development of this algorithm are extendable to the development of algorithms operating at the bit level to solve other variants of dynamic shortest path problems and other dynamic network flow problems. These developments then open new research possibilities in the development of solution algorithms for dynamic network problems.

Get full access to this article

View all access options for this article.

References

Cai

, Kloks

, and Wong

C. K.

. Time-Varying Shortest Path Problems with Constraints. Networks, Vol. 29, 1997, pp. 141–149.

Chabini

Fastest Routes in Temporal Networks Revisited. Presented at Optimization Days, Centre for Research on Transportation, Montreal, Quebec, Canada, May 1996.

Chabini

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

Chabini

Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 170–175.

Chabini

, and Dean

. Shortest Path Problems in Discrete-Time Dynamic Networks: Complexity, Algorithms, and Implementations. Internal Report. Massachusetts Institute of Technology, Cambridge, 1999.

Cooke

, and Halsey

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

Dean

Continuous-Time Dynamic Shortest Path Algorithms. Master’s thesis. Massachusetts Institute of Technology, Cambridge, 1999.

Dreyfus

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

Ganugapati

Dynamic Shortest Paths Algorithms: Parallel Implementations and Application to the Solution of Dynamic Traffic Assignment Models. Master’s thesis. Massachusetts Institute of Technology, Cambridge, 1998.

10.

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.

11.

Orda

, and Rom

. Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. Journal of the ACM, Vol. 37, No. 3, 1990, pp. 607–625.

12.

Orda

, and Rom

. Minimum Weight Paths in Time-Dependent Networks. Networks, Vol. 21, No. 3, 1991, pp. 295–320.

13.

Pallottino

, and Scutellà

M. G.

. Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects. In Equilibrium and Advanced Transportation Modelling ( Marcotte

and Nguyen

, eds.), Kluwer, New York, 1998, pp. 245–281.

14.

Ziliaskopoulos

Optimum Path Algorithms on Multidimensional Networks: Analysis, Design, Implementation and Computational Experience. Ph.D. thesis. University of Texas at Austin, 1994.

15.

Ahn

B. H.

, and Shin

J. Y.

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

16.

Ziliaskopoulos

A. K.

, and Mahmassani

H. S.

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