Transit node routing: Difference between revisions

Revision as of 19:17, 18 August 2019

Revision as of 18:31, 9 September 2019

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|url=httphttps://dx.doi.org/10.1126/science.1137521|journal=Science|volume=316|issue=5824|pages=566–566|doi=10.1126/science.1137521|issn=0036-8075}}</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|title=Dynamic Highway-Node Routing|url=httphttps://dx.doi.org/10.1007/978-3-540-72845-0_6|work=Experimental Algorithms|pages=66–79|publisher=Springer Berlin Heidelberg|isbn=9783540728443|access-date=2019-07-16|last2=Sanders|first2=Peter}}</ref>

__TOC__

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|url=httphttps://dx.doi.org/10.1137/1.9781611972870.5|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|access-date=2019-06-28|last2=Funke|first2=Stefan|last3=Matijevic|first3=Domagoj|last4=Sanders|first4=Peter|last5=Schultes|first5=Dominik}}</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|url=httphttps://dx.doi.org/10.1007/978-3-642-38527-8_7|work=Experimental Algorithms|pages=55–66|publisher=Springer Berlin Heidelberg|isbn=9783642385261|access-date=2019-06-28|last2=Luxen|first2=Dennis|last3=Sanders|first3=Peter|arxiv=1302.5611}}</ref>.

=== Geometrical approach using grids===