License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2020.9
URN: urn:nbn:de:0030-drops-131453
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13145/
Go to the corresponding OASIcs Volume Portal

Buchhold, Valentin ; Wagner, Dorothea ; Zeitz, Tim ; Zündorf, Michael

Customizable Contraction Hierarchies with Turn Costs

pdf-format:
OASIcs-ATMOS-2020-9.pdf (0.4 MB)

Abstract

We incorporate turn restrictions and turn costs into the route planning algorithm customizable contraction hierarchies (CCH). There are two common ways to represent turn costs and restrictions. The edge-based model expands the network so that road segments become vertices and allowed turns become edges. The compact model keeps intersections as vertices, but associates a turn table with each vertex. Although CCH can be used as is on the edge-based model, the performance of preprocessing and customization is severely affected. While the expanded network is only three times larger, both preprocessing and customization time increase by up to an order of magnitude. In this work, we carefully engineer CCH to exploit different properties of the expanded graph. We reduce the increase in customization time from up to an order of magnitude to a factor of about 3. The increase in preprocessing time is reduced even further. Moreover, we present a CCH variant that works on the compact model, and show that it performs worse than the variant on the edge-based model. Surprisingly, the variant on the edge-based model even uses less space than the one on the compact model, although the compact model was developed to keep the space requirement low.

BibTeX - Entry

@InProceedings{buchhold_et_al:OASIcs:2020:13145,
  author =	{Valentin Buchhold and Dorothea Wagner and Tim Zeitz and Michael Z{\"u}ndorf},
  title =	{{Customizable Contraction Hierarchies with Turn Costs}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{9:1--9:15},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Dennis Huisman and Christos D. Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13145},
  URN =		{urn:nbn:de:0030-drops-131453},
  doi =		{10.4230/OASIcs.ATMOS.2020.9},
  annote =	{Keywords: Turn costs, realistic road networks, customizable contraction hierarchies, route planning, shortest paths}
}

Keywords: Turn costs, realistic road networks, customizable contraction hierarchies, route planning, shortest paths
Collection: 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Issue Date: 2020
Date of publication: 10.11.2020
Supplementary Material: We publish our extensions to the projects RoutingKit and InertialFlowCutter as pull requests on Github: https://github.com/RoutingKit/RoutingKit/pull/77 and https://github.com/kit-algo/InertialFlowCutter/pull/6.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI