Abstract
We study the problem of computing all Pareto-optimal journeys in a public transit network regarding the two criteria of arrival time and number of transfers taken. We take a novel approach, focusing on trips and transfers between them, allowing fine-grained modeling. Our experiments on the metropolitan network of London show that the algorithm computes full 24-hour profiles in 70ms after a preprocessing phase of 30s, allowing fast queries in dynamic scenarios.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bast, H., Carlsson, E., Eigenwillig, A., Geisberger, R., Harrelson, C., Raychev, V., Viger, F.: Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 290–301. Springer, Heidelberg (2010)
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route Planning in Transportation Networks. ArXiv e-prints arXiv:1504.05140 [cs.DS] (Apr 2015)
Bast, H., Storandt, S.: Frequency-based Search for Public Transit. In: SIGSPATIAL, pp. 13–22. ACM, New York (2014)
Berger, A., Delling, D., Gebhardt, A., Müller-Hannemann, M.: Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected. In: ATMOS 2009. OASIcs (2009)
Brodal, G.S., Jacob, R.: Time-dependent networks as models to achieve fast exact time-table queries. Electronic Notes in Theor. Computer Science 92, 3–15 (2004)
Cionini, A., D’Angelo, G., D’Emidio, M., Frigioni, D., Giannakopoulou, K., Paraskevopoulos, A., Zaroliagis, C.: Engineering Graph-Based Models for Dynamic Timetable Information Systems. In: ATMOS 2014. OASIcs (2014)
Dean, B.C.: Continuous-Time Dynamic Shortest Path Algorithms. Master’s thesis, Massachusetts Institute of Technology (1999)
Delling, D., Dibbelt, J., Pajor, T., Werneck, R.F.: Public Transit Labeling. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 273–285. Springer, Heidelberg (2015)
Delling, D., Katz, B., Pajor, T.: Parallel Computation of Best Connections in Public Transportation Networks. JEA 17, 4.4:4.1–4.4:4.26 (2012)
Delling, D., Pajor, T., Werneck, R.F.: Round-Based Public Transit Routing. Transportation Science, advance online publication (2012)
Dibbelt, J., Pajor, T., Strasser, B., Wagner, D.: Intriguingly Simple and Fast Transit Routing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 43–54. Springer, Heidelberg (2013)
Geisberger, R.: Contraction of Timetable Networks with Realistic Transfers. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 71–82. Springer, Heidelberg (2010)
Hansen, P.: Bicriterion Path Problems. In: Multiple Criteria Decision Making Theory and Application. LNEMS, vol. 177, pp. 109–127. Springer, Heidelberg (1980)
Müller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.: Timetable Information: Models and Algorithms. In: Geraets, F., Kroon, L.G., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Railway Optimization 2004. LNCS, vol. 4359, pp. 67–90. Springer, Heidelberg (2007)
Müller-Hannemann, M., Weihe, K.: On the cardinality of the Pareto set in bicriteria shortest path problems. Annals of Operations Research 147(1), 269–286 (2006)
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient Models for Timetable Information in Public Transportation Systems. JEA 12, 2.4:1–2.4:39 (2008)
Strasser, B., Wagner, D.: Connection Scan Accelerated. In: ALENEX 2014, pp. 125–137 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Witt, S. (2015). Trip-Based Public Transit Routing. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_85
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_85
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)