Shortest Paths in Time‐Dependent FIFO Networks

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 ( ${\mathrm{𝒯𝒟𝒮𝒫}}_{\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 ( ${\mathrm{𝒯𝒟𝒮𝒫}}_{\mathrm{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 ${\mathrm{𝒯𝒟𝒮𝒫}}_{\mathrm{lin}}$ 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 ${\mathrm{𝒯𝒟𝒮𝒫}}_{\mathrm{int}}$ problem in O(λ(|E|+|V|log|V|)) time by reducing it to an instance of the ${\mathrm{𝒯𝒟𝒮𝒫}}_{\mathrm{lin}}$ problem. Here, λ denotes the total number of availability intervals in the entire network. Both methods improve significantly on the previously known algorithms.