Mode Personalization in Trip-Based Transit Routing

File

Author Details

Vassilissa Lehoux

NAVER LABS Europe, Meylan, France

Darko Drakulic

NAVER LABS Europe, Meylan, France

Cite As Get BibTex

Vassilissa Lehoux and Darko Drakulic. Mode Personalization in Trip-Based Transit Routing. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.ATMOS.2019.13

Abstract

We study the problem of finding bi-criteria Pareto optimal journeys in public transit networks. We extend the Trip-Based Public Transit Routing (TB) approach [Sascha Witt, 2015] to allow for users to select modes of interest at query time. As a first step, we modify the preprocessing of the TB method for it to be correct for any set of selected modes. Then, we change the bi-criteria earliest arrival time queries, and propose a similar algorithm for latest departure time queries, that can handle the definition of the allowed mode set at query time. Experiments are run on 3 networks of different sizes to evaluate the cost of allowing for mode personalization. They show that although preprocessing times are increased, query times are similar when all modes are allowed and lower when some part of the network is removed by mode selection.

Subject Classification

ACM Subject Classification

Mathematics of computing → Graph theory

Keywords

Public transit
Route planning
Personalization

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Christoper L. Barrett, Riko Jacob, and Madhav Marathe. Formal-language-constrained path problems. SIAM Journal on Computing, 30(3):809-837, 2000. URL: https://doi.org/10.1137/S0097539798337716.
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.
Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Algorithm Engineering: Selected Results and Surveys, chapter Route Planning in Transportation Networks, pages 19-80. Springer International Publishing, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
Daniel Delling, Julian Dibbelt, and Thomas Pajor. Fast and exact public transit routing with restricted pareto sets. In Stephen Kobourov and Henning Meyerhenke, editors, Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 54-65, 2019. URL: https://doi.org/10.1137/1.9781611975499.5.
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.
Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-constrained multi-modal route planning. In SIAM, editor, Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX'12), pages 118-129, 2012. URL: https://doi.org/10.1137/1.9781611972924.12.
R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Catherine C. McGeoch, editor, Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 319-333, Berlin, Heidelberg, 2008. Springer. URL: https://doi.org/10.1007/978-3-540-68552-4_24.
Andrew V. Goldberg and Chris Harrelson. Computing the shortest path: A search meets graph theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pages 156-165, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1070432.1070455.
General Transit Feed Standard (GTFS). URL: https://developers.google.com/transit/gtfs/reference/.
Pierre Hansen. Bicriterion path problems. In Günter Fandel and Tomas Gal, editors, Multiple Criteria Decision Making Theory and Application. Proceedings of the Third Conference Hagen/Königswinter, West Germany, August 20-24, 1979, volume 177 of Lecture Notes in Economics and Mathematical Systems, pages 109-127, Berlin, Heidelberg, 1980. Springer. URL: https://doi.org/10.1007/978-3-642-48782-8_9.
Dominik Kirchler, Leo Liberti, and Roberto Wolfler Calvo. Efficient computation of shortest paths in time-dependent multi-modal networks. Journal of Experimental Algorithmics, 19:1-29, January 2014. URL: https://doi.org/10.1145/2670126.
Data Grand Lyon. URL: https://data.grandlyon.com/.
Île De France Mobilités. Open data. URL: https://opendata.stif.info.
Matthias Müller-Hannemann and Karsten Weihe. Pareto shortest paths is often feasible in practice. In Gerth Stølting Brodal, Daniele Frigioni, and Alberto Marchetti-Spaccamela, editors, Algorithm Engineering. WAE 2001, pages 185-197, Berlin, Heidelberg, 2001. Springer. URL: https://doi.org/10.1007/3-540-44688-5_15.
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):1-39, 2008. URL: https://doi.org/10.1145/1227161.1227166.
Luis Ulloa, Vassilissa Lehoux, and Frédéric Rouland. 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.
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.
Sascha Witt. Trip-based public transit routing using condensed search trees. In Marc Goerigk and Renato Werneck, editors, Proccedings of the 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’16), number Article No. 10, pages 10:1-10:12, 2016. URL: https://doi.org/10.4230/OASIcs.ATMOS.2016.10.