Transit node routing: Difference between revisions

Revision as of 02:32, 13 April 2020

Revision as of 01:33, 12 October 2020

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|last=Bast|first=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}}</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|last=Schultes|first=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)|s]]. 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.

Line 32:

* 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|last=Bast|first=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|last=Arz|first=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}}</ref>.

=== Geometrical approach using grids===

Line 56:

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