Document Open Access Logo

Cost-Minimal Public Transport Planning

Authors Julius Pätzold, Alexander Schiewe, Anita Schöbel

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.8.pdf
  • Filesize: 1.12 MB
  • 22 pages

Document Identifiers

Author Details

Julius Pätzold
  • University of Goettingen, Lotzestr. 16-18, 37083 Göttingen, Germany
Alexander Schiewe
  • University of Goettingen, Lotzestr. 16-18, 37083 Göttingen, Germany
Anita Schöbel
  • University of Goettingen, Lotzestr. 16-18, 37083 Göttingen, Germany

Funding

This work was partially supported by DFG under SCHO 1140/8-1 and by the Simulation Science Center Clausthal/Göttingen.

Cite As Get BibTex

Julius Pätzold, Alexander Schiewe, and Anita Schöbel. Cost-Minimal Public Transport Planning. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.ATMOS.2018.8

Abstract

In this paper we discuss what a cost-optimal public transport plan looks like, i.e., we determine a line plan, a timetable and a vehicle schedule which can be operated with minimal costs while, at the same time, allowing all passengers to travel between their origins and destinations. We are hereby interested in an exact solution of the integrated problem. In contrast to a passenger-optimal transport plan, in which there is a direct connection for every origin-destination pair, the structure or model for determining a cost-optimal transport plan is not obvious and has not been researched so far.
We present three models which differ with respect to the structures we are looking for. If lines are directed and may contain circles, we prove that a cost-optimal schedule can (under weak assumptions) already be obtained by first distributing the passengers in a cost-optimal way. We are able to streamline the resulting integer program such that it can be applied to real-world instances. The model gives bounds for the general case. In the second model we look for lines operated in both directions, but allow only simplified vehicle schedules. This model then yields stronger bounds than the first one. Our most realistic model looks for lines operated in both directions, and allows all structures for the vehicle schedules. This model, however, is only computable for small instances. Finally, the results of the three models and their respective bounds are compared experimentally.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
  • Applied computing → Transportation
Keywords
  • Public Transport Planning
  • Integer Optimization
  • Line Planning
  • Vehicle Scheduling

Metrics

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

