Transit node routing

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. Transit node routing as a framework was established in 20071 and many concrete implementations have surfaced in the years after such as approaches using grids, highway hierarchies and contraction hierarchies. Transit node routing is a static approach that requires pre-processing of pair-wise distances between important nodes in the graph (see below how those nodes are chosen). A dynamic approach has not been published. __TOC__

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. Transit node routing as a framework was established in 2007 and many concrete implementations have surfaced in the years after such as approaches using grids, highway hierarchies and contraction hierarchies. Transit node routing is a static approach that requires pre-processing of pair-wise distances between important nodes in the graph (see below how those nodes are chosen). A dynamic approach has not been published. __TOC__ 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)

Geometrical approach using grids

In a grid-based approach, the bounding square of all nodes is equally subdivided into square cells. How are access nodes selected? For each cell C , a set of access nodes can be found by looking at an inner area I of 5x5 cells and an outer area O of 9x9 cells around C . Focusing on crossing nodes (ends of edges that cross the boundary of C , I or O ), the access nodes for C are those nodes of I that are part of a shortest path from some node in C to a node in O . As access nodes for an arbitrary node v \in C all access nodes of C are chosen (red dots in the image to the right). How are transit nodes selected? The set of transit nodes is exactly the union of all sets of access nodes. Which locality filter should be used? 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. If they lie closer together, a fallback-algorithm is used to obtain the distance. How should local queries be handled? 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.

Using contraction hierarchies

How are transit nodes selected? By definition, a contraction hierarchy moves important nodes (i.e. nodes that are part of many shortest paths) to the top of the hierarchy. A set of transit nodes therefore can be selected as the k highest nodes of the contraction hierarchy. How are access nodes selected? Forward access nodes of a node v can be found by running the upward-search of the contraction hierarchy starting at v . During the upward-search, edges leaving previously found transit nodes aren't relaxed. When the search has no more upward nodes left to settle, those transit nodes that have been settled are the access nodes of v . Backward access nodes can be found analogously. Which locality filter should be used? If the highest node of a shortest up-down-path in the hierarchy is not part of the set of transit nodes, then the query was local. This implies that neither the up-part of the path (beginning at the starting node) nor the down-part of the path (ending at the target node) can contain a transit node and there must be a common node in both paths. During the calculation of the access nodes, the search space (all visited nodes towards the top of the hierarchy) for each node can be stored without including transit nodes. When performing a query, those search spaces for start- and target node are checked for an intersection. If those spaces are disjoint, transit node routing can be used because the up- and down-paths must meet at a transit node. Otherwise there could be a shortest path without a transit node. How should local queries be handled? Local queries use the regular query algorithm of the contraction hierarchy.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1365858181 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Transit node routing” revision 1365858181 · retrieved 2026-10-20 date of establishment (×1) · confidence 0.95 revision URL

Provenance

snapshot enwiki-001365858181 · captured 1784920535.0 · version history

Cite this page as: encyclopegia.org, “Transit node routing”, snapshot enwiki-001365858181. https://encyclopegia.org/a/transit-node-routing