Transit node routing

In applied mathematics, transit node routing can be used to speed up shortest-path routing by pre-computing connections between common access nodes to a sub-network relevant to long-distance travel.

[1] Transit node routing as a framework was established in 2007[1] and many concrete implementations have surfaced in the years after such as approaches using grids, highway hierarchies[2] and contraction hierarchies.

This sub-network can only be entered by using sparsely distributed access nodes.

When compared to one another, multiple long-distance routes starting at the same location always use the same small amount of access nodes close to the starting location to enter this network.

In the same way, similar target locations are always reached by using the same access nodes close to them.

When travelling short distances, such access nodes might be never used because the fastest path to the target only uses local roads.

Short routes between close start and target locations may not require any transit nodes.

In this case, the above framework leads to incorrect distances because it forces routes to visit at least one transit node.

For given start and target locations, the locality filter decides, if transit node routing should be applied or if a fallback-routine should be used (local query).

The general framework leaves open a few questions that need to be answered to implement it: The following example implementations of this framework answer these questions using different underlying methods such as grouping nodes in cells of an overlay grid[2] and a more sophisticated implementation based on contraction hierarchies.

The way access nodes are selected implies that if source and target are more than four grid cells apart, a transit node must be passed on the shortest path and the distance can be calculated as described above.

Local queries are only needed if start and target already lie close together, therefore every suitable shortest-path algorithm such as Dijkstra's algorithm or extensions thereof can be chosen.

In the grid-based implementation outlined above, this results in 16 bytes of storage that is required for each node of the road graph.

A full graph of the USA road network has 23,947,347 nodes.

383 MB of storage would be required to store the distance tables.

can be found by running the upward-search of the contraction hierarchy starting at

During the upward-search, edges leaving previously found transit nodes aren't relaxed.

When performing a query, those search spaces for start- and target node are checked for an intersection.