Content deleted Content added
No edit summary |
No edit summary |
||
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=http://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" />.
__TOC__
Line 30 ⟶ 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=http://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=http://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}}</ref>.
=== Geometrical approach using grids===
| |||