# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
Figure 11: Query running times in milliseconds with different optimizations by Dijkstra ranks on Eur20. The boxes cover the range between the first and the third quartile. The band in the box indicates the median. The whiskers indicate 1.5 times the interquartile range. Running times outside this range are considered as outliers and displayed separately. Obviously, query running times scale with the distance. The fully optimized algorithm takes only fractions of milliseconds for short range queries, except for some outliers which take up to a millisecond. For long range queries, we usually achieve query times within a couple of milliseconds and the maximum query time was 39 ms. The basic query algorithm is around two orders of magnitude slower across all ranks. The impact of lazy optimization appears to depend on the rank of the query. For lower ranks, it introduces some overhead but reduces outliers compared to only the corridor optimization. This is due to the overhead of the queue operations. For long range queries, this is completely amortized by the reduction in arc relaxations. #### 3.4.2 Profile Queries

We perform experiments for profile queries and report the results in Table 4. The total running time depends on the amount of time-dependent information in the instance. From Ger06 to Ger17, the total running time increases by a factor of eight even though the network grows only little. The same can be observed between Eur17 and Eur20. The total running time is dominated by the reconstruction and contraction phases. Reconstruction of the travel time functions of the existing shortcuts takes roughly twice as long as computing the functions for the new shortcuts in the contraction phase. The corridor phase with the elimination tree interval query takes a negligible amount of time. Surprisingly, the time required to compute a final exact travel time profile is not much greater than to compute a path profile (on Ger06, the path profile is even slower than the travel time profile). The average complexity of the final travel time function varies by an order of magnitude across the different instances. This confirms that Ger06 is a relatively simple instance. Surprisingly, the average complexity on Eur17 is higher than on Eur20. We suspect that this is caused by the higher average complexity in the input graph and that many important arcs that cover many shortest paths already have a non-constant travel time function in Eur17. The number of path switches is magnitudes smaller. It ranges from 3 path switches on Ber to 24 on Eur20. The number of distinct paths during the day are roughly half of that. The arithmetic mean of these numbers is slightly skewed upwards by a few very high values. However, the median is still fairly close: For example, the median number of distinct paths is two on Ger06 and ten on Eur20. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline  & \multicolumn{6}{c}{**Running Time [ms]**} & \\ \cline{2-10}  & **I** & **II** & **III** & \multicolumn{2}{c}{**IV**} & \multicolumn{2}{c}{**Total**} & \(|f|\) & \(|X|\) & **Distinct** \\  & & & & **TTF** & **Paths** & & & **Paths** \\ \hline Ber & 0.1 & 37.8 & 13.9 & 2.8 & 0.4 & 55.6 & 30,974.9 & 2.7 & 2.3 \\ Ger06 & 0.4 & 56.5 & 23.0 & 0.7 & 0.8 & 83.6 & 9359.6 & 6.9 & 3.3 \\ Ger17 & 0.8 & 452.2 & 189.0 & 6.1 & 2.4 & 660.1 & 66,146.0 & 9.7 & 3.7 \\ Eur17 & 1.7 & 1135.8 & 732.9 & 13.0 & 7.8 & 1913.2 & 122,192.1 & 16.5 & 6.8 \\ Eur20 & 2.8 & 3166.6 & 1507.7 & 12.3 & 10.3 & 4747.5 & 107,690.7 & 24.4 & 11.6 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Running times of profile queries and characteristics of the obtained profiles. We report the total running time and the running time of each phase (Corridor, Reconstruction, Contraction, Extraction) of the query. The total running time is slightly larger than the sum of all phases as it includes some additional initialization and cleanup work. In addition, we report the number of breakpoints in the obtained travel time profile (Column \(|f|\)).