Customizable Contraction Hierarchies
This addresses the need for efficient shortest-path computations in dynamic scenarios like traffic routing or game maps, though it is incremental as it builds on existing Contraction Hierarchies and three-phase workflows.
The paper tackled the problem of quickly computing shortest paths in weighted graphs with frequently changing edge weights by extending Contraction Hierarchies with a fast weight-customization phase, resulting in a practicable solution with experimental analysis on large road and game maps.
We consider the problem of quickly computing shortest paths in weighted graphs given auxiliary data derived in an expensive preprocessing phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies by Geisberger et al to support the three-phase workflow introduced by Delling et al. Our Customizable Contraction Hierarchies use nested dissection orders as suggested by Bauer et al. We provide an in-depth experimental analysis on large road and game maps that clearly shows that Customizable Contraction Hierarchies are a very practicable solution in scenarios where edge weights often change.