Symposium on Combinatorial Search (SoCS 2010)

Stone Mountain, Atlanta, Georgia, USA

Juli 2010

R. Geisberger, D. Schieferdecker

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.

• PDF