We study the problem of finding shortest paths in time-dependent networks with edge load forecasts where the behavior of each edge is modeled as a time-dependent arrival function with FIFO property. Here, we present a new algorithm that computes for a given start node s and destination node d, the shortest paths and earliest arrival times for all possible starting times. Our algorithm runs in time O((F d + λ)(|E| + |V| log |V|)) where F d is the output size (number of linear pieces needed to represent the earliest arrival time function) and λ is the input size (number of linear pieces needed to represent the local earliest arrival time functions for all edges in the network). Our method improves significantly on the best previously known algorithm which requires time O(F max |V||E|) where F max ≥ F d is the maximum number of linear pieces needed to represent the earliest arrival time function between the start node s to any node in the network. It has been conjectured that there are cases where F max is of super-polynomial size; however, even in such cases, F d might still be of linear size. In such cases, our algorithm would take polynomial time to find the solution, while other methods require super-polynomial time. Both of the above methods are not useful in practice for graphs where F d is of super-polynomial size. For such graphs, we present the first approximation method to compute for all possible starting times at s, the earliest arrival times at d within error at most ε. Our algorithm runs in time O(Δ/ε(|E| + |V|log|V|)) where Δ is the difference between the earliest arrival times at d for the latest and earliest starting times at s. Copyright 2009 ACM.

Additional Metadata
Persistent URL dx.doi.org/10.1145/1645373.1645374
Conference 2nd International Workshop on Computational Transportation Science, in Conjunction with ACM SIGSPATIAL GIS 2009, IWCTS 2009
Citation
Dehne, F, Omran, M.T. (Masoud T.), & Sack, J.-R. (2009). Shortest paths in time-dependent FIFO networks using edge load forecasts. Presented at the 2nd International Workshop on Computational Transportation Science, in Conjunction with ACM SIGSPATIAL GIS 2009, IWCTS 2009. doi:10.1145/1645373.1645374