# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
Queries take almost a second on average on the newer Europe graphs. Naively evaluating shortcut travel times with Algorithm 2 is too slow. Limiting the search space to a shortest path corridor using the elimination tree interval query significantly reduces running times. The speedup is between a factor of 20 on Ger06 and 8 and Eur20. The effectiveness of this optimization corresponds inversely to the relative delay (see Table 1). Greater relative delays lead to bigger corridors and thus smaller speedups. The lazy evaluation optimization has limited impact on the running time (speedups between 1.3 and 3). However, it drastically shifts the balance between queue operations and travel time function evaluations. On the newer graphs, the number of queue pops increases by more than two orders of magnitude, while the number of travel time function evaluations decreases by up to a factor of 20. The additional queue operations introduce some overhead. However, this is mitigated by the avoided unnecessary and duplicate evaluations. Reusing the lower bounds from the corridor search for goal directed search yields an additional speedup of factor two to seven. Figure 10.— Customization behavior depending on the approximation parameters difference (varying by column) and threshold \(\delta\) (indicated by color). The xaxis in all plots indicates the progress of the customization by number of processed triangles. The y-axis is the passed time in the first row, the memory usage in the second row (measure by the total number of stored breakpoints) and the mean travel time function complexity in the third row. There are many more elements which contribute to memory consumption. However, the breakpoints for travel time functions are the biggest chunk and are the easiest to measure. A breakpoint has a size of 16 bytes in memory. Thus, \(8\times 10^{6}\) breakpoints correspond to 128 CB memory consumption for travel time functions alone. The configuration \(\delta=10,000\), \(\epsilon=0.1\) s caused an out-of-memory error and is not listed. #### 3.4.1 Local Queries

We generate another set of queries to investigate the performance of our algorithms depending on the distance of source and target. We draw 10,000 start nodes and departure times uniformly at random and perform time-dependent Dijkstra without a specific target. For every \(2^{i}\)th settled node, we store it as the target of a query of _Dijkstra rank i_. This methodology was introduced by [PERSON] and [PERSON] (2009). Figure 11 shows query running times by rank for the query algorithm with the various query optimizations enabled successively. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & & **Queue** & **Evaluated** & **Running** \\  & & **Pops** & **TTFs** & **Time [ms]** \\ \hline Ber & Basic & 167.4 & 100,820.5 & 8.8 \\  & + Corridor & 38.1 & 5224.1 & 0.6 \\  & + Lazy & 1603.6 & 1747.4 & 0.6 \\  & + A\({}^{\star}\) & 635.2 & 691.5 & 0.3 \\ \hline Ger06 & Basic & 492.3 & 818,721.3 & 46.4 \\  & + Corridor & 79.7 & 31,740.8 & 2.3 \\  & + Lazy & 3323.2 & 3838.0 & 1.7 \\  & + A\({}^{\star}\) & 831.0 & 995.1 & 0.6 \\ \hline Ger17 & Basic & 510.3 & 2,100,731.8 & 169.7 \\  & + Corridor & 143.4 & 164,372.5 & 13.7 \\  & + Lazy & 18,450.0 & 19,910.5 & 9.1 \\  & + A\({}^{\star}\) & 3,099.2 & 3495.5 & 1.7 \\ \hline Eur17 & Basic & 861.6 & 9,951,623.1 & 808.6 \\  & + Corridor & 229.3 & 806,727.8 & 62.3 \\  & + Lazy & 39,714.8 & 43,581.1 & 20.8 \\  & + A\({}^{\star}\) & 6876.5 & 7911.0 & 4.1 \\ \hline Eur20 & Basic & 871.0 & 10,527,072.7 & 813.2 \\  & + Corridor & 335.6 & 1,222,655.6 & 92.9 \\  & + Lazy & 62,677.7 & 70,145.4 & 33.7 \\  & + A\({}^{\star}\) & 7231.9 & 8844.7 & 4.7 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Query performance with different optimizations. We report the number of nodes popped from the queue, the number of evaluated travel time functions (TTFs) and the running time. All values are arithmetic means over 100,000 queries executed in bulk with source, target and departure times drawn uniformly at random.