Document Open Access Logo

Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies

Authors Valentin Buchhold, Peter Sanders, Dorothea Wagner

PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.27.pdf
  • Filesize: 462 kB
  • 15 pages

Document Identifiers

Author Details

Valentin Buchhold
  • Karlsruhe Institute of Technology, Germany
Peter Sanders
  • Karlsruhe Institute of Technology, Germany
Dorothea Wagner
  • Karlsruhe Institute of Technology, Germany

Cite As Get BibTex

Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SEA.2018.27

Abstract

Given an urban road network and a set of origin-destination (OD) pairs, the traffic assignment problem asks for the traffic flow on each road segment. A common solution employs a feasible-direction method, where the direction-finding step requires many shortest-path computations. In this paper, we significantly accelerate the computation of flow patterns, enabling interactive transportation and urban planning applications. We achieve this by revisiting and carefully engineering known speedup techniques for shortest paths, and combining them with customizable contraction hierarchies. In particular, our accelerated elimination tree search is more than an order of magnitude faster for local queries than the original algorithm, and our centralized search speeds up batched point-to-point shortest paths by a factor of up to 6. These optimizations are independent of traffic assignment and can be generally used for (batched) point-to-point queries. In contrast to prior work, our evaluation uses real-world data for all parts of the problem. On a metropolitan area encompassing more than 2.7 million inhabitants, we reduce the flow-pattern computation for a typical two-hour morning peak from 76.5 to 10.5 seconds on one core, and 4.3 seconds on four cores. This represents a speedup of 18 over the state of the art, and three orders of magnitude over the Dijkstra-based baseline.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
Keywords
  • traffic assignment
  • equilibrium flow pattern
  • customizable contraction hierarchies
  • batched shortest paths

Metrics

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

