# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
We use traffic predictions for a car on a typical midweek day or a Tuesday. Table 1 lists characteristics of each graph. For time-independent routing, the performance of algorithms primarily depends on the size of the network. In our case, however, the amount and complexity of time-dependent information also has a significant impact on the performance. To measure this, we report the fraction of arcs which have a non-constant travel time and the average number of breakpoints among all non-constant travel time functions. We also report the _relative total delay_\(\frac{\sum_{a}\max f_{a}-\min f_{a}}{\sum_{a}\min f_{a}}\) as a measure for the degree of time-dependency of the predictions. (Variants of this measure have been used in previous works. Delling reported \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & **Nodes** & **Arcs** & **TD arcs** & **Avg. \(|f|\)** & **Rel. Delay** & **Rel. Delay** & **Size** \\  & [-10\({}^{3}\)] & [-10\({}^{3}\)] & [\%] & **per TD arc** & **[\%]** & **TD [\%]** & **[GB]** \\ \hline Ber & 443.2 & 988.5 & 27.4 & 75.0 & 3.1 & 17.6 & 0.2 \\ Ger06 & 4688.2 & 10,795.8 & 7.2 & 19.5 & 1.7 & 33.1 & 0.3 \\ Ger17 & 7247.6 & 15,752.1 & 29.2 & 31.6 & 3.5 & 20.8 & 1.3 \\ Eur17 & 25,758.0 & 55,503.8 & 27.2 & 29.5 & 2.7 & 19.0 & 4.2 \\ Eur20 & 28,510.0 & 60,898.8 & 76.3 & 22.5 & 21.0 & 34.9 & 8.7 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: 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. the average relative delay of time-dependent earliest arrival queries over the result of a time-independent query with lower bound travel times in [14]. [PERSON] reported the average _relative delay_\(\frac{\max f_{a}-\min f_{a}}{\min f_{a}}\) in [8]. We use the _total_ delay because averages of ratios have hard to interpret semantics [31]. For example, a short arc with a large relative delay could have a much bigger influence on the average relative delay than it has on the actual shortest path structure.). The smaller is the relative delay, the greater is the effectiveness of pruning with upper and lower bounds. The Ber instance was provided by TomTom ([[https://www.tomtom.com](https://www.tomtom.com)]([https://www.tomtom.com](https://www.tomtom.com)) (accessed on 15 March 2021)) in 2013. It contains the northern eastern part of Germany, but in the literature it is referred to by the largest city, Berlin. This instance features the most complex input functions and 27.4% of the arcs have a non-constant travel time function. However, the road network is quite small which makes the instance comparatively easy. All other instances were provided by PTV ([[https://ptvgroup.com](https://ptvgroup.com)]([https://ptvgroup.com](https://ptvgroup.com)) (accessed on 15 March 2021)). The Ger06 instance is the easiest with respect to all time-dependency measures except the total relative delay limited to non-constant travel time functions. That means that the degree of time-dependency in the non-constant functions is significant. However, the overall influence on the shortest path structure is limited, because only 7.2% of the arcs have a non-constant travel time. Ger06 has also the smallest average complexity of non-constant travel time functions. The newer graphs are not only bigger in terms of number of nodes and arcs but have also significantly more non-constant travel time functions. Ger17 has four times as many time-dependent arcs as Ger06 and about 1.5 times as many breakpoints per time-dependent function. Even though the relative delay among non-constant functions is not as high as for Ger06, the relative delay among all arcs is twice as high. Eur17 exhibits similar characteristics but additionally has 3.5 times as many nodes and arcs.