|
== 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 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.
* How should local queries be handled?
===The Geometricalfollowing approachexample implementations of this framework answer these questions using gridsdifferent underlying methods such as grouping nodes in cells of an overlay [[Grid (spatial index)|grid]]<ref>{{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>{{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===
In a [[Grid (spatial index)|grid]]-based approach, the [[Minimum bounding box|bounding]] square of all nodes is equally subdivided into square cells.
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.
=== Using contraction hierarchies===
=== Using contraction hierarchies<ref>{{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>===
'''How are transit-nodes selected?'''
'''How are access-nodes selected?'''
Forward access-nodes of a node <math>nv</math> can be found by running the upward-search of the contraction hierarchy starting at <math>nv</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>nv</math>. Backward access-nodes can be found analogously.
'''Which locality filter should be used?'''
| 