In this paper, we present an overview over existing speed-up techniques for time-dependent route planning. Apart from only explaining each technique one by one, we follow a more systematic approach. We identify basic ingredients of these recent techniques and show how they need to be augmented to guarantee correctness in time-dependent networks. With the ingredients adapted, three efficient speed-up techniques can be set up: Core-ALT, SHARC, and Contraction Hierarchies. Experiments on real-world data deriving from road networks and public transportation confirm that these techniques allow the fast computation of time-dependent shortest paths. © 2009 Springer-Verlag Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-05465-5_8Cite as:
@incollection{Delling_2009,
doi = {10.1007/978-3-642-05465-5_8},
url = {https://doi.org/10.1007%2F978-3-642-05465-5_8},
year = 2009,
publisher = {Springer Berlin Heidelberg},
pages = {207--230},
author = {Daniel Delling and Dorothea Wagner},
title = {Time-Dependent Route Planning},
booktitle = {Robust and Online Large-Scale Optimization}
}