In this paper, we study the time-dependent shortest paths problem for two types of time-dependent FIFO networks. First, we consider networks where the availability of links, given by a set of disjoint time intervals for each link, changes over time. Here, each interval is assigned a non-negative real value which represents the travel time on the link during the corresponding interval. The resulting shortest path problem is the time-dependent shortest path problem for availability intervals ( $\mathcal TDSP - \mathrm int $ ), which asks to compute all shortest paths to any (or all) destination node(s) d for all possible start times at a given source node s. Second, we study time-dependent networks where the cost of using a link is given by a non-decreasing piece-wise linear function of a real-valued argument. Here, each piece-wise linear function represents the travel time on the link based on the time when the link is used. The resulting shortest paths problem is the time-dependent shortest path problem for piece-wise linear functions ( $TDSP lin$ ) which asks to compute, for a given source node s and destination d, the shortest paths from s to d, for all possible starting times. We present an algorithm for the $\mathcal TDSP - mathrm $ problem that runs in time O((F d +γ)(|E|+|V|log∈|V|)) where F d is the output size (i.e., number of linear pieces needed to represent the earliest arrival time function to d) and γ is the input size (i.e., number of linear pieces needed to represent the local earliest arrival time functions for all links in the network). We then solve the $\mathcal TDSP - mathrm int $ problem in O(λ(|E|+|V|log∈|V|)) time by reducing it to an instance of the $\mathcal TDSP - \mathrm lin $ problem. Here, λ denotes the total number of availability intervals in the entire network. Both methods improve significantly on the previously known algorithms.

Additional Metadata
Keywords Algorithms, Earliest arrival time, FIFO property, Shortest paths, Time-dependent networks
Persistent URL dx.doi.org/10.1007/s00453-010-9461-6
Journal Algorithmica
Citation
Dehne, F, Omran, M.T. (Masoud T.), & Sack, J.-R. (2012). Shortest paths in time-dependent fifo networks. Algorithmica, 62(1-2), 416–435. doi:10.1007/s00453-010-9461-6