# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Preliminaries  
We model road networks as directed graphs \(G=(V,A)\). A node \(v\in V\) represents an intersection and an arc \(a=uv\in A\) with \(u,v\in V\) represents a road segment. Every  
Figure 2: Shortcuts and their travel time functions. (**a**) A shortcut arc (dashed, black) bypassing several nodes. In our implementation, shortcuts always skip over exactly one node and two arcs, which may in turn be shortcut arcs (dashed gray arcs). (**b**) Travel time functions for two different paths between the same start and end node. arc \(a\) has a _travel time function_\(f_{a}:\mathbb{R}\to\mathbb{R}^{>0}\) mapping departure time to travel time. These functions are also referred to as _travel time profiles_. We assume that travel time functions fulfill the _First-In-First-Out_ (FIFO) property, that is, for any \(\sigma,\tau\in\mathbb{R}\) with \(\sigma\leq\tau\), \(\sigma+f(\sigma)\leq\tau+f(\tau)\) has to hold. Informally, this means that it is not possible to arrive earlier by starting later. If there are arcs that do not fulfill the FIFO property, the shortest path problem becomes \(\mathcal{NP}\)-hard [22] if waiting is not allowed. In our implementation, travel time functions are periodic piecewise linear functions represented by a sequence of _breakpoints_. We denote the number of breakpoints in a function \(f\) by its _complexity_\(|f|\). A path is a sequence of nodes \([v_{1},\ldots,v_{k}]\) such that \(v_{i}v_{i+1}\in A\). We denote the concatenation of two paths by \([v_{1},\ldots,v_{k}]\cdot[v_{k},\ldots,v_{l}]=[v_{1},\ldots,v_{k},\ldots v_{l}]\). The travel time to traverse a path \([v_{1},\ldots,v_{k}]\) can be evaluated by successively evaluating each link's travel time: \(\textsc{Eval}([v_{1},\ldots,v_{k}],\tau)=f_{v_{1}v_{2}}(\tau)+\textsc{Eval}([ v_{2},\ldots,v_{k}],\tau+f_{v_{1}v_{2}}(\tau))\). Given two travel time functions \(f\) and \(g\) for arcs \(uv\) and \(vw\), we are often interested in the travel time function of traversing first \(uv\) and then \(vw\), that is \(f(\tau)+g(f(\tau)+\tau)\). Computing this function is called _linking_. In a slight abuse of notation, we write \(g\circ f\) for this linked function. When combining two travel time functions \(f\) and \(g\) for different paths \([u,\ldots,v]\) with the same start and end, we often want to know the travel time of the best path between \(u\) and \(v\), that is \(\min(f,g)\). Computing this function is called _merging_. Both linking and merging can be implemented with coordinated linear sweeps over the breakpoints of both functions. Given a departure time \(\tau\) and nodes \(s\) and \(t\), an _earliest-arrival query_ asks for earliest point in time one can arrive at \(t\) when starting from \(s\) at \(\tau\). Such a query can be handled by [PERSON]'s algorithm [1] with minor modifications [23]. The algorithm keeps track of the earliest known arrival time \(\mathrm{ea}_{v}\) at each node \(v\). These labels are initialized with \(\tau\) for \(s\) and \(\infty\) for all other nodes. A priority queue is initialized with \((s,\tau)\). In each step, the node \(u\) with minimal earliest arrival \(\mathrm{ea}_{u}\) is popped from the queue and outgoing arcs are _relaxed_. To relax an arc \(uv\), the algorithm checks if \(\mathrm{ea}_{u}+f_{uv}(\mathrm{ea}_{u})\) improves \(\mathrm{ea}_{v}\) and updates label and queue position of \(v\) accordingly. When nodes are popped from the queue, their earliest arrival is final. This property is denoted as _label-setting_. Once \(t\) is extracted from the queue, the earliest arrival at \(t\) is known. To retrieve the shortest path, one can use _parent pointers_ which store the previous node on the shortest path from \(s\) for each node. We refer to this algorithm as _TD-Dijkstra_. A _profile query_ asks for the shortest travel time function between two nodes \(s\) and \(t\) for a time interval \(T\). This query type can also be solved by a variant of [PERSON]'s algorithm.