Heuristic Contraction Hierarchies with Approximation Guarantee
DOI:
https://doi.org/10.1609/socs.v1i1.18161Keywords:
route planning, shortest paths problem, approximation, algorithm engineeringAbstract
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.
Downloads
Published
2010-08-25
Issue
Section
Oral Presentations