  We present a new heuristic point-to-point routing 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. CH is based on node contraction:
removing nodes from a network and adding shortcut edges to preserve shortest
path distances. Our algorithm tries to avoid shortcuts even when a replacement
path is epsilon times longer.
