Time-Dependent Contraction Hierarchies
Gernot Veit Batz, Daniel Delling, Peter W. Sanders, Christian Vetter · Society for Industrial and Applied Mathematics eBooks · 2009
Contraction hierarchies are a simple hierarchical routing technique that has proved extremely efficient for static road networks. We explain how to generalize them to networks with time-dependent edge weights. This is the first hierarchical speedup technique for time-dependent routing that allows bidirectional query algorithms. For large realistic networks with considerable time-dependence (Germany, weekdays) our method outperforms previous techniques with respect to query time using comparable or lower preprocessing time.