AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
Heuristic Contraction Hierarchies with Approximation Guarantee
Robert Geisberger, Dennis Schieferdecker

Last modified: 2010-08-25


We present a new heuristic point-to-point shortest path algorithm based on contraction hierarchies (CH). Given an epsilon >= 0, we can prove that the length of the path computed by our algorithm is at most (1 + ε) times the length of the optimal (shortest) path. Exact CH is based on node contraction: removing nodes from a network and adding shortcuts to preserve shortest path distances. Our heuristic CH tries to avoid adding shortcuts even when a replacement path is (1+epsilon) times longer. However, we cannot avoid all such shortcuts, as we need to ensure that errors do not stack. Combinations with goal-directed techniques bring further speed-ups.


route planning; shortest paths problem; approximation; algorithm engineering

Full Text: PDF