Contraction Hierarchies with Turn Restrictions
For single-pair shortest path problems, Contraction Hierarchies (CH) provide very small query times together with a very low space overhead for the graph. During a preprocessing every node is assigned a distinct rank. Queries are performed using an altern
- PDF / 293,242 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 281 Views
1 Introduction Modern digital road maps do not only model the bare geometry of the road network but also other real-life aspects like speed limits or turn restrictions. Algorithms solving the single source-single destination on such maps can therefore deliver a more precise estimation of driving distance and time of routes chosen by real drivers by taking into account such information. The demand for a concise estimation arises in many real world applications like vehicle routing, where tight time windows for delivery exist.
2 Related Work Turn restrictions are normally modelled as a set forbidden combination of a pair of edges (TR) and can be approached in two different ways (see e.g., [4] in [5]): • Adaption of the graph: Nodes with TR are split into complex nodes representing only allowed turns, thus strongly increasing both the memory needed for the storage of the graph and the number of iterations performed by the algorithm. • Adaption of the algorithm: The originally node-oriented Dijkstra algorithm can be switched to edge-orientation by iterating over edges. This allows for an easy C. Nowak (B) · F. Hahne · K. Ambrosi Institut für Betriebswirtschaft und Wirtschaftsinformatik, Universität Hildesheim, Marienburger Platz 22, 31141 Hildesheim, Germany e-mail: [email protected] F. Hahne e-mail: [email protected] K. Ambrosi e-mail: [email protected] S. Helber et al. (eds.), Operations Research Proceedings 2012, Operations Research Proceedings, DOI: 10.1007/978-3-319-00795-3_85, © Springer International Publishing Switzerland 2014
569
570
C. Nowak et al.
incorporation of TR into the algorithm. Yet it also leads to a much larger number of iterations (depending on the average node degree in the underlying graph) when compared to iterating over nodes. We present an enhancement of Dijkstra’s algorithm (Dijkstra with adaptive TR), which is TR-aware, iterates over nodes and adapts an edge-oriented point-of-view only when needed. As worst case, the number of iterations is equal to that needed by the edge-iterating version, but in many real-data cases it is smaller. Our enhancement is also applicable when techniques like A* or Contraction Hierarchies (CH) are used. Geisberger and Vetter [2] presents an edge-based CHalgorithm accounting for turn-costs, modelling soft turn restrictions to which we will refer in the benchmarks in Sect. 4.
3 Dijkstra’s Algorithm with Adaptive Turn Restrictions 3.1 Approach and Pseudocode The existence of TR may cause nodes to appear more than once in the shortest path, even with all edge costs greater zero. See e.g., Fig. 1, where the shortest path from node a to node i is a, e, f, g, h, d, g, f, i (note: no U-turns are allowed). In other words: shortest paths may contain cycles and sub-paths do not have to be shortest paths by themselves. In a TR-free graph, a node-oriented Dijkstra’s algorithm maintains two sets: • Reached: A set of reached nodes, queued to be expanded. Here the length of the best shortest path so far serves as (upper) bound for furthe
Data Loading...
