# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline  & & \multicolumn{4}{c}{Running Time [ms]} & & \\ \cline{2-10}  & & **Corridor** & **Reconstruct** & **Context** & **Exact Profile** & **Paths** & **Total** & \([f]\) & \([X]\) & **Distinct Paths** \\ \hline Ber & Monday & 0.1 & 39.7 & 14.9 & 2.6 & 0.4 & 58.4 & 29,090.5 & 2.7 & 2.3 \\  & Tuesday & 0.1 & 37.8 & 13.9 & 2.8 & 0.4 & 55.6 & 30,974.9 & 2.7 & 2.3 \\  & Wedelsday & 0.1 & 38.4 & 14.1 & 2.8 & 0.4 & 56.5 & 31,126.2 & 2.6 & 2.2 \\  & Thursday & 0.1 & 40.1 & 14.8 & 2.8 & 0.4 & 58.8 & 30,662.1 & 2.7 & 2.3 \\  & Friday & 0.1 & 34.2 & 12.5 & 2.4 & 0.3 & 50.2 & 27,671.5 & 2.6 & 2.2 \\  & Saturday & 0.1 & 11.2 & 3.4 & 1.5 & 0.2 & 16.6 & 17,872.8 & 1.6 & 1.8 \\  & Sunday & 0.1 & 8.9 & 2.5 & 1.4 & 0.2 & 13.2 & 16,768.7 & 1.6 & 1.8 \\ \hline Ger06 & Monday & 0.3 & 42.2 & 17.3 & 0.6 & 0.8 & 62.9 & 9036.7 & 7.0 & 3.1 \\  & midweek & 0.4 & 56.5 & 23.0 & 0.7 & 0.8 & 83.6 & 9359.6 & 6.9 & 3.3 \\  & Friday & 0.3 & 32.4 & 14.0 & 0.5 & 0.7 & 49.3 & 7986.2 & 6.0 & 3.0 \\  & Saturday & 0.2 & 1.7 & 0.9 & 0.1 & 0.4 & 3.6 & 2047.2 & 2.8 & 2.0 \\ \hline SynEur & Low & 2.1 & 591.3 & 501.7 & 0.2 & 7.3 & 1128.2 & 3379.4 & 151.4 & 144.9 \\  & Medium & 3.1 & 1664.3 & 962.7 & 0.4 & 6.1 & 2694.1 & 5226.1 & 99.0 & 90.1 \\  & High & 3.2 & 3321.5 & 1484.9 & 0.5 & 5.3 & 5102.2 & 5939.1 & 7.0 & 69.2 \\ \hline Ger17 & Tuesday & 0.8 & 452.2 & 189.0 & 6.1 & 2.4 & 660.1 & 66,146.0 & 9.7 & 3.7 \\ \hline Eur17 & Tuesday & 1.7 & 1135.8 & 732.9 & 13.0 & 7.8 & 1913.2 & 12,2192.1 & 16.5 & 6.8 \\ \hline Eur20 & Tuesday & 2.8 & 3166.6 & 1507.7 & 12.3 & 10.3 & 47,50 & 107,690.7 & 24.4 & 11.6 \\ \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 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|\)). Column \(|X|\) contains the number of times the shortest path changes during the day. Since the same path may be the fastest for several times, we also report the number of distinct paths in the last column. All values are arithmetic means over 1000 queries executed in bulk with source and target nodes drawn uniformly at random. ## References

* [PERSON] (1959) [PERSON] A Note on Two Problems in Connexion with Graphs. _Numer. Math._**1959**, \(1\), 269-271. [CrossRef]
* [PERSON] et al. (2016) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Route Planning in Transportation Networks. In _Algorithm Engineering--Selected Results and Surveys_; [PERSON], [PERSON], Eds. ; Springer: Berlin/Heidelberg, Germany, 2016; Volume 9220, pp. 19-80. * [PERSON] and [PERSON] (2009) [PERSON]; [PERSON] SHARC: Fast and Robust Unidirectional Routing. _ACM J. Exp. Algorithmics_**2009**, _14_, 1-29. [CrossRef]
* [PERSON] and [PERSON] (2012) [PERSON]; [PERSON] Core Routing on Dynamic Time-Dependent Road Networks. _Informs J. Comput._**2012**, _24_, 187-201. [CrossRef]
* [PERSON] et al. (2016) [PERSON]; [PERSON]; [PERSON] Customizable Contraction Hierarchies. _ACM J. Exp. Algorithmics_**2016**, _21_, 1.5:1-1.549. [CrossRef]
* [PERSON] et al. (2012) [PERSON]; [PERSON]; [PERSON]; [PERSON] Exact Routing in Large Road Networks Using Contraction Hierarchies. _Transp. Sci._**2012**, _46_, 388-404. [CrossRef]
* [PERSON] et al. (2017) [PERSON]; [PERSON]; [PERSON]; [PERSON] Customizable Route Planning in Road Networks. _Transp. Sci._**2017**, _51_, 566-591. [CrossRef]
* [PERSON] et al. (2013) [PERSON]; [PERSON]; [PERSON]; [PERSON] Minimum Time-Dependent Travel Times with Contraction Hierarchies. _ACM J. Exp. Algorithmics_**2013**, _18_, 1-43. [CrossRef]
* [PERSON] et al. (2016) [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON] Dynamic Time-Dependent Route Planning in Road Networks with User Preferences.