Time-Dependent Contraction Hierarchies

Contraction hierarchies are a simple hierarchical rout-ing 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 algo-rithms. For large realistic networks with considerable time-dependence (Germany, weekdays) our method out-performs previous techniques with respect to query time using comparable or lower preprocessing time.