Transit node routing: Difference between revisions

Revision as of 12:51, 28 June 2019

Latest revision as of 19:58, 12 October 2024

(33 intermediate revisions by 12 users not shown)

Line 1:

In [[applied mathematics]], '''transit node routing''' can be used to speed up [[Shortest path routing|shortest-path routing]] by pre-computing connections between common access nodes to a sub-network relevant to long-distance travel.<ref name=":0">{{Cite journal|last1=Bast|first1=H.|last2=Funke|first2=S.|last3=Sanders|first3=P.|last4=Schultes|first4=D.|date=2007-04-27|title=Fast Routing in Road Networks with Transit Nodes|journal=Science|volume=316|issue=5824|pages=566|doi=10.1126/science.1137521|pmid=17463281|issn=0036-8075|bibcode=2007Sci...316..566B|s2cid=16559205 }}</ref>

Transit node routing as a framework was established in 2007<ref name=":0" /> and many concrete implementations have surfaced in the years after such as approaches using grids, highway hierarchies<ref name=":1" /> and [[contraction hierarchies]].<ref name=":2" /> 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.<ref>{{Citation|last1=Schultes|first1=Dominik|chapter=Dynamic Highway-Node Routing|pages=66–79|publisher=Springer Berlin Heidelberg|isbn=9783540728443|last2=Sanders|first2=Peter|doi=10.1007/978-3-540-72845-0_6|title=Experimental Algorithms|volume=4525|series=Lecture Notes in Computer Science|year=2007}}</ref>

__TOC__

== Intuition ==

[[File:Transit node routing intuition.gif|thumb|Multiple routes using the same access nodes to long-distance road network.]]

Long-distance travel usually involves driving along a specialised subset of the [[road network]] such as highways[[Controlled-access highway|freeways]] instead of e.g. urban roads. This sub-network can only be entered by using sparsely distributed access- [[Node (computer science)|nodes]]. When compared to one another, multiple long-distance [[Path (graph theory)|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. This intuition only holds for long-distance travel. When travelling short distances, such access nodes might be never used because the fastest path to the target only uses local roads.

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.

{{Clear}}

== General Framework ==

== General Frameworkframework ==

# Transit node routing starts with a selection of transit nodes <math>T \subseteq V</math> as a subset of all nodes <math>V</math> of the road network.

# For every node <math>v \in V</math> dedicated sets of forward access- nodes <math>\overrightarrow{A}(v) \subseteq T</math> and backward access- nodes <math>\overleftarrow{A}(v) \subseteq T</math> are chosen from all transit nodes.

# Now, pairwise distances between transit nodes <math>D_T</math> and distances between nodes <math>v</math> and their corresponding access- nodes <math>d_A</math> are calculated and stored.

# A distance between two nodes can now be calculated as <math>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)</math>

=== Locality Filterfilter ===

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 (local query).

== ApproachesConcrete instances ==

Transit node routing is not an algorithm but merely a framework for speeding up route planning. The general framework leaves open a few questions that need to be answered to implement it:

* How are transit nodes selected?

=== Grid-based ===

* How are access nodes chosen?

<br />

* Which locality filter should be used?

* How should local queries be handled?

The following example implementations of this framework answer these questions using different underlying methods such as grouping nodes in cells of an overlay [[Grid (spatial index)|grid]]<ref name=":1">{{Citation|last1=Bast|first1=Holger|title=In Transit to Constant Time Shortest-Path Queries in Road Networks|date=2007-01-06|work=2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX)|pages=46–59|publisher=Society for Industrial and Applied Mathematics|isbn=9781611972870|last2=Funke|first2=Stefan|last3=Matijevic|first3=Domagoj|last4=Sanders|first4=Peter|last5=Schultes|first5=Dominik|doi=10.1137/1.9781611972870.5|doi-access=free}}</ref> and a more sophisticated implementation based on [[contraction hierarchies]].<ref name=":2">{{Citation|last1=Arz|first1=Julian|title=Transit Node Routing Reconsidered|date=2013|work=Experimental Algorithms|pages=55–66|publisher=Springer Berlin Heidelberg|isbn=9783642385261|last2=Luxen|first2=Dennis|last3=Sanders|first3=Peter|arxiv=1302.5611|doi=10.1007/978-3-642-38527-8_7|bibcode=2013arXiv1302.5611A|s2cid=14371800 }}</ref>

=== Contraction Hierarchies ===

<br />

=== Geometrical approach using grids===

In a [[Grid (spatial index)|grid]]-based approach, the [[Minimum bounding box|bounding]] square of all nodes is equally subdivided into square cells.

'''How are access nodes selected?'''

[[File:Grid based transit node routing.png|thumb|Access nodes (red dots) for a cell C (red) with inner area I (orange) and outer area O (blue)]]

For each cell <math>C</math>, a set of access nodes can be found by looking at an inner area <math>I</math> of 5x5 cells and an outer area <math>O</math> of 9x9 cells around <math>C</math>. Focusing on crossing nodes (ends of edges that cross the boundary of <math>C</math>, <math>I</math> or <math>O</math>), the access nodes for <math>C</math> are those nodes of <math>I</math> that are part of a shortest path from some node in <math>C</math> to a node in <math>O</math>. As access nodes for an arbitrary node <math>v \in C</math> all access nodes of <math>C</math> 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.

==== Space requirements ====

The pre-computed distances between each node and the corresponding access node as well as the pairwise distances between transit nodes need to be stored in distance tables.

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.<ref>{{Cite web|url=http://users.diag.uniroma1.it/challenge9/download.shtml|title=9th DIMACS Implementation Challenge: Shortest Paths|website=users.diag.uniroma1.it|access-date=2019-07-15}}</ref> Therefore approx. 383 MB of storage would be required to store the distance tables.

=== Using contraction hierarchies===

'''How are transit nodes selected?'''

By definition, a [[Contraction hierarchies|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 <math>k</math>highest nodes of the contraction hierarchy.

'''How are access nodes selected?'''

Forward access nodes of a node <math>v</math> can be found by running the upward-search of the contraction hierarchy starting at <math>v</math>. During the [[Contraction hierarchies#Querying|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 <math>v</math>. 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 sets|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 [[Contraction hierarchies#Querying|query algorithm]] of the contraction hierarchy.

== See also ==

<br />

* [[Shortest path problem]]

== References ==

* [[Hub labels]]

<br />

* [[Bidirectional search]]

* [[Highway dimension]]

== References ==

{{reflist}}

[[Category:Routing algorithms]]

[[Category:Graph algorithms]]