Home | english | Impressum | Sitemap | KIT

Heuristic Contraction Hierarchies with Approximation Guarantee

Heuristic Contraction Hierarchies with Approximation Guarantee
Tagung:

Symposium on Combinatorial Search (SoCS 2010)

Links:PDF
Tagungsort:

Stone Mountain, Atlanta, Georgia, USA

Datum:

Juli 2010

Autoren:

R. Geisberger, D. Schieferdecker

Referent:

Robert Geisberger

Abstract

We present a new heuristic point-to-point shortest paths 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 + epsilon) 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 shortcuts even when a replacement path is 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.