# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
On the other hand, with all optimizations, SynEur with high traffic has the slowest query times among all instances. Again, the reason is the combination of few time-dependent arcs with high relative delays. Because there is little time-dependent information in the instance, the basic query algorithm is not as slow as one could expect. However, because of the high delays, the corridor search and the A* optimizations are not as effective. In [12], it is stated that unimportant arcs (with respect to a Highway Hierarchy) will never get a non-constant travel time function. In combination with the high relative delays, detours through unimportant parts of the network can often become the shortest paths. This also decreases the effectiveness of our A* optimization. Table 14 contains profile query results for all instances. Once again, the results mostly conform to the already reported observations and SynEur deviates. In this case, the results are particularly surprising. While the travel time profiles are comparatively simple because of the low complexity of the input functions, the number of path switches is so high that we initially suspected bugs as the cause. In addition, it decreases as the amount of traffic increases. Nevertheless, we claim that the numbers are correct and that the reason lies in the combination of high relative delays with few time-dependent arcs. When there are only few time-dependent arcs and the slowdown due to a predicted traffic jam on an arc is very high, there will always be a faster detour using less important arcs without travel time predictions. This leads to the extremely high number of switches and distinct paths. As the amount of time-dependent arcs is increased, the spatial consistency increases and an increasing amount of detours will now also have an increased travel time. Thus, the number of path switches decreases. \begin{table}
\begin{tabular}{c c c c c c c c} \hline  & & **Nodes** & **Arcs** & **TD arcs** & **Avg. \(|f|\)** & **Rel. Delay** & **Rel. Delay** & **Size** \\  & & **[-103]** & **[-103]** & **[\%]** & **per TD arc** & **[\%]** & **TD [\%]** & **[GB]** \\ \hline Ber & Monday & 443.2 & 988.5 & 27.4 & 74.6 & 3.1 & 17.7 & 0.2 \\  & Tuesday & 443.2 & 988.5 & 27.4 & 75.0 & 3.1 & 17.6 & 0.2 \\  & Wednesday & 443.2 & 988.5 & 27.5 & 74.9 & 3.1 & 17.5 & 0.2 \\  & Thursday & 443.2 & 988.5 & 27.6 & 75.2 & 3.2 & 17.7 & 0.2 \\  & Friday & 443.2 & 988.5 & 27.2 & 73.4 & 3.1 & 17.5 & 0.2 \\  & Saturday & 443.2 & 988.5 & 20.2 & 69.1 & 2.1 & 14.8 & 0.1 \\  & Sunday & 443.2 & 988.5 & 19.9 & 67.2 & 2.0 & 14.6 & 0.1 \\ \hline Ger06 & Monday & 4688.2 & 10,795.8 & 7.0 & 20.1 & 1.7 & 33.1 & 0.3 \\  & midweek & 4688.2 & 10,795.8 & 7.2 & 19.5 & 1.7 & 33.1 & 0.3 \\  & Friday & 4688.2 & 10,795.8 & 6.4 & 18.9 & 1.5 & 32.0 & 0.3 \\  & Saturday & 4688.2 & 10,795.8 & 3.9 & 15.8 & 0.8 & 28.5 & 0.2 \\  & Sunday & 4688.2 & 10,795.8 & 2.5 & 15.0 & 0.4 & 26.2 & 0.2 \\ \hline SynEur & Low & 18,010.2 & 42,188.7 & 0.1 & 13.2 & 0.3 & 125.2 & 0.8 \\  & Medium & 18,010.2 & 42,188.7 & 1.0 & 13.2 & 0.8 & 124.9 & 0.8 \\  & High & 18,010.2 & 42,188.7 & 6.2 & 13.2 & 4.6 & 124.8 & 1.0 \\ \hline Ger17 & Tuesday & 7247.6 & 15,752.1 & 29.2 & 31.6 & 3.5 & 20.8 & 1.3 \\ \hline Eur17 & Tuesday & 25,758.0 & 55,503.8 & 27.2 & 29.5 & 2.7 & 19.0 & 4.2 \\ \hline Eur20 & Tuesday & 28,510.0 & 60,898.8 & 76.3 & 22.5 & 21.0 & 34.9 & 8.7 \\ \hline \end{tabular}
\end{table} 
Table 14: Characteristics of test instances used. The third column contains the percentage of arcs with a non-constant travel time function. The fourth column the average number of breakpoints among those. The fifth and sixth columns report the relative total delay for all/only non-constant arcs. The final column contains the graph size in a compact representation in memory.