Contraction Hierarchies

The preprocessing phase iteratively removes nodes from the graph one by one, in a specific order of 'importance'. When a node v is contracted, it is removed, and shortcut edges are added between its neighbors to preserve the shortest path distances. A shortcut is only added if the path through v was the unique shortest path between two neighbors. This process effectively encodes all-pairs shortest-path information into a sparser but augmented graph.

Queries are executed as a bidirectional variant of Dijkstra's algorithm. The forward search from the source only traverses edges leading to nodes with a higher importance (rank), while the backward search from the target traverses edges from nodes with a lower importance. Both searches meet at the highest-ranked node on the shortest path, known as the 'meeting point'. This drastically limits the search space to a small, cone-shaped subgraph.

The performance of CH critically depends on the order in which nodes are contracted. Poor ordering leads to an explosion of shortcuts and degrades query speed. Common heuristics combine several factors to compute a priority score for each node:

• Edge Difference: The difference between shortcuts added and edges removed.
• Uniformity: Penalizes contracting nodes that create dense clusters of shortcuts.
• Cost of Contraction: The raw computational cost of simulating the contraction. Nodes with the lowest priority score are contracted first.

CH is fundamentally a static graph algorithm. The preprocessing step is computationally intensive and must be re-run from scratch if the underlying road network topology or edge weights (e.g., average travel times) change significantly. This makes it ideal for core routing on stable maps but requires a complementary dynamic layer, such as Time-Dependent VRP solvers or Model Predictive Control, to handle real-time traffic incidents or road closures during the actual route execution.

Unlike many heuristic or approximate methods, Contraction Hierarchies is an exact algorithm. The bidirectional query on the augmented graph is mathematically proven to find the identical optimal shortest path as a full Dijkstra's search on the original graph. This property is non-negotiable for logistics applications where precise distance and time calculations are required for cost estimation, driver payroll, and guaranteed service level agreements.

A strategy that runs two simultaneous searches: one forward from the origin and one backward from the destination. The algorithm terminates when the two search frontiers meet. Contraction Hierarchies inherently leverage a bidirectional approach, but with a critical advantage—the preprocessing step orders nodes so that the forward and backward searches only need to traverse a small, upward-closed subset of the graph.

A predecessor to Contraction Hierarchies that also uses preprocessing to accelerate queries. It identifies and contracts low-importance local roads around each node, creating a hierarchy of increasingly important highway levels. While effective, Contraction Hierarchies are generally simpler to implement, offer faster query times, and have become the more widely adopted standard in production routing engines.

The offline phase where the road network is transformed to enable sub-millisecond queries. For Contraction Hierarchies, this involves:

• Node Ordering: Heuristically ranking nodes by importance using edge difference metrics.
• Node Contraction: Removing nodes one by one and adding shortcut edges to preserve shortest-path distances between remaining neighbors. This one-time computation is what enables the dramatic query-time speedup.

A synthetic edge inserted during the contraction of a node v. If the only shortest path between neighbors u and w passes through v, a shortcut edge u → w is added with a weight equal to the sum of u → v and v → w. This preserves all shortest-path distances in the remaining graph. During a query, the algorithm only relaxes edges leading to nodes with a higher rank, guaranteeing correctness.