Contraction Hierarchies with Turn Restrictions

Curt Nowak (), Felix Hahne () and Klaus Ambrosi ()
Additional contact information
Curt Nowak: Universität Hildesheim
Felix Hahne: Universität Hildesheim
Klaus Ambrosi: Universität Hildesheim

A chapter in Operations Research Proceedings 2012, 2014, pp 569-575 from Springer

Abstract: Abstract 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 alternating bidirectional Dijkstra search that only expands towards higher ranked nodes. In its original version CH do not take turn restrictions (TR) into account. This may lead to illegal routes whose length may considerably differ from legal ones. Incorporating TR widens the scope of application for CH, e.g., car navigation or precise traffic simulations. A way to consider TR is to switch from a node-based to an edge-based search, implicitly allowing nodes to be settled more than once. Compared to the original CH query this increases the size of the search trees substantially. A more space efficient adaptive algorithm combining node-based with on-demand edge-based search is presented, where nodes may only be settled multiply if the encountered path towards them traverses a (possible) TR. The number of iterations in this approach is at most as high as the edge-base search. Depending on the number of TR and the average node degree in the graph our approach outperforms the edge-based search by far.

Keywords: Contraction Hierarchies (CH); Turn Restrictions; Single-pair Shortest Path Problem; Average Node Degree; Higher Ranked Nodes (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-00795-3_85

Ordering information: This item can be ordered from
http://www.springer.com/9783319007953

DOI: 10.1007/978-3-319-00795-3_85

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().