# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
Algorithm 6 depicts a routine to compute path switches and the associated shortest paths. The algorithm follows the same schema as all unpacking algorithms. The operation is recursively applied to all expansions limited to the validity time of the expansion. Only the Combine operation is more involved. It performs a coordinated linear sweep over the path sets from \(uw_{x}\) and \(w_{x}v\) and appends the paths where the validity intervals overlap. For the paths from \(w_{x}\) to \(v\), we only know the validity times with respect to departure at \(w_{x}\). To obtain the corresponding departure time at \(u\), we reverse evaluate the current \(uw_{x}\) path, i.e., we successively evaluate the inverted arrival time function of all arcs on the path in reverse order. ```
Input: Expansions \(X_{uv}\) for edge \(uv\), Time interval \(T\) Output: Set \(P\) of unpacked paths \(p\) with associated validity times \(\Pi_{p}\)
1\(P\leftarrow\emptyset\)for\(x\in X_{uv}\)do
2\([\tau_{x},\pi_{x}]\gets T\cap\Pi_{x}\)if\(E(x_{t})=uv\in A\)then
3\(P\gets P\cup([u,v]_{x}[\tau_{x},\pi_{x}])\)
4 else
5\(w_{x}\gets E(x_{t})\)
6\(P_{uw_{x}}\leftarrow\textsc{UnpackPaths}(uw_{x_{x}}[\tau_{x},\pi_{x}])\)\(P_{w_{x}v}\leftarrow\textsc{UnpackPaths}(w_{x}v,[\tau_{x}+f_{uw_{x}}(\tau_{x}),\pi_{x}+f_{uw_{x}}( \pi_{x})])\)\(P_{x}\leftarrow\textsc{Combine}(P_{w_{x}v},P_{uw_{x}})\)
7\(P\gets P\cup P_{x}\)
8
9 return\(P\)
```

**Algorithm 6**UnpackPaths

Figure 8: Example of profile query search space with inserted shortcuts. Gray nodes and arcs are not in the shortest path corridor. Dashed arcs are new shortcuts. ## 3 Results

In this section, we present our experimental results. We first discuss the experimental setup and the input road networks. Then, we discuss the performance of each of our presented algorithms in turn. Finally, we compare our approach to related work. ### Experimental Setup

Our benchmark machine runs openSUSE Leap 15.2 (kernel 5.3.18) and has 192 GB of DDR4-2666 RAM and two Intel Xeon Gold 6144 CPUs, each of which has eight cores clocked at 3.5 GHz and 8 \(\times\) 64 KB of L1, 8 \(\times\) 1 MB of L2 and 24.75 MB of shared L3 cache. Hyperthreading was disabled and parallel experiments use 16 threads. We implemented our algorithms in Rust (the code for this paper and all experiments is available at [[https://github.com/kit-algo/catchup](https://github.com/kit-algo/catchup)]([https://github.com/kit-algo/catchup](https://github.com/kit-algo/catchup)) (accessed on 15 March 2021)) and compiled them with ruste 1.49.0-nightly (cf9 cf7e92 2020-11-10) in the release profile with the target-cpu = native option (we disabled AVX512 instructions, as they caused misoptimizations). To compile competing implementations written in C++, we use GCC 9.3.1 using optimization level 3. We investigated the performance of our preprocessing and query algorithms and compare dit to competing algorithms. Our experiments were focused on but not limited to space consumption and running times. We performed preprocessing five times for each input network and report arithmetic means of the running times. Unless reported otherwise, preprocessing utilized all 16 cores. For queries, we generated 100,000 source, target, departure time triples chosen uniformly at random for each graph. These were executed in bulk. Competing algorithms were evaluated with the same query set. For profile queries, we only used 1000 queries (and discarded the departure time). We report arithmetic means of query running times and machine independent measures such as number of nodes popped from the queue and number of evaluated travel time functions. ### Input Road Networks

In this section, we report results for five road networks: an instance of Berlin and the surrounding area, an old instance of Germany from 2006 which is used in many related works, two production-grade instances for Germany and Europe and with traffic predictions from 2017 and a recent production-grade instance of Europe. All instances include traffic predictions as piecewise linear functions.