The Relative Performance of Time-Dependent Shortest Paths Algorithms: A Network Expansion Perspective

This paper studies three types of algorithms for computing all-to-one time-dependent shortest paths for all departure times on a discrete time dynamic network: the CLASSIC algorithms (direct extensions of static shortest path algorithms), the decreasing order of time (DOT) algorithm and the STEN algorithm based on an explicit network expansion. All algorithms are analyzed under the same type of compact space-time expansion networks, and implemented in a flexible and extendable framework using object-oriented programming (OOP) concepts. Two types of randomly generated networks similar to those found in real transportation systems are used for evaluating the relative performance of the studied algorithms. Our numerical results show a discrepancy between DOT's theoretical and practical computational efficiency, and STEN's computational tractability in applications involving large-size networks and demanding strict acyclicity.