Cost-minimal public transport planning
Pätzold J, Schiewe A, Schöbel A (2018)
Publication Type: Conference contribution
Publication year: 2018
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 65
Conference Proceedings Title: OpenAccess Series in Informatics
Event location: Helsinki, FIN
ISBN: 9783959770965
DOI: 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 passengeroptimal 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.
Involved external institutions
Germany (DE)How to cite
APA:
Pätzold, J., Schiewe, A., & Schöbel, A. (2018). Cost-minimal public transport planning. In Sabine Storandt, Ralf Borndorfer (Eds.), OpenAccess Series in Informatics. Helsinki, FIN: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Pätzold, Julius, Alexander Schiewe, and Anita Schöbel. "Cost-minimal public transport planning." Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018, Helsinki, FIN Ed. Sabine Storandt, Ralf Borndorfer, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018.
BibTeX: Download