Over the years, Oslandia has been able to apply its GIS expertise many times over the transport field, and particularly to route planning. Even if software development and databases are our natural entry points into the subject, we do not lose sight of algorithmic issues!
We have recently turned our attention to the discipline’s king of algorithms, which has some of the most interesting computation times: Hierarchical Contractions.
What are Hierarchical Contractions?
Hierarchical Contractions algorithm is based on a pre-processing step, which drastically accelerates computation times of shortest paths queries.
The main features of this algorithm are the following:
– Virtual edges, called “shortcuts”, are defined to compact information contained in the graph. Short-circuited nodes are said to be “contracted”.
– Nodes are ranked in order of importance, during the pre-processing, so that the highest nodes in the hierarchy are the most likely to be used by shortest paths (typically, large urban arterials intersections or busy motorway sections) and the less likely to be contracted.
Shortcut creation mechanism: an intermediate node u is contracted only if it has a lower level than the source s and destination d in the hierarchy l, and if there is no better alternative path P (cases (c) and (g)).
– The shortest path search exploits the node hierarchy and shortcuts defined during pre-processing, and is divided into two components: a forward search from the source, and a backward search from the destination. These two components converge at the top level of the node hierarchy.
Type of path highlighted by the hierarchical contraction procedure, between a source “s” and a destination “d”
Can we use that in PostgreSQL?
Hierarchical Contractions are implemented in several Open Source projects. For example, RoutingKit is a project initiated by the research team which proposed and implemented for the first time Hierarchical Contractions, and OSRM.
On the side of PostgreSQL, the fastest way to benefit from routing algorithms is the pgRouting extension. Unfortunately, this extension does not currently include Hierarchical Contractions. However, PgRouting offers lighter contraction algorithms, which can handle dead-ends as well as corridors (chains of consecutive sections without junctions).
In this example, taken from the PgRouting documentation, node 1 will be for example contracted as a dead end and node 8 as a corridor.
To illustrate, a full scale test on data from BDCarto for mainland France can be carried out. The initial graph is made of about 1.12M nodes and 1.65M arcs. After application of both types of contraction, resulting graph is made of about 0.86M nodes and 1.48M arcs, i.e. reductions of 22.9% and 10.2% respectively.
Examples of contraction results on the BD Carto, in red the network before preprocessing and in red after
With a Dijkstra-type algorithm, the expected gains in computation time are therefore limited, to the order of 30% at most. Hierarchical contractions, on the other hand, offer far greater improvements, and would therefore be a key contribution to pgRouting.
Oslandia, Open source and Contraction Hierarchies
As said in a previous post, Oslandia dedicates development days to open-source projects of the GIS ecosystem. PgRouting falls squarely within this framework and Hierarchical Contractions integration in this PostgreSQL extension appears to us as particularly attractive challenge!
If you’re interested in this subject, and would like to join us on this adventure, please don’t hesitate to contact us at info@oslandia.com!