References

  1. S. Albert, J. Pätzold, A. Schiewe, P. Schiewe, and A. Schöbel. LinTim - Integrated Optimization in Public Transportation. Homepage. see http://lintim.math.uni-goettingen.de/. Google Scholar
  2. R. Borndörfer, M. Grötschel, and M. Pfetsch. A column-generation approach to line planning in public transport. Transportation Science, 41:123-132, 2007. Google Scholar
  3. R. Borndörfer, H. Hoppmann, and M. Karbstein. Passenger routing for periodic timetable optimization. Public Transport, 9(1-2):115-135, 2017. Google Scholar
  4. R. Borndörfer, M. Neumann, and M. E. Pfetsch. The line connectivity problem. In Operations Research Proceedings 2008, pages 557-562. Springer, 2009. Google Scholar
  5. Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner. A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable. In Ralf Borndörfer and Sabine Storandt, editors, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), volume 65 of OpenAccess Series in Informatics (OASIcs), pages 16:1-16:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2018.16.
  6. S. Bunte and N. Kliewer. An overview on vehicle scheduling models. Public Transport, 1(4):299-317, 2009. Google Scholar
  7. S. Burggraeve, S.H. Bull, R.M. Lusby, and P. Vansteenwegen. Integrating robust timetabling in line plan optimization for railway systems. Transportation Research C, 77:134-160, 2017. Google Scholar
  8. M.R. Bussieck. Optimal lines in public transport. PhD thesis, Technische Universität Braunschweig, 1998. Google Scholar
  9. A. Ceder and N.H.M. Wilson. Bus network design. Transportation Research Part B: Methodological, 20(4):331-344, 1986. Google Scholar
  10. M.T. Claessens, N.M. van Dijk, and P.J. Zwaneveld. Cost optimal allocation of rail passenger lines. European Journal on Operational Research, 110:474-489, 1998. Google Scholar
  11. G. Desaulniers and M.D. Hickman. Public transit. Handbooks in operations research and management science, 14:69-127, 2007. Google Scholar
  12. H. Fleischner. X. 1 algorithms for eulerian trails. eulerian graphs and related topics: Part 1. Annals of Discrete Mathematics, 50:1-13, 1991. Google Scholar
  13. M. Friedrich, M. Hartl, A. Schiewe, and A. Schöbel. Angebotsplanung im öffentlichen Verkehr - planerische und algorithmische Lösungen. In Heureka'17, 2017. Google Scholar
  14. P. Gattermann, J. Harbering, and A. Schöbel. Line pool generation. Public Transport, 9(1):7-32, 2017. Google Scholar
  15. Philine Gattermann, Peter Großmann, Karl Nachtigall, and Anita Schöbel. Integrating Passengers' Routes in Periodic Timetabling: A SAT approach. In Marc Goerigk and Renato Werneck, editors, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 3:1-3:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2016.3.
  16. M. Goerigk, M. Schachtebeck, and A. Schöbel. Evaluating line concepts using travel times and robustness: Simulations with the lintim toolbox. Public Transport, 5(3), 2013. Google Scholar
  17. M. Goerigk and A. Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers and Operations Research, 40(5):1363-1370, 2013. Google Scholar
  18. J. Goossens, C.P.M. van Hoesel, and L.G. Kroon. On solving multi-type railway line planning problems. European Journal of Operational Research, 168(2):403-424, 2006. Google Scholar
  19. C. Liebchen. Periodic Timetable Optimization in Public Transport. dissertation.de - Verlag im Internet, Berlin, 2006. Google Scholar
  20. C. Liebchen. Nutzung graphentheoretischer konzepte zur manuellen erstellung effizienter verkehrsangebote. In J. Schönberger & S. Nerlich, editor, 26. Verkehrswissenschaftliche Tage, pages 309-332, Dresden, Germany, 2018. Technische Universität Dresden, Fakultät Verkehrswissenschaften "Friedrich List". Google Scholar
  21. C. Liebchen and R. Möhring. The modeling power of the periodic event scheduling problem: Railway timetables - and beyond. In Proceedings of 9th meeting on Computer-Aided Scheduling of Public Transport(CASPT 2004). Springer, 2004. Google Scholar
  22. M. Lübbecke, C. Puchert, P. Schiewe, and A. Schöbel. Detecting structures in network models of integrated traffic planning. Presentation at the Clausthal-Göttingen International Workshop on Simulation Science. Google Scholar
  23. K. Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. PhD thesis, University of Hildesheim, 1998. Google Scholar
  24. Karl Nachtigall and Jens Opitz. Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations. In Matteo Fischetti and Peter Widmayer, editors, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), volume 9 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2008. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2008.1588.
  25. Julius Pätzold, Alexander Schiewe, Philine Schiewe, and Anita Schöbel. Look-Ahead Approaches for Integrated Planning in Public Transportation. 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 17:1-17:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2017.17.
  26. Julius Pätzold and Anita Schöbel. A Matching Approach for Periodic Timetabling. In Marc Goerigk and Renato Werneck, editors, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 1:1-1:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2016.1.
  27. L. Peeters. Cyclic Railway Timetabling Optimization. PhD thesis, ERIM, Rotterdam School of Management, 2003. Google Scholar
  28. L. Peeters and L. Kroon. A cycle based optimization model for the cyclic railway timetabling problem. In S. Voß and J. Daduna, editors, Computer-Aided Transit Scheduling, volume 505 of Lecture Notes in Economics and Mathematical systems, pages 275-296. Springer, 2001. Google Scholar
  29. L. Peeters and L. Kroon. A variable trip time model for cyclic railway timetabling. Transportation Science, 37(2):198-212, 2003. Google Scholar
  30. DFG research unit FOR 2083. Public tranport networks. https://github.com/FOR2083/PublicTransportNetworks. Google Scholar
  31. A. Schiewe, S. Albert, J. Pätzold, P. Schiewe, A. Schöbel, and J. Schulz. LinTim: An integrated environment for mathematical public transport optimization. Documentation. Technical Report 2018-08, Preprint-Reihe, Institut für Numerische und Angewandte Mathematik, Georg-August-Universität Göttingen, 2018. Google Scholar
  32. M. Schmidt and A. Schöbel. Timetabling with passenger routing. OR Spectrum, 37:75-97, 2015. Google Scholar
  33. A. Schöbel. Line planning in public transportation: models and methods. OR Spectrum, 34(3):491-510, 2012. Google Scholar
  34. A. Schöbel. An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research C, 74:348-365, 2017. Google Scholar
  35. A. Schöbel and S. Scholl. Line planning with minimal travel time. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, number 06901 in Dagstuhl Seminar Proceedings, 2006. Google Scholar
  36. P. Serafini and W. Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematic, 2:550-581, 1989. Google Scholar
  37. L.P. Veelenturf, L.G. Kroon, and G. Maroti. Passenger oriented railway disruption management by adapting timetables and rolling stock schedules. Transportation Research C, 80:133-147, 2017. Google Scholar
  38. P.J. Zwaneveld. Railway Planning - Routing of trains and allocation of passenger lines. PhD thesis, School of Management, Rotterdam, 1997. 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