Customizable Contraction Hierarchies – A Survey

Thomas Bläsius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, Michael Zündorf · 2025

Read Customizable Contraction Hierarchies – A Survey by Thomas Bläsius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, Michael Zündorf (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10519.txt.

Introduction

Thomas Bläsius and co-authors survey a route-planning technique that powers fast directions on road maps. Contraction hierarchies pre-rank road junctions so searches can skip most of the network. The customizable version splits the work: a slow setup that knows only the map's shape, then a fast update whenever travel times change. That split suits live traffic and personal preferences.

The survey gathers the state of the art, walks through recent advances, and shows how to combine them into one clean implementation. The authors add their own refinements on top. Wide tests show the framework matches rival methods on speed while supporting more features. The paper serves as both a reference and a build guide for engineers who need directions that adapt in seconds.

Catalog record

CREATORThomas Bläsius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, Michael Zündorf
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-10519

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Customizable Contraction Hierarchies – A Survey Thomas Bläsius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, Michael Zündorf Abstract This work establishes the technical fundamentals of a well-tuned Customizable Contraction Hierarchies (CCH) implementation that is simple and elegant. We give a detailed overview of the state of the art of CCH, review recent advances on CCH and show how to combine them. Additionally, we propose further refinements that improve the performance of CCH. An extensive evaluation confirms that a CCH framework is not only comprehensive in supported features but also competitive in performance to both Contraction Hierarchies (CH) and Customizable Route Planning (CRP). Karlsruhe Institute of Technology, Germany Karlsruhe Institute of Technology, Germany Karlsruhe Institute of Technology, Germany Karlsruhe Institute of Technology, Germany Karlsruhe Institute of Technology, Germany This work was supported by funding from the pilot program Core-Informatics of the Helmholtz Association (HGF) ccs Theory of computation Shortest paths ccs Mathematics of computing Graph algorithms ccs Applied computing Transportation keywords realistic road networks, customizable contraction hierarchies, route planning, shortest paths † † runningauthor: T. Bläsius, V. Buchhold, D. Wagner, T. Zeitz, and M. Zündorf † † copyright: Thomas Bläsius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction A routing framework for modern map and navigation applications requires far more than an effective speedup technique for the quick computation of shortest paths [ 8 ] . While the shortest path computation should not be the bottleneck of the routing engine, there are many additional requirements. A practical algorithm must handle not only car travel times but also other length functions (metrics) such as walking, biking, or user-defined preferences, for example, to avoid highways. Further, dynamic routing considering real-time traffic is critical. Therefore, updates to the length function must be fast enough for frequent adjustments. Integrating turn costs and restrictions is also an essential requirement for high-quality routing. Finally, point-of-interest queries are also an important feature in such applications. The first speedup technique that supports this entirety of requirements is Customizable Route Planning (CRP) sometimes also referred to as Multi Level Dijkstra (MLD) [ 8 , 10 ] . This technique is also the first to take advantage of a three-phase approach where the classical preprocessing phase is split into an metric-independent phase and a customization phase . The motivation behind this is that topological updates happen much less frequently than metric updates and thus only one part of the preprocessing has to be redone frequently. Inspired by CRP, Contraction Hierarchies (CH) have also been extended to a three-phase setup [ 11 ] . This variant is called Customizable Contraction Hierarchies (CCH). Classical CH uses heuristic ad-hoc methods to build “good enough” axillary data in reasonable preprocessing running times. These methods only work well for well-behaved weight functions with a strong hierarchy. In contrast, CCH draws on nested dissections and algorithms from chordal graph theory for the augmented graph construction. This yields surprisingly elegant and simple algorithms that also have stronger theoretical guarantees. CCH queries are roughly as fast as CH queries, i.e., around an order of magnitude faster than CRP. On the downside, the CCH customization is slower than the CRP customization thus far. Also, the CCH proposed by Dibbelt et al. does not support all the features mentioned above. However, CCH is an area of active research and in the past few years, there have been several research articles [ 4 , 5 , 6 , 16 ] improving CCH and pushing it closer to feature parity with CRP. Contribution and Overview. In this work, we give a detailed overview of the state of the art of CCHs. We review recent advances, show how to combine them, propose additional refinements, and provide a state-of-the-art reference implementation. While this involves introducing, explaining, and discussing various concepts and details, we also strive to provide an accessible introduction to CCHs that is understandable without prior knowledge in route planning. To achieve this, we start with a description on a high level of abstraction in Section 2 . This description is complete in the sense that it fully explains how and why CCH works, while leaving some freedom of how to exactly implement it. In Section 3 we discuss in detail the different ways of implementing the various aspects of a CCH, with a focus on the state of the art. This is also the section where we propose several improvements to what has been done in the literature before. This includes a simpler and more efficient algorithm for the metric-independent preprocessing in Section 3.1 and a better parallelization of the customization in Section 3.2 (basic as well as perfect customization). In Section 4 , we discuss the extended scenarios of point-of-interest queries as well as turn costs. Moreover, we provide an adaptation of the Lazy RPHAST algorithm for one-to-many queries from CHs to CCHs, which in particular accelerates point-of-interest queries. Finally, in Section 5 , we evaluate our reference implementation. Besides showing that our improvements are actually improvements, we also make a comparison to related techniques that are not the subject of this paper. 2 Customizable Contraction Hierarchies At its core, the CCH framework has a preprocessing phase that augments the input graph with additional edges, which then speed-up subsequent shortest-path queries. In the following, we give a concise introduction into how and why this works. We assume that the input consists of an undirected graph G=(V,E) together with a weight function \ell\colon V\times V\to\mathbb{R}^{\geq 0}\cup\{\infty\} with \ell(u,v)=\infty for \{u,v\}\notin E . Note that the graph itself is undirected while the weight function is directed. Thus, for an edge \{u,v\}\in E , the weights \ell(u,v) and \ell(v,u) can be different and \ell(u,v) represents the cost to traverse the edge \{u,v\} from u to v . This definition allows us to work with the graph’s topology independent of directions but still allows asymmetric costs as well as one-way streets (using \infty as weight for one direction). The length of a path \langle v_{0},\dots,v_{k}\rangle is \sum_{i=1}^{k}\ell(v_{i-1},v_{i}) and the distance from one vertex to another is the length of the shortest path between them. The CCH preprocessing starts by assigning every vertex a unique rank and constructing the augmented graph G^{+}=(V,E^{+}) by contracting the vertices in rank order , i.e., by increasing ranks. For vertices u,v\in V , we also write u\prec v if the rank of u is smaller than the rank of v . To contract v\in V , complete the neighbors of v with higher rank to a clique; see Figure 1 for an example 1 1 1 We note that G^{+} is chordal and that the rank order is a perfect elimination scheme. . The edges created this way are called shortcuts . The idea is to perform shortest-path queries on G^{+} instead of G . To take the new shortcut edges into account, we also define a modified weight function \ell^{+}\colon V\times V\to\mathbb{R}^{\geq 0}\cup\{\infty\}

Read the complete text