Document Open Access Logo

Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm

Authors Vassilissa Lehoux , Christelle Loiodice

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.3.pdf
  • Filesize: 450 kB
  • 12 pages

Document Identifiers

Author Details

Vassilissa Lehoux
  • NAVER LABS Europe, Meylan, France
Christelle Loiodice
  • NAVER LABS Europe, Meylan, France

Cite AsGet BibTex

Vassilissa Lehoux and Christelle Loiodice. Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.3

Abstract

We propose an additional preprocessing step for the Trip-Based Public Transit Routing algorithm, an exact state-of-the art algorithm for bi-criteria min cost path problems in public transit networks. This additional step reduces significantly the preprocessing time, while preserving the correctness and the computation times of the queries. We test our approach on three large scale networks and show that the improved preprocessing is compatible with frequent real-time updates, even on the larger data set. The experiments also indicate that it is possible, if preprocessing time is an issue, to use the proposed preprocessing step on its own to obtain already a significant reduction of the query times compared to the no pruning scenario.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Public transit
  • Route planning
  • Algorithms
  • Preprocessing

Metrics

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

References

  1. Hannah Bast. Car or Public transport - Two Worlds. In Susanne Albers, Helmut Alt, and Stefan Näher, editors, Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pages 355-367. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-03456-5_24.
  2. Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result Diversity for Multi-Modal Route Planning. In Daniele Frigioni and Sebastian Stiller, editors, ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, volume 33 of OpenAccess Series in Informatics (OASIcs), pages 123-136, Sophia Antipolis, France, September 2013. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2013.123.
  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 Conference on Algorithms: Part I, ESA'10, pages 290-301, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1888935.1888969.
  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 Kliemann L., Sanders P. (eds) Algorithm Engineering, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, Cham, 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 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 15-29, January 2016. URL: https://doi.org/10.1137/1.9781611974317.2.
  6. Île de France Mobilités. Open data. https://opendata.stif.info. Google Scholar
  7. Daniel Delling, Julian Dibbelt, and Thomas Pajor. Fast and Exact Public Transit Routing with Restricted Pareto Sets. In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 54-65, San Diego, California, USA, 2019. Editor(s): Stephen Kobourov and Henning Meyerhenke. URL: https://doi.org/10.1137/1.9781611975499.5.
  8. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. Public Transit Labeling. In Evripidis Bampis, editor, Experimental Algorithms. SEA 2015., Lecture Notes in Computer Science, pages 273-285. Springer, Cham, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_21.
  9. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zündorf. Faster Transit Routing by Hyper Partitioning. In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.8.
  10. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-based public transit routing. In Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX'12), pages 130-140, 2012. URL: https://doi.org/10.1137/1.9781611972924.13.
  11. Mattia D'Emidio and Imran Khan. Dynamic Public Transit Labeling. In Sanjay Misra, Osvaldo Gervasi, Beniamino Murgante, Elena N. Stankova, Vladimir Korkhov, Carmelo Maria Torre, Ana Maria A. C. Rocha, David Taniar, Bernady O. Apduhan, and Eufemia Tarantino, editors, Computational Science and Its Applications - ICCSA 2019 - 19th International Conference, Saint Petersburg, Russia, July 1-4, 2019, Proceedings, Part I, volume 11619 of Lecture Notes in Computer Science, pages 103-117. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24289-3_9.
  12. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly Simple and Fast Transit Routing. In Vincenzo Bonifaci, Camil Demetrescu, and Alberto Marchetti-Spaccamela, editors, Experimental Algorithms. International Symposium on Experimental Algorithms SEA 2013, volume 7933 of Lecture Notes in Computer Science, pages 43-54, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-38527-8_6.
  13. Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-Constrained Multi-Modal Route Planning. In Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX’12), pages 118-129. SIAM, 2012. Editors David A. Bader and Petra Mutzel. URL: https://doi.org/10.1137/1.9781611972924.12.
  14. Pierre Hansen. Bicriterion Path Problems. In Günter Fandel and Tomas Gal, editors, Multiple Criteria Decision Making Theory and Application, volume 177 of Lecture Notes in Economics and Mathematical Systems, pages 109-127. Springer Berlin Heidelberg, 1980. URL: https://doi.org/10.1007/978-3-642-48782-8_9.
  15. Dominik Kirchler, Leo Liberti, and Roberto Wolfler Calvo. Efficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks. Journal of Experimental Algorithmics, 19:2.5:1-2.5:29, 2014. URL: https://doi.org/10.1145/2670126.
  16. Vassilissa Lehoux and Darko Drakulic. Mode Personalization in Trip-Based Transit Routing. In Valentina Cacchiani and Alberto Marchetti-Spaccamela, editors, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), volume 75 of OpenAccess Series in Informatics (OASIcs), pages 13:1-13:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2019.13.
  17. Thomas Liebig, Sebastian Peter, Maciej Grzenda, and Konstanty Junosza-Szaniawski. Dynamic Transfer Patterns for Fast Multi-modal Route Planning. In Arnold Bregt, Tapani Sarjakoski, Ron van Lammeren, and Frans Rip, editors, Societal Geo-innovation, pages 223-236, Cham, 2017. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-56759-4_13.
  18. Nave Map. https://map.naver.com/v5/. Google Scholar
  19. OVapi. http://gtfs.ovapi.nl/. Google Scholar
  20. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Efficient Models for Timetable Information in Public Transportation Systems. ACM Journal of Experimental Algorithmics, 12(2.4), 2008. URL: https://doi.org/10.1145/1227161.1227166.
  21. Andrea Raith, Marie Schmidt, Anita Schöbel, and Lisa Thom. Extensions of labeling algorithms for multi-objective uncertain shortest path problems. Networks, 72(1):84-127, 2018. URL: https://doi.org/10.1002/net.21815.
  22. Ben Strasser and Dorothea Wagner. Connection Scan Accelerated. 2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), pages 125-137, 2014. URL: https://doi.org/10.1137/1.9781611973198.12.
  23. Sascha Witt. Trip-based public transit routing. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 1025-1036, Berlin, Heidelberg, 2015. Springer. URL: https://doi.org/10.1007/978-3-662-48350-3_85.
  24. Sascha Witt. Trip-Based Public Transit Routing Using Condensed Search Trees. In Marc Goerigk and Renato Werneck, editors, Proceedings of the 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 1-12, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 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 Imprint Privacy Contact