Document Open Access Logo

Trip-Based Public Transit Routing Using Condensed Search Trees

Author Sascha Witt

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.10.pdf
  • Filesize: 410 kB
  • 12 pages

Document Identifiers

Author Details

Sascha Witt

Cite AsGet BibTex

Sascha Witt. Trip-Based Public Transit Routing Using Condensed Search Trees. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/OASIcs.ATMOS.2016.10

Abstract

We study the problem of planning Pareto-optimal journeys in public transit networks. Most existing algorithms and speed-up techniques work by computing subjourneys to intermediary stops until the destination is reached. In contrast, the trip-based model focuses on trips and transfers between them, constructing journeys as a sequence of trips. In this paper, we develop a speed-up technique for this model inspired by principles behind existing state-of-the-art speed-up techniques, Transfer Patterns and Hub Labelling. The resulting algorithm allows us to compute Pareto-optimal (with respect to arrival time and number of transfers) 24-hour profiles on very large real-world networks in less than half a millisecond. Compared to the current state of the art for bicriteria queries on public transit networks, this is up to two orders of magnitude faster, while increasing preprocessing overhead by at most one order of magnitude.
Keywords
  • Public Transit
  • Routing
  • Public Transport
  • Route Planning

Metrics

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

References

  1. 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 European Symposium on Algorithms (ESA), volume 6346, pages 290-301, 2010. Google Scholar
  2. 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. ArXiv e-prints, April 2015. URL: http://arxiv.org/abs/1504.05140.
  3. Hannah Bast, Matthias Hertel, and Sabine Storandt. Scalable Transfer Patterns. In Algorithm Engineering and Experiments (ALENEX), pages 15-29, 2016. URL: http://dx.doi.org/10.1137/1.9781611974317.2.
  4. Hannah Bast and Sabine Storandt. Frequency-Based Search for Public Transit. In ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 13-22. ACM Press, November 2014. URL: http://dx.doi.org/10.1145/2666310.2666405.
  5. Annabell Berger, Martin Grimmer, and Matthias Müller-Hannemann. Fully Dynamic Speed-Up Techniques for Multi-criteria Shortest Path Searches in Time-Dependent Networks. In Symposium on Experimental Algorithms (SEA), pages 35-46. Springer Berlin Heidelberg, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13193-6_4.
  6. J.C. Bermond, M.C. Heydemann, and D. Sotteau. Line graphs of hypergraphs I. Discrete Mathematics, 18(3):235-241, 1977. URL: http://dx.doi.org/10.1016/0012-365X(77)90127-3.
  7. Ulrik Brandes. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, 25(2):163-177, 2001. Google Scholar
  8. Ulrik Brandes and Christian Pich. Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos, 17(07):2303-2318, 2007. Google Scholar
  9. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5):1338-1355, 2003. Google Scholar
  10. Rene De La Briandais. File Searching Using Variable Length Keys. In Western Joint Computer Conference 1959, IRE-AIEE-ACM '59 (Western), pages 295-298, New York, NY, USA, 1959. ACM. URL: http://dx.doi.org/10.1145/1457838.1457895.
  11. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F Werneck. Computing Multimodal Journeys in Practice. In Experimental Algorithms, pages 260-271. Springer, 2013. Google Scholar
  12. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. Public Transit Labeling. In Experimental Algorithms, volume 9125 of Lecture Notes in Computer Science (LNCS), pages 273-285. Springer, 2015. Google Scholar
  13. Daniel Delling, Bastian Katz, and Thomas Pajor. Parallel computation of best connections in public transportation networks. Journal of Experimental Algorithmics (JEA), 17, 2012. URL: http://dx.doi.org/10.1145/2133803.2345678.
  14. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. Transportation Science, 49(3):591-604, 2015. URL: http://dx.doi.org/10.1287/trsc.2014.0534.
  15. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly Simple and Fast Transit Routing. In Experimental Algorithms, volume 7933 of Lecture Notes in Computer Science (LNCS), pages 43-54. Springer, Heidelberg, 2013. Google Scholar
  16. Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee. Multi-criteria Shortest Paths in Time-Dependent Train Networks. In Workshop on Experimental Algorithms (WEA), pages 347-361. Springer Berlin Heidelberg, 2008. URL: http://dx.doi.org/10.1007/978-3-540-68552-4_26.
  17. Alexandros Efentakis. Scalable Public Transportation Queries on the Database. In International Conference on Extending Databse Technology (EDBT), pages 527-538. OpenProceedings.org, 2016. URL: http://dx.doi.org/10.5441/002/edbt.2016.50.
  18. Marco Farina and Paolo Amato. A Fuzzy Definition of "Optimality" for Many-Criteria Optimization Problems. Systems, Man and Cybernetics, Part A: Systems and Humans, 34(3):315-326, 2004. Google Scholar
  19. Linton C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry, 40(1):35-41, 1977. Google Scholar
  20. Robert Geisberger. Contraction of Timetable Networks with Realistic Transfers. In Experimental Algorithms, volume 6049 of Lecture Notes in Computer Science (LNCS), pages 71-82. Springer, Heidelberg, 2010. Google Scholar
  21. Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm. Partitioning Graphs to Speedup Dijkstra’s Algorithm. J. Exp. Algorithmics, 11, February 2007. URL: http://dx.doi.org/10.1145/1187436.1216585.
  22. Matthias Müller-Hannemann and Karsten Weihe. On the cardinality of the Pareto set in bicriteria shortest path problems. Annals of Operations Research, 147(1):269-286, 2006. Google Scholar
  23. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Efficient Models for Timetable Information in Public Transportation Systems. Journal of Experimental Algorithmics, 12:1, 2008. URL: http://dx.doi.org/10.1145/1227161.1227166.
  24. Ben Strasser and Dorothea Wagner. Connection Scan Accelerated. In Algorithm Engineering and Experiments (ALENEX), 2014. URL: http://dx.doi.org/10.1137/1.9781611973198.12.
  25. Sibo Wang, Wenqing Lin, Yi Yang, Xiaokui Xiao, and Shuigeng Zhou. Efficient Route Planning on Public Transportation Networks: A Labelling Approach. In ACM SIGMOD International Conference on Management of Data, SIGMOD '15, pages 967-982, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2723372.2749456.
  26. Sascha Witt. Trip-Based Public Transit Routing. In European Symposium on Algorithms (ESA), pages 1025-1036. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_85.
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 Imprint Privacy Contact