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.

Intuition

Long-distance travel usually involves driving along a specialised subset of the road network such as highways. 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.

Because the number of such access nodes is small compared to the overall number of nodes in a road network, all shortest routes connecting those nodes with each other can be pre-calculated and stored. When calculating a shortest path therefore only routes to access nodes close to start and target location need to be calculated.

General Framework

1. Transit node routing starts with a selection of transit nodes $T\subseteq V$ as a subset of all nodes $V$ of the road network.
2. For every node $v\in V$ dedicated sets of forward access-nodes ${\overrightarrow {A}}(v)\subseteq T$ and backward access-nodes ${\overleftarrow {A}}(v)\subseteq T$ are chosen from all transit nodes.
3. Now, pairwise distances between transit nodes $D_{T}$ and distances between nodes $v$ and their corresponding access-nodes $d_{A}$ are calculated.
4. A distance between two nodes can now be calculated as $d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{A}(s,u)+D_{T}(u,v)+d_{A}(v,t)$

Locality Filter

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.

To prevent this kind of problem, a locality filter can be used. 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.