Brian C. Dean Associate Professor Division of Computer Science School of Computing, Clemson University Office: McAdams Hall, Room 205 Phone: 864-656-5866 Mail: Brian C. Dean, School of Computing, Box 340974, Clemson SC 29634-0974 Email: bcdean@cs.clemson.edu

Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms

We present a concise study of the time-dependent shortest path problem, its theoretical properties, and its solution algorithms. Time-dependent networks, in which the travel time along each arc is a known function of the departure time along the arc, arise in many practical applications, particularly those related to vehicular transportation. Since the general problem is at least NP-hard, we focus entirely on the case of FIFO networks, in which commodities travel through arcs in a First-In-First-Out manner. This special case is very common in practice and enables the development of rich theoretical properties and efficient solution algorithms. Our aim is to present a unified framework which encompasses a wide range of problem variants in both discrete and continuous time, which ties together past work and recent developments.

Note: Conjecture 3.1 has recently been resolved by a recent paper of L. Foschini, J. Hershberger, and S. Suri in SODA 2011.

Available in pdf and postscript.