Transit node routing: Difference between revisions

Revision as of 15:22, 28 June 2019

Revision as of 16:11, 28 June 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>{{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>.

__TOC__

== Intuition ==

Long-distance travel usually involves driving along a specialised subset of the [[road network]] such as highways. 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.

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.

Line 28:

* How should local queries be handled?

=== Geometrical approach using grids<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>===

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

'''How are access-nodes selected?'''

Line 45:

'''How should local queries be handled?'''

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

=== Using Contraction Hierarchies ===

'''How are transit-nodes selected?'''

By definition, a [[Contraction hierarchies|contraction hierarchy]] movemoves important nodes (i.e. nodes that are part of many shortest paths) to the top of the hierarchy. A set of transit-nodes therefore can be selected as the <math>k</math>highest nodes of the contraction hierarchy.

'''How are access-nodes selected?'''

Forward access-nodes of a node <math>n</math>can be found by running the upward-phasesearch of the contraction hierarchy starting at <math>n</math>. During the upward-phasesearch, 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>n</math>. Backward access-nodes can be found analogously.

'''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]] (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?'''

Local queries use the regular [[Contraction hierarchies#Querying|query algorithm]] of the contraction hierarchy.<br />

== See also ==

<br />

==References==