License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2018.8
URN: urn:nbn:de:0030-drops-97138
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9713/
Go to the corresponding OASIcs Volume Portal

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

Cost-Minimal Public Transport Planning

pdf-format:
OASIcs-ATMOS-2018-8.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{ptzold_et_al:OASIcs:2018:9713,
  author =	{Julius P{\"a}tzold and Alexander Schiewe and Anita Sch{\"o}bel},
  title =	{{Cost-Minimal Public Transport Planning}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation  Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{8:1--8:22},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Ralf Bornd{\"o}rfer and Sabine Storandt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9713},
  URN =		{urn:nbn:de:0030-drops-97138},
  doi =		{10.4230/OASIcs.ATMOS.2018.8},
  annote =	{Keywords: Public Transport Planning, Integer Optimization, Line Planning, Vehicle Scheduling}
}

Keywords: Public Transport Planning, Integer Optimization, Line Planning, Vehicle Scheduling
Collection: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Issue Date: 2018
Date of publication: 28.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI