Content deleted Content added
No edit summary |
No edit summary |
||
Line 8:
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.
== General
# Transit node routing starts with a selection of transit nodes <math>T \subseteq V</math> as a subset of all nodes <math>V</math> of the road network.
Line 15:
# A distance between two nodes can now be calculated as <math>d(s,t) = \min_{u \in \overrightarrow{A}(s), v \in \overleftarrow{A}(t)}d_A(s,u) + D_T(u,v) + d_A(v,t)</math>
=== Locality
Short routes between close start and target locations may not require any transit nodes. In this case, the above framework leads to incorrect distances because it forces routes to visit at least one transit node.
To prevent this kind of problem, a '''locality filter''' can be used. For given start and target locations, the locality filter decides, if transit node routing should be applied or if a fallback-routine should be used (local query).
== Concrete
Transit node routing is not an algorithm but merely a framework for speeding up route planning. The general framework leaves open a few questions that need to be answered to implement it:
Line 47:
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
'''How are transit-nodes selected?'''
Line 62:
'''How should local queries be handled?'''
Local queries use the regular [[Contraction hierarchies#Querying|query algorithm]] of the contraction hierarchy.
== See also ==
* [[Shortest path problem]]
* [[Hub labels]]
* [[Bidirectional search]]
==References==
| |||