Contraction hierarchies

The contraction hierarchies (CH) algorithm is a two-phase approach to the shortest path problem consisting of a preprocessing phase and a query phase. As road networks change rather infrequently, more time (seconds to hours) can be used to once precompute some calculations before queries are to be answered. Using this precomputed data, many queries can be answered taking very little time (microseconds) each. heuristics are used. Top-down heuristics, on the other hand, yield better results but need more preprocessing time. They classify vertices that are part of many shortest paths as more important than those that are only needed for a few shortest paths. This can be approximated using nested dissections. the intuition being that all queries from one half of the graph to the other half of the graph need to pass through the small separator and therefore nodes in this separator are of high importance. Nested dissections can be efficiently calculated on road networks because of their small separators. Query phase In the query phase, a bidirectional search is performed starting from the starting node s and the target node t on the original graph augmented by the shortcuts created in the preprocessing phase. The most important vertex on the shortest path between s and t will be either s or t themselves or more important than both s and t. Therefore, the vertex u minimizing \mathrm{dist}(s, u) + \mathrm{dist}(u, t) is on the shortest s-t path in the original graph and \mathrm{dist}(s, u) + \mathrm{dist}(u, t) = \mathrm{dist}(s, t) holds. This, in combination with how shortcuts are created, means that both forward and backward search only need to relax edges leading to more important nodes (upwards) in the hierarchy which keeps the search space small. In all up-(down-up)-down paths, the inner (down-up) can be skipped, because a shortcut has been created in the preprocessing stage. Path retrieval A CH query, as described above, yields the time or distance from s to t but not the actual path. To obtain the list of edges (roads) on the shortest path, the shortcuts taken have to be unpacked. Each shortcut is the concatenation of two edges: either two edges of the original graph, or two shortcuts, or one original edge and one shortcut. Storing the middle vertex of each shortcut during contraction enables linear-time recursive unpacking of the shortest route. == Customized contraction hierarchies ==

If the edge weights are changed more often than the network topology, CH can be extended to a three-phase approach by including a customization phase between the preprocessing and query phase. This can be used for example to switch between shortest distance and shortest time or include current traffic information as well as user preferences like avoiding certain types of roads (ferries, highways, ...). In the preprocessing phase, most of the runtime is spent on computing the order in which the nodes are contracted. This sequence of contraction operations in the preprocessing phase can be saved for when they are later needed in the customization phase. Each time the metric is customized, the contractions can then be efficiently applied in the stored order using the custom metric. Additionally, depending on the new edge weights it may be necessary to recompute some shortcuts. For this to work, the contraction order has to be computed using metric-independent nested dissections. == Extensions and applications ==

CHs as described above search for a shortest path from one starting node to one target node. This is called one-to-one shortest path and is used for example in car-navigation systems. Other applications include matching GPS traces to road segments and speeding up traffic simulators which have to consider the likely routes taken by all drivers in a network. In route prediction one tries to estimate where a vehicle is likely headed by calculating how well its current and past positions agree with a shortest path from its starting point to any possible target. This can be efficiently done using CHs. Note, that this is possible because the order in which the nodes are processed in the second phase is independent of the source node s. In production, car-navigation systems should be able to compute fastest travel routes using predicted traffic information and display alternative routes. Both can be done using CHs. The former is called routing with time-dependent networks where the travel time of a given edge is no longer constant but rather a function of the time of day when entering the edge. Alternative routes need to be smooth-looking, significantly different from the shortest path but not significantly longer. CHs can be extended to optimize multiple metrics at the same time; this is called multi-criteria route planning. For example, one could minimize both travel cost and time. Another example are electric vehicles for which the available battery charge constrains the valid routes as the battery may not run empty. == Theory ==

A number of bounds have been established on the preprocessing and query performance of contraction hierarchies. In the following let n be the number of vertices in the graph, m the number of edges, h the highway dimension, D the graph diameter, td is the tree-depth and tw is the tree-width. The first analysis of contraction hierarchy performance relies in part on a quantity known as the highway dimension. While the definition of this quantity is technical, intuitively a graph has a small highway dimension if for every r>0 there is a sparse set of vertices S_r such that every shortest path of length greater than r includes a vertex from S_r. Calculating the exact value of the highway dimension is NP-hard and most likely Parameterized complexity|W[1]-hard, but for grids it is known that the highway dimension is h\in\Theta(\sqrt{n}). An alternative analysis was presented in the Customizable Contraction Hierarchy line of work. Query running times can be bounded by O(td^2). As the tree-depth can be bounded in terms of the tree-width, O((tw \log n)^2) is also a valid upper bound. The main source is but the consequences for the worst case running times are better detailed in. Preprocessing Performance Query Performance == References ==