Transit node routing: Difference between revisions

Revision as of 19:19, 19 December 2019

Latest revision as of 19:58, 12 October 2024

(7 intermediate revisions by 7 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|lastlast1=Bast|firstfirst1=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|lastlast1=Schultes|firstfirst1=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|border|thumb|Multiple routes using the same access nodes to long-distance road network.]]

Long-distance travel usually involves driving along a subset of the [[road network]] such as [[Controlled-access highway|freeways]] instead of e.g. urban roads. This sub-network can only be entered by using sparsely distributed access node[[Node (computer science)|snodes]]. 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 ==

Line 32 ⟶ 33:

* 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|lastlast1=Bast|firstfirst1=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|lastlast1=Arz|firstfirst1=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>.

=== Geometrical approach using grids===

Line 56 ⟶ 57:

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===

Line 69 ⟶ 70:

'''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]]{{dn|date=August 2019}} (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?'''

Line 80 ⟶ 81:

* [[Hub labels]]

* [[Bidirectional search]]

* [[Highway dimension]]

==References==