Document Open Access Logo

Customizable Contraction Hierarchies with Turn Costs

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

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.9.pdf
  • Filesize: 414 kB
  • 15 pages

Document Identifiers

Author Details

Valentin Buchhold
  • Karlsruhe Institute of Technology (KIT), Germany
Dorothea Wagner
  • Karlsruhe Institute of Technology (KIT), Germany
Tim Zeitz
  • Karlsruhe Institute of Technology (KIT), Germany
Michael Zündorf
  • Karlsruhe Institute of Technology (KIT), Germany

Acknowledgements

We thank Peter Vortisch for providing the Stuttgart instance. We are also grateful to Transport for London (TfL) for permitting us to use their data, and to PTV AG for providing the London data. Further information about the London instance is provided by Tony Dichev (tonydichev@tfl.gov.uk).

Cite As Get BibTex

Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf. Customizable Contraction Hierarchies with Turn Costs. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/OASIcs.ATMOS.2020.9

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • Turn costs
  • realistic road networks
  • customizable contraction hierarchies
  • route planning
  • shortest paths

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Panos M. Pardalos and Steffen Rebennack, editors, Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 230-241. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20662-7_20.
  2. Julian Arz, Dennis Luxen, and Peter Sanders. Transit node routing reconsidered. In Vincenzo Bonifaci, Camil Demetrescu, and Alberto Marchetti-Spaccamela, editors, Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 55-66. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_7.
  3. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
  4. Holger Bast, Stefan Funke, Peter Sanders, and Dominik Schultes. Fast routing in road networks with transit nodes. Science, 316(5824):566, 2007. URL: https://doi.org/10.1126/science.1137521.
  5. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theoretical Computer Science, 645:112-127, 2016. URL: https://doi.org/10.1016/j.tcs.2016.07.003.
  6. Joschka Bischoff and Michal Maciejewski. Simulation of city-wide replacement of private cars with autonomous taxis in Berlin. In Ansar-Ul-Haque Yasar and Jesús Fraile-Ardanuy, editors, Proceedings of the 7th International Conference on Ambient Systems, Networks and Technologies (ANT'16), volume 83 of Procedia Computer Science, pages 237-244. Elsevier, 2016. URL: https://doi.org/10.1016/j.procs.2016.04.121.
  7. Joschka Bischoff, Michal Maciejewski, and Kai Nagel. City-wide shared taxis: A simulation study in berlin. In 20th IEEE International Conference on Intelligent Transportation Systems (ITSC'17), pages 275-280. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/ITSC.2017.8317926.
  8. Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Real-time traffic assignment using engineered customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 24(2):2.4:1-2.4:28, 2019. URL: https://doi.org/10.1145/3362693.
  9. Tom Caldwell. On finding minimum routes in a network with turn penalties. Communications of the ACM, 4(2):107-108, 1961. URL: https://doi.org/10.1145/366105.366184.
  10. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning. In Panos M. Pardalos and Steffen Rebennack, editors, Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 376-387. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20662-7_32.
  11. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning in road networks. Transportation Science, 51(2):566-591, 2017. URL: https://doi.org/10.1287/trsc.2014.0579.
  12. Daniel Delling and Renato F. Werneck. Faster customization of road networks. In Vincenzo Bonifaci, Camil Demetrescu, and Alberto Marchetti-Spaccamela, editors, Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 30-42. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_5.
  13. Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book. American Mathematical Society, 2009. Google Scholar
  14. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 21(1):1.5:1-1.5:49, 2016. URL: https://doi.org/10.1145/2886843.
  15. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  16. Transportation Networks for Research Core Team. Transportation networks for research. URL: https://github.com/bstabler/TransportationNetworks.
  17. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388-404, 2012. URL: https://doi.org/10.1287/trsc.1110.0401.
  18. Robert Geisberger and Christian Vetter. Efficient routing in road networks with turn costs. In Panos M. Pardalos and Steffen Rebennack, editors, Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 100-111. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20662-7_9.
  19. Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345-363, 1973. URL: https://doi.org/10.1137/0710032.
  20. Andrew V. Goldberg and Chris Harrelson. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 156-165. SIAM, 2005. Google Scholar
  21. Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl, and Dorothea Wagner. Faster and better nested dissection orders for customizable contraction hierarchies. Algorithms, 12(9):1-20, 2019. URL: https://doi.org/10.3390/a12090196.
  22. Ron Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04). SIAM, 2004. Google Scholar
  23. Moritz Hilger, Ekkehard Köhler, Rolf H. Möhring, and Heiko Schilling. Fast point-to-point shortest path computations with arc-flags. In Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book, pages 41-72. American Mathematical Society, 2009. Google Scholar
  24. Ulrich Lauther. An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags. In Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book, pages 19-39. American Mathematical Society, 2009. Google Scholar
  25. Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-25209-0.
  26. Aaron Schild and Christian Sommer. On balanced separators in road networks. In Evripidis Bampis, editor, Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), volume 9125 of Lecture Notes in Computer Science, pages 286-297. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_22.
  27. Arne Schneck and Klaus Nökel. Accelerating traffic assignment with customizable contraction hierarchies. Transportation Research Record, 2674(1):188-196, 2020. URL: https://doi.org/10.1177/0361198119898455.
  28. Stephan Winter. Modeling costs of turns in route planning. GeoInformatica, 6(4):345-361, 2002. URL: https://doi.org/10.1023/A:1020853410145.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact