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. The shortest paths problem in networks has been the subject of extensive research for many years (1). The analysis of transportation networks is one of the many application areas in which the computation of shortest paths is one of the most fundamental problems. The majority of published research on shortest paths algorithms, however, dealt with static networks that have fixed topology and fixed link costs. Interest in the concept of dynamic management of transportation systems has been increasing. New advances have brought renewed interest in the study of shortest paths problems with a new twist: Link costs generally depend on the entry time of a link. This results in a new family of shortest paths problems known as dynamic, or time-dependent, shortest paths problems. Chabini (2) distinguishes various types of dynamic shortest path problems depending on the following: (a) fastest versus minimum cost (or shortest) path problems; (b) discrete versus continuous representation of time; (c) first-in-first-out (FIFO) networks versus non-FIFO networks, in which one can depart later at the beginning of one or more arcs and arrive earlier at their end; (d) waiting is allowed versus waiting is not allowed at nodes; (e) types of shortest path questions asked: one-to-all for a given departure time or all departure times, and all-to-one for all departure times; and ( f ) integer versus real valued link travel times and link travel costs. In fastest path problems, the cost of a link is the travel time of that link. In minimum cost paths problems, link costs can be of general form. Although the fastest paths problem is a particular case of the minimum cost paths problem, the distinction between the two is particularly important for the design of efficient solution algorithms. Time-dependent marginal travel times encountered in system optimum dynamic traffic assignment models are an example of general form costs. Depending on how time is treated, dynamic shortest paths problems can be subdivided into two types: discrete and continuous. In discrete dynamic networks, time is modeled as a set of integers. Orda and Rom (3) establish various properties for continuous dynamic networks where time is treated as real numbers. The results for the oneto-all fastest paths problem studied here are valid for both discrete and continuous representations of time. It is important to note that a discrete dynamic network can be viewed alternatively as a static network obtained by using a timespace expansion representation. The size of the equivalent representation depends on the waiting policy at nodes. As may be expected, it is not the best approach to explicitly use the time-space expansion representation to compute dynamic shortest paths. The time-space expansion network has, however, some particular properties that can be exploited in the design of efficient shortest paths algorithms. The challenge is to discover particular properties of these networks and appropriately exploit them in designing better algorithms. Compared with that for static shortest paths problems, the literature on dynamic versions is very limited. The main known result is the condition under which static shortest path algorithms can be used, at no extra cost, to solve the one-to-all fastest paths problem in dynamic networks: Arc travel times must satisfy the FIFO condition. Hidden behind this result are various limitations: 1. This result applies to the fastest paths problem only and not to the minimum cost paths problem. 2. This result is limited to forward-search labeling algorithms only. Transportation applications need the computation of fastest paths from all nodes to a set of destinations. Hence, static methods typically would first compute fastest paths from all nodes to all nodes and then extract needed solutions. Because the number of destinations in a transportation network usually is a small fraction of total number of nodes, a static approach may not lead to the best solution algorithm possible. 3. Transportation applications do not necessarily satisfy the FIFO condition. 4. A static algorithm computes shortest paths for one departure time interval only, but shortest paths for all possible departure time intervals are generally sought. Traffic management centers in intelligent transportation systems (ITS) must operate in real time. The time taken to collect data, process them, and broadcast the resulting information may consti-
REF proposed to calculate the shortest path from any point to an end point by time discretization under the first in first out (FIFO) condition.
Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time
234 I. Chabini. Minimum expected travel times in stochastic time-dependent networks revisited. Internal Report. MIT
Computer Science