# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
This clearly demonstrates the advantage of storing expansion information instead of travel time functions. Revisiting ATCH, TCH and TD-CRP with the insights gained in this work could be fruitful. Combining ATCH with our A* query extension could reduce ATCH query running times. CATCHUp makes use of travel time independent node orders. Combining CATCHUp with TCH-like node orders could result in even smaller index sizes and query running times. We further expect that some of our optimizations to the preprocessing can also be applied in a TD-CRP context. Another possible direction for future research would be to support partial updates to further accelerate the customization. This could enable the integration of live traffic information. Conceptualization, B.S. and T.Z. ; methodology, B.S. and T.Z. ; software, T.Z. ; validation, B.S. and T.Z. ; formal analysis, T.Z. ; investigation, B.S. and T.Z. ; resources, D.W.; data curation, B.S. and T.Z. ; writing--original draft preparation, B.S. and T.Z. ; writing--review and editing, B.S., D.W. and T.Z. ; visualization, B.S. and T.Z. ; supervision, D.W.; project administration, D.W.; and funding acquisition, D.W. All authors have read and agreed to the published version of the manuscript. This research was funded by Karlsruhe Institute of Technology and BMW Group. We thank [PERSON] and [PERSON] for fruitful discussions and feedback. We also thank [PERSON] for his input on approximation algorithms. We acknowledge support by the KIT-Publication Fund of the Karlsruhe Institute of Technology. The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results. ## Appendix A Extended Experimental Results

In this section, we document our experimental results on additional networks and prediction sets for different weekdays. Table A1 contains characteristics for the full instance set. We report results for predictions for different weekdays on Ber and Ger06. Judging from the numbers in Table A1, the additional weekdays are no harder than the midweek predictions. The SynEur instance uses the Western Europe graph provided for the 9 th DIMACs implementation challenge [32] with synthetic travel time functions [12]. The evaluation in [8] also used the medium and high traffic prediction sets. In comparison to the real world datasets, SynEur features extremely high delays on its time-dependent arcs. However, there are only few time-dependent arcs. Even the high traffic set has less time-dependent arcs than Ger06 midweek. This combination of few time-dependent arcs with extremely high travel time fluctuations causes some interesting effects in our experiments. Since the behavior of CATCHUp is very stable across all real world datasets, we are confident that this is an artifact of the synthetic predictions. Table A2 contains preprocessing results for all graphs. The other days for Ger06 and Ber behave roughly as expected. The weekend instances feature less time-dependent arcs and preprocessing accordingly runs faster. SynEur with medium and high traffic produces some surprising results regarding the unpacking data. Even the medium traffic instance has a higher average number of expansions than Eur17. With high traffic, the number is even greater than on Eur20. The number of arcs with only a single expansion is correspondingly small. We suspect that the reason for this are the extreme relative delays of the predicted travel time functions. These extreme fluctuations in travel time lead to many shortest path changes despite the little amount of time-dependent information. The results for query experiments on all instances reported in Table A3 also confirm our observations from the main part of this article. Each optimization yields similar accelerations. Again, SynEur exhibits surprising behavior. On the one hand, unoptimized queries are surprisingly fast, i.e., up to four times faster than on Eur17.