# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
For our approach, we have to compute the travel time bounds and time-dependent expansions for all arcs in the augmented graph. Recall that a shortcut \(uv\) always bypasses one or many lower triangles \([u,w_{i},v]\) for different nodes \(w_{i}\), where \(w_{i}\) has lower rank than \(u\) and \(v\). For the bounds, we want to find the minimum and maximum travel time of the fastest travel time function between \(u\) and \(v\) over any \(w_{i}\). For the expansions, we need to determine for each point in time which lower triangle is the fastest. Assuming we know the final travel time functions of all \(uw_{i}\) and \(w_{i}v\), we can compute this using the LowerTriangleRelax algorithm (see Algorithm 1). This leads to the following algorithmic schema: Maintain a set of necessary travel time functions in memory starting with the functions from the input graph. Iterate over all arcs in the augmented graph in a bottom-up fashion. For each arc enumerate lower triangles. Link and merge their functions to compute the function, bounds and expansions of the current arc. Keep the current arc's travel time function in memory until it is no longer needed. We implement this schema as follows: We process all arcs \(uv\) ordered ascending by their lower ranked endpoint. Since the middle node \(w\) of a lower triangle \([u,w,v]\) has always lower rank than \(u\) and \(v\), the arcs \(uw\) and \(wv\) will have been processed already. To process an arc \(uv\) we enumerate lower triangles \([u,w,v]\). Perform LowerTriangleRelax for each triangle in both directions. Once all arcs \(uv\) have been processed where \(u\) is the lower ranked endpoint, we drop the travel time functions of all arcs \(wu\) where \(u\) is the higher ranked endpoint. Algorithm 5 depicts this in pseudo code. When enumerating triangles, we order them ascending by \(\underline{b}_{uw}+\underline{b}_{uw}\). This way, we process triangles first, which are likely faster. This gives us preliminary bounds on the travel time of \(uv\). Before linking the functions of another triangle \(f_{uw}\) and \(f_{wv}\), we check if \(\overline{b}_{uv}\leq\underline{b}_{uw}+\underline{b}_{wv}\). If so, the linked path would be dominated by the shortcut, and we can skip linking and merging completely. If not, we link \(f_{uw}\) and \(f_{uw}\) and obtain \(f_{[u,w,v]}\). We still can skip merging if one function is strictly smaller than the other, that is either \(\overline{b}_{uv}\leq\min(f_{[u,w,v]})\) or \(\max(f_{[u,w,v]})\leq\underline{b}_{uv}\). Even if the bounds overlap, one function might still dominate the other. To check for this case, we simultaneously sweep over the breakpoints of both functions, determining the value of the respectively other function by linear interpolation. Only when this check fails, we perform the merge operation. Before the time-dependent customization, we first use the basic and perfect customization algorithms from [5] to compute preliminary scalar upper and lower bounds for all arcs. With these bounds, we can skip additional linking and merging operations. Employing perfect customization, we can remove some arcs completely, when a dominating path through higher ranked nodes exists. Figure 4: Avoiding allocations when reconstructing shortcut travel time functions with two reusable buffers. ```
Input: Augmented graph \(G=(V,A)\) with travel time functions for input graph arcs, node ranking \(r\) Output: Expansion data and bounds for all arcs
1 for\(u\in V\) ordered by \(r(u)\)do
2 for\(uv\in\{uv\mid uv\in A,r(u)<r(v)\}\)do
3 for\(w\in\{w\mid uw\in A,wv\in A,r(w)<r(u)\}\)do
4 RelaxLowerTriangle\(([u,w,v],f_{uv},f_{uv},f_{uv})\)
5 RelaxLowerTriangle\(([v,w,u],f_{ou},f_{vw},f_{uu})\)
6
7 for\(uw\in\{uw\mid uw\in A,r(w)<r(u)\}\)do
8 Drop\((f_{uw})\)
9 Drop\((f_{wu})\)
```
**Algorithm 5**Customization

**Parallelization** We employ both loop based and task based parallelism. The original CCH publication [5] suggests processing arcs with their lower ranked endpoint on the same _level_ in parallel.