OASIcs.ATMOS.2021.15.pdf
- Filesize: 0.63 MB
- 17 pages
Document
Transfer Customization with the Trip-Based Public Transit Routing Algorithm
Authors
-
Part of:
Volume:
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-09-27
Cite As Get BibTex
Vassilissa Lehoux-Lebacque and Christelle Loiodice. Transfer Customization with the Trip-Based Public Transit Routing Algorithm. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.15
Abstract
In the context of routing in public transit networks, we consider the issue of the customization of walking transfer times, which is incompatible with the preprocessing required by many state-of-the-art algorithms. We propose to extend one of those, the Trip-Based Public Transit Routing algorithm, to take into account at query time user defined transfer speed and maximum transfer duration. The obtained algorithm is optimal for the bicriteria problem of optimizing minimum arrival time and number of transfers. It is tested on two large data sets and the query times are compatible with real-time queries in a production context.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
Keywords
- Public transit
- Route planning
- Algorithms
- Customization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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.
- Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.14.
- Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. Public Transit Labeling. In Evripidis Bampis, editor, Experimental Algorithms, pages 273-285. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_21.
- 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), pages 130-140, 2012. URL: https://doi.org/10.1137/1.9781611972924.13.
- 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. SEA 2013, volume 7933 of Lecture Notes in Computer Science, pages 43-54, Berlin, Heidelberg, 2013. Springer. URL: https://doi.org/10.1007/978-3-642-38527-8_6.
- 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.
- Vassilissa Lehoux and Christelle Loiodice. Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm. In Dennis Huisman and Christos D. Zaroliagis, editors, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), volume 85 of OpenAccess Series in Informatics (OASIcs), pages 3:1-3:12, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2020.3.
- Île De France Mobilités. Open data. URL: https://www.iledefrance-mobilites.fr.
- OSM. Open street map. URL: https://www.openstreetmap.org.
- OSRM. Open source routing machine. URL: http://project-osrm.org/.
- Duc-Minh Phan and Laurent Viennot. Fast public transitrouting with unrestrictedwalking through hub labeling. In Proceedings of the Special Event on Analysis of Experimental Algorithms (SEA2019), volume 11544 of Lecture Notes in Computer Science. Springer, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-34029-2_16.
- 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.
- Luis Ulloa, Vassilissa Lehoux, and Frédéric Roulland. Trip Planning Within a Multimodal Urban Mobility. IET Intelligent Transport Systems, 12(2):87-92, 2018. URL: https://doi.org/10.1049/iet-its.2016.0265.
- Dorothea Wagner and Tobias Zündorf. Public Transit Routing with Unrestricted Walking. 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 7:1-7:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.7.
- Sacha Witt. Trip-based public transit routing. In N. Bansal and I. Finocchi, editors, ESA 2015, volume 9294 of Lecture Notes in Computer Science, Berlin, Heidelberg, 2015. Springer. URL: https://doi.org/10.1007/978-3-662-48350-3_85.