References

  1. Frédéric Babonneau and Jean-Philippe Vial. Test instances for the traffic assignment problem. Technical report, Ordecsys, 2008. Google Scholar
  2. 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 Algorithm Engineering: Selected Results and Surveys, pages 19-80. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49487-6_2.
  3. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theoretical Computer Science, 645:112-127, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.07.003.
  4. Reinhard Bauer and Daniel Delling. SHARC: Fast and robust unidirectional routing. ACM Journal of Experimental Algorithmics, 14:2.4:1-2.4:29, 2009. URL: http://dx.doi.org/10.1145/1498698.1537599.
  5. Martin Beckmann, C. Bart McGuire, and Christopher B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956. Google Scholar
  6. M. Bruynooghe, A. Gilbert, and M. Sakarovich. Une méthode d'affectation du traffic. In Proceedings of the 4th International Symposium on the Theory of Road Traffic Flow, 1968. Google Scholar
  7. Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing, 73(7):940-952, 2013. URL: http://dx.doi.org/10.1016/j.jpdc.2012.02.007.
  8. 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: http://dx.doi.org/10.1287/trsc.2014.0579.
  9. Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Faster batched shortest paths in road networks. In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11), pages 52-63, 2011. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2011.52.
  10. Daniel Delling and Renato F. Werneck. Customizable point-of-interest queries in road networks. IEEE Transactions on Knowledge and Data Engineering, 27(3):686-698, 2015. URL: http://dx.doi.org/10.1109/TKDE.2014.2345386.
  11. 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
  12. 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: http://dx.doi.org/10.1145/2886843.
  13. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  14. Alexandros Efentakis and Dieter Pfoser. Optimizing landmark-based routing and preprocessing. In Proceedings of the 6th ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS'13), pages 25-30, 2013. URL: http://dx.doi.org/10.1145/2533828.2533838.
  15. Alexandros Efentakis and Dieter Pfoser. GRASP. Extending graph separators for the single-source shortest-path problem. In Proceedings of the 22th Annual European Symposium on Algorithms (ESA'14), pages 358-370, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_30.
  16. Alexandros Efentakis, Dieter Pfoser, and Yannis Vassiliou. SALT. A unified framework for all shortest-path query variants on road networks. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), pages 298-311, 2015. URL: http://dx.doi.org/10.1007/978-3-319-20086-6_23.
  17. Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2):95-110, 1956. URL: http://dx.doi.org/10.1002/nav.3800030109.
  18. 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: http://dx.doi.org/10.1287/trsc.1110.0401.
  19. Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345-363, 1973. URL: http://dx.doi.org/10.1137/0710032.
  20. Moritz Hilger, Ekkehard Köhler, Rolf H. Möhring, and Heiko Schilling. Fast point-to-point shortest path computations with arc-flags. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, pages 41-72. American Mathematical Society, 2009. Google Scholar
  21. Donald B. Johnson. Priority queues with update and finding minimum spanning trees. Information Processing Letters, 4(3):53-57, 1975. URL: http://dx.doi.org/10.1016/0020-0190(75)90001-0.
  22. Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner. Computing many-to-many shortest paths using highway hierarchies. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07), pages 36-45, 2007. URL: http://dx.doi.org/10.1137/1.9781611972870.4.
  23. Donald E. Knuth. The Art of Computer Programming: Sorting and Searching. Addison-Wesley, 1998. Google Scholar
  24. Daniel Kusswurm. Modern X86 Assembly Language Programming: 32-bit, 64-bit, SSE, and AVX. Apress, 2014. Google Scholar
  25. Larry J. LeBlanc, Edward K. Morlok, and William P. Pierskalla. An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Research, 9(5):309-318, 1975. URL: http://dx.doi.org/10.1016/0041-1647(75)90030-1.
  26. Dennis Luxen and Peter Sanders. Hierarchy decomposition for faster user equilibria on road networks. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), pages 242-253, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20662-7_21.
  27. Nicolai Mallig, Martin Kagerbauer, and Peter Vortisch. mobitopp - A modular agent-based travel demand modelling framework. In Proceedings of the 2nd International Workshop on Agent-based Mobility, Traffic and Transportation Models, Methodologies and Applications (ABMTRANS'13), pages 854-859, 2013. URL: http://dx.doi.org/10.1016/j.procs.2013.06.114.
  28. Nicolai Mallig and Peter Vortisch. Modeling car passenger trips in mobitopp. In Proceedings of the 4nd International Workshop on Agent-based Mobility, Traffic and Transportation Models, Methodologies and Applications (ABMTRANS'15), pages 938-943, 2015. URL: http://dx.doi.org/10.1016/j.procs.2015.05.169.
  29. Kurt Mehlhorn and Peter Sanders. Algorithms and Data Structures: The Basic Toolbox. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-77978-0.
  30. Enock T. Mtoi and Ren Moses. Calibration and evaluation of link congestion functions: Applying intrinsic sensitivity of link speed as a practical consideration to heterogeneous facility types within urban network. Journal of Transportation Technologies, 4:141-149, 2014. URL: http://dx.doi.org/10.4236/jtts.2014.42014.
  31. John D. Murchland. Road traffic distribution in equilibrium. In Proceedings of Mathematical Methods in the Economic Sciences, 1969. Google Scholar
  32. Michael Patriksson. The Traffic Assignment Problem: Models and Methods. Topics in Transportation. VSP, 1994. Google Scholar
  33. Srinivas Peeta and Athanasios K. Ziliaskopoulos. Foundations of dynamic traffic assignment: The past, the present and the future. Networks and Spatial Economics, 1(3-4):233-265, 2001. URL: http://dx.doi.org/10.1023/A:1012827724856.
  34. Peter Sanders and Dominik Schultes. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05), pages 568-579, 2005. URL: http://dx.doi.org/10.1007/11561071_51.
  35. Aaron Schild and Christian Sommer. On balanced separators in road networks. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), pages 286-297, 2015. URL: http://dx.doi.org/10.1007/978-3-319-20086-6_22.
  36. Johannes Schlaich, Udo Heidl, and R. Pohlner. Verkehrsmodellierung für die Region Stuttgart: Schlussbericht. unpublished, 2011. Google Scholar
  37. Yosef Sheffi. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice Hall, 1985. Google Scholar
  38. Verband Region Stuttgart. Mobilität und Verkehr in der Region Stuttgart 2009/2010: Regionale Haushaltsbefragung zum Verkehrsverhalten. Schriftenreihe Verband Region Stuttgart, 29:1-138, 2011. Google Scholar
  39. John G. Wardrop. Some theoretical aspects of road traffic research. In Proceedings of the Institution of Civil Engineers, pages 325-362, 1952. URL: http://dx.doi.org/10.1680/ipeds.1952.11259.
  40. Hiroki Yanagisawa. A multi-source label-correcting algorithm for the all-pairs shortest paths problem. In 24th IEEE International Symposium on Parallel and Distributed Processing (IPDPS'10), pages 1-10, 2010. URL: http://dx.doi.org/10.1109/IPDPS.2010.5470362.
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