Document Open Access Logo

Public Transit Routing with Unrestricted Walking

Authors Dorothea Wagner, Tobias Zündorf

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2017.7.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Dorothea Wagner
Tobias Zündorf

Cite As Get BibTex

Dorothea Wagner and Tobias Zündorf. Public Transit Routing with Unrestricted Walking. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/OASIcs.ATMOS.2017.7

Abstract

We study the problem of answering profile queries in public transportation networks that allow unrestricted walking. That is, finding all Pareto-optimal journeys regarding travel time and number of transfers in a given time interval. We introduce a novel algorithm that, unlike most state-of-the-art algorithms, can compute profiles efficiently in a setting that allows arbitrary walking. Using our algorithm, we show in an extensive experimental study that allowing unrestricted walking, significantly reduces travel times, compared to settings where walking is restricted. Beyond that, we publish the transportation networks of Switzerland that we used in our study, in order to encourage further research on this topic.

Subject Classification

Keywords
  • Algorithms
  • Optimization
  • Route planning
  • Public transportation

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 Proceedings of the 18th Annual European Symposium on Algorithms (ESA'10), volume 6346 of Lecture Notes in Computer Science, pages 290-301. Springer, 2010. Google Scholar
  2. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks. In Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. Google Scholar
  3. Hannah Bast, Matthias Hertel, and Sabine Storand. Scalable Transfer Patterns. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 15-29. SIAM, 2016. Google Scholar
  4. Hannah Bast and Sabine Storandt. Frequency-Based Search for Public Transit. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 13-22. ACM Press, November 2014. Google Scholar
  5. Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected. In Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09), OpenAccess Series in Informatics (OASIcs), 2009. Google Scholar
  6. 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 Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 35-46. Springer, May 2010. Google Scholar
  7. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck. Computing Multimodal Journeys in Practice. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 260-271. Springer, 2013. Google Scholar
  8. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. Public Transit Labeling. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), Lecture Notes in Computer Science, pages 273-285. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-20086-6_21.
  9. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. Transportation Science, 2014. URL: http://dx.doi.org/10.1287/trsc.2014.0534.
  10. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly Simple and Fast Transit Routing. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 43-54. Springer, 2013. Google Scholar
  11. Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-Constrained Multimodal Route Planning. Journal of Experimental Algorithmics (JEA), 19:3-2, 2015. Google Scholar
  12. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'14), OpenAccess Series in Informatics (OASIcs), 2014. Google Scholar
  13. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Fast Exact Shortest Path and Distance Queries on Road Networks with Parametrized Costs. In Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 66:1-66:4. ACM Press, 2015. Google Scholar
  14. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  15. Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee. Multi-Criteria Shortest Paths in Time-Dependent Train Networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 347-361. Springer, June 2008. Google Scholar
  16. 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. Google Scholar
  17. Ben Strasser and Dorothea Wagner. Connection Scan Accelerated. In Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX'14), pages 125-137. SIAM, 2014. Google Scholar
  18. Sascha Witt. Trip-Based Public Transit Routing. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA'15), Lecture Notes in Computer Science. Springer, 2015. Google Scholar
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 About DROPS Imprint Privacy Contact