Contraction hierarchies

From Wikipedia, the free encyclopedia

In applied mathematics, the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contracted" versions of the connection graph.[1] It can be regarded as a special case of "highway-node routing".

Contraction hierarchies can be used to generate shortest-path routes much more efficiently than Dijkstra's algorithm or previous highway-node routing approaches,[1] and is used in many advanced routing techniques.[2] It is publicly available in open source software to calculate routes from one place to another.[3][4][5]

The algorithm

In general, scalable map routing algorithms have two distinct phases: preprocessing of the original graph (which may take more than an hour to finish) and queries (less than a second). Contraction hierarchy is an extreme case of "hierarchy" approach, which generates a multi-layered node hierarchy in the preprocessing stage. In CH every node in the graph is represented as its own level of hierarchy. This can be achieved in many ways; one simple way is simply to label each node in order of some enumeration from 1 to |N|. More sophisticated approaches might consider the type of road (highway vs minor road, etc.).

A nice explanation of contraction hierarchy is given in lectures from Prof. Bast at University Freiburg.[6]

Note: As of 2013-02-09 this "algorithm" section is derived in part from tutorial material by Ivan Škugor.[7] The copyright holder has licensed the content utilized under CC-By.

Preprocessing

Levels/order of nodes in CH can be arbitrary. The main point is that shortcuts are introduced when necessary. To understand when a shortcut is necessary, one has to understand the searching algorithm. The searching algorithm (bidirectional Dijkstra's algorithm) in this case is constrained so that it only relaxes edges that are connected to the nodes that are higher in CH than current node in one direction, and vice versa. With this constraint, the algorithm would not find certain shortest paths in the unprocessed network, and because of that we need to introduce new edges to the graph that represent existing shortest paths that the algorithm doesn't take into consideration. Not all shortest paths need to be restored as new shortcut edges: it's enough to take in consideration adjacent nodes of some node that are higher in CH (since the sub-path of some shortest path is itself a shortest path). Algorithmically:

  • Add order/levels to the graph nodes
  • For each node, respecting order, get its adjacent nodes of higher order and find if shortest path between each pair of them goes through current node and if it is, add shortcut edge

Let's say that we take in consideration just 2 adjacent nodes (from, in general, n of them):

From this picture, if shortest path from v to w goes through node u that is lower in CH, a new edge has to be added the CH graph so that the shortest paths that the searching algorithm takes into consideration are preserved.

The weight of the new edge is equal to the path distance from v to w.

When preprocessing of the original graph is done, we have a CH graph which consists of the original graph with node ordering added and with shortcut edges introduced.

Querying

For the searching algorithm, bidirectional Dijkstra's algorithm is used. It is classical Dijkstra's algorithm with some modifications. The algorithm searches from the starting node in one direction and from the ending node in other direction (this is classical bidirectional Dijkstra's algorithm), but it relaxes edges that are directed toward higher hierarchy nodes in one direction (essentially it expands towards higher hierarchy nodes) and edges that are directed toward lower hierarchy nodes in the other direction. If the shortest path exists, those two searches will meet at some node v. A shortest path from s to t consists from paths from s to v and from v to t.

The shortest paths found by this algorithm have particular form:

<s=u_{0},u_{1},...,u_{p}=v,...,u_{q}=t>,p,q\in N

ui<u_{{i+1}}zai\in N,i<p

uj>u_{{j+1}}zaj\in N,p\leq j<q

A path found by a query is the shortest path because of the preprocessing stage. In the preprocessing stage we transformed graph introducing shortcut edges, which represents the shortest paths that algorithm does not take into consideration.

In order to return the final result, the shortcut edges need to be postprocessed to give the actual paths they represent in the original graph.

In order to demonstrate that this algorithm retrieves shortest paths, consider it by contradiction: let's assume (for forward search, identical thing stands for backward search) that there exists a path that is shorter than the one we found with this algorithm:

Let's say that at some point there exists a subpath that is shorter than path. Because algorithm expands towards nodes that have higher order, order of u_{k} node must be lower than order of u_{{k-1}} and u_{{k+1}} nodes. Because of that fact, in preprocessing stage that path would be represented as shortcut edge with equal length, and therefore no such path that is shorter than the one algorithm found can exists.

References

  1. ↑ 1.0 1.1 Robert Geisberger (1 July 2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (Thesis). Institut für Theoretische Informatik Universität Karlsruhe. Retrieved 2010-12-27. 
  2. ↑ Delling, D. and Sanders, P. and Schultes, D. and Wagner, D. (2009). "Engineering route planning algorithms". Algorithmics of large and complex networks. Springer. pp. 117–139. doi:10.1007/978-3-642-02094-0_7. 
  3. ↑ "OSRM - Open Source Routing Machine". 
  4. ↑ "Wiki - OpenTripPlanner". 
  5. ↑ "Web - GraphHopper". 
  6. ↑ Hannah Bast (2012). "Efficient Route Planning, Lectures". 
  7. ↑ Ivan Škugor (2012). "Contraction hierarchies". Retrieved 10 February 2013.  (CC-BY)
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.