Document Open Access Logo

Arc-Flags Meet Trip-Based Public Transit Routing

Authors Ernestine Großmann , Jonas Sauer , Christian Schulz , Patrick Steil

PDF
Thumbnail PDF

File

LIPIcs.SEA.2023.16.pdf
  • Filesize: 0.75 MB
  • 18 pages

Document Identifiers

Author Details

Ernestine Großmann
  • Universität Heidelberg, Germany
Jonas Sauer
  • Karlsruhe Institute of Technology, Germany
Christian Schulz
  • Universität Heidelberg, Germany
Patrick Steil
  • Universität Heidelberg, Germany

Funding

We acknowledge support by DFG grants SCHU 2567/3-1 and WA 654/23-2.

Acknowledgements

We want to thank Dr. Patrick Brosi for providing us with the Germany dataset and Sascha Witt for providing us with the source code for TB-CST.

Cite As Get BibTex

Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil. Arc-Flags Meet Trip-Based Public Transit Routing. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SEA.2023.16

Abstract

We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compared to previous attempts to apply Arc-Flags to public transit networks, which saw limited success, our approach uses stronger pruning rules to reduce the search space. Our experiments show that Arc-Flag TB achieves a speedup of up to two orders of magnitude over TB, offering query times of less than a millisecond even on large countrywide networks. Compared to the state-of-the-art speedup technique Trip-Based Public Transit Routing Using Condensed Search Trees (TB-CST), our algorithm achieves similar query times but requires significantly less additional memory. Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. In contrast, Arc-Flag TB offers a tradeoff between query performance and memory usage due to the fact that the number of regions in the network partition required by our algorithm is a configurable parameter. We also identify a previously undiscovered issue in the transfer precomputation of TB, which causes both TB-CST and Arc-Flag TB to answer some queries incorrectly. We provide discussion on how to resolve this issue in the future. Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • Public transit routing
  • graph algorithms
  • algorithm engineering

Metrics

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

Supplementary Materials

References

  1. Prateek Agarwal and Tarun Rambha. Scalable Algorithms for Bicriterion Trip-Based Transit Routing. Technical report, Department of Civil Engineering, Indian Institute of Science, 2022. URL: https://arxiv.org/abs/2111.06654.
  2. Hannah Bast. Car or Public Transport - Two Worlds. In Efficient Algorithms, volume 5760 of Lecture Notes in Computer Science (LNCS), pages 355-367. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03456-5_24.
  3. Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. Fast Routing in Very Large Public Transportation Networks using Transfer Patterns. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA'10), volume 6346 of Lecture Notes in Computer Science (LNCS), pages 290-301. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15775-2_25.
  4. Hannah Bast, Daniel Delling, Andrew 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, volume 9220 of Lecture Notes in Computer Science (LNCS), pages 19-80. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
  5. Hannah Bast, Matthias Hertel, and Sabine Storandt. Scalable Transfer Patterns. In Proc. 18th Workshop on Algorithm Engineering and Experiments (ALENEX'16), pages 15-29. Society for Industrial and Applied Mathematics (SIAM), 2016. URL: https://doi.org/10.1137/1.9781611974317.2.
  6. Reinhard Bauer and Daniel Delling. SHARC: Fast and Robust Unidirectional Routing. Journal of Experimental Algorithmics (JEA), 14:4.1-4.29, 2009. URL: https://doi.org/10.1145/1498698.1537599.
  7. Reinhard Bauer, Daniel Delling, and Dorothea Wagner. Experimental Study of Speed Up Techniques for Timetable Information Systems. Networks, 57:38-52, 2011. URL: https://doi.org/10.1002/net.20382.
  8. Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.14.
  9. Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. Technical report, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2023. URL: https://arxiv.org/abs/1906.04832.
  10. Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected. In Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'09), volume 12 of OpenAccess Series in Informatics (OASIcs), pages 2:1-2:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. URL: https://doi.org/10.4230/OASIcs.ATMOS.2009.2148.
  11. Gerth S. Brodal and Riko Jacob. Time-dependent Networks as Models to Achieve Fast Exact Time-table Queries. In Proceedings of the 3rd Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'03), volume 92, pages 3-15. Elsevier, 2004. URL: https://doi.org/10.1016/j.entcs.2003.12.019.
  12. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and Distance Queries via 2-Hop Labels. SIAM Journal on Computing (SICOMP), 32(5):1338-1355, 2003. URL: https://doi.org/10.1137/S0097539702403098.
  13. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. Public Transit Labeling. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), volume 9125 of Lecture Notes in Computer Science (LNCS), pages 273-285. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_21.
  14. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zündorf. Faster Transit Routing by Hyper Partitioning. In Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'17), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.8.
  15. Daniel Delling, Thomas Pajor, and Dorothea Wagner. Engineering Time-Expanded Graphs for Faster Timetable Information. In Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems, volume 5868 of Lecture Notes in Computer Science (LNCS), pages 182-206. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-05465-5_7.
  16. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. Transportation Science, 49:591-604, 2015. URL: https://doi.org/10.1287/trsc.2014.0534.
  17. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1:269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  18. Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee. Multi-criteria Shortest Paths in Time-Dependent Train Networks. In Proceedings of the 7th International Workshop on Experimental and Efficient Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science (LNCS), pages 347-361. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-68552-4_26.
  19. Pierre Hansen. Bicriterion Path Problems. In Multiple Criteria Decision Making Theory and Application, volume 177 of Lecture Notes in Economics and Mathematical Systems, pages 109-127. Springer, 1980. URL: https://doi.org/10.1007/978-3-642-48782-8_9.
  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, volume 74 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 41-72. American Mathematical Society (AMS), 2009. URL: https://doi.org/10.1090/dimacs/074/03.
  21. Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm. Partitioning Graphs to Speed Up Dijkstra’s Algorithm. Journal of Experimental Algorithmics (JEA), 11:2.8:1-2.8:29, 2006. URL: https://doi.org/10.1007/11427186_18.
  22. Matthias Müller-Hannemann and Mathias Schnee. Finding All Attractive Train Connections by Multi-Criteria Pareto Search. In Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science (LNCS), pages 246-263. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74247-0_13.
  23. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos D. Zaroliagis. Efficient Models for Timetable Information in Public Transportation Systems. Journal of Experimental Algorithmics (JEA), 12:2.4:1-2.4:39, 2008. URL: https://doi.org/10.1145/1227161.1227166.
  24. Peter Sanders and Christian Schulz. Think Locally, Act Globally: Highly Balanced Graph Partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science (LNCS), pages 164-175. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_16.
  25. Sascha Witt. Trip-Based Public Transit Routing. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA'15), volume 9294 of Lecture Notes in Computer Science (LNCS), pages 1025-1036. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_85.
  26. Sascha Witt. Trip-Based Public Transit Routing Using Condensed Search Trees. In Proc. 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'16), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 10:1-10:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/OASIcs.ATMOS.2016.10.
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