Document Open Access Logo

Efficient Traffic Assignment for Public Transit Networks

Authors Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, Tobias Zündorf



PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.20.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Lars Briem
Sebastian Buck
Holger Ebhart
Nicolai Mallig
Ben Strasser
Peter Vortisch
Dorothea Wagner
Tobias Zündorf

Cite AsGet BibTex

Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf. Efficient Traffic Assignment for Public Transit Networks. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SEA.2017.20

Abstract

We study the problem of computing traffic assignments for public transit networks: Given a public transit network and a demand (i.e. a list of passengers, each with associated origin, destination, and departure time), the objective is to compute the utilization of every vehicle. Efficient assignment algorithms are a core component of many urban traffic planning tools. In this work, we present a novel algorithm for computing public transit assignments. Our approach is based upon a microscopic Monte Carlo simulation of individual passengers. In order to model realistic passenger behavior, we base all routing decisions on travel time, number of transfers, time spent walking or waiting, and delay robustness. We show how several passengers can be processed during a single scan of the network, based on the Connection Scan Algorithm [Dibbelt et al., LNCS Springer 2013], resulting in a highly efficient algorithm. We conclude with an experimental study, showing that our assignments are comparable in terms of quality to the state-of-the-art. Using the parallelized version of our algorithm, we are able to compute a traffic assignment for more than ten million passengers in well below a minute, which outperforms previous works by more than an order of magnitude.
Keywords
  • Algorithms
  • Optimization
  • Route planning
  • Public transportation

Metrics

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

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, Jonas Sternisko, and Sabine Storandt. Delay-robustness of transfer patterns in public transportation route planning. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'13), OpenAccess Series in Informatics (OASIcs), pages 42-54, 2013. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2013.42.
  4. 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. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2009.2148.
  5. 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.
  6. 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
  7. 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. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2014.1.
  8. Michael Patriksson. The Traffic Assignment Problem: Models and Methods. Courier Dover Publications, 2015. Google Scholar
  9. Johannes Schlaich, Udo Heidl, and Regine Pohlner. Verkehrsmodellierung für die Region Stuttgart - Schlussbericht. Unpublished manuscript, 2011. Google Scholar
  10. Yosef Sheffi. Urban Transportation Networks. Prentice-Hall, Englewood Cliffs, NJ, 1985. Google Scholar
  11. 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
  12. 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. Accepted for publication. 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