ZIB-Report
Refine
Year of publication
- 2018 (5) (remove)
Document Type
- ZIB-Report (5)
Has Fulltext
- yes (5)
Is part of the Bibliography
- no (5)
Keywords
- Periodic timetabling (2)
- Bipartite matching (1)
- Change-cycle inequality (1)
- Cycle inequality (1)
- Linienplanung (1)
- Vehicle scheduling (1)
- ÖPNV (1)
Institute
18-27
We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip.
Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths.
Our runtime analysis shows, that the presented approach compares very well against the
theoretical minimum runtime.
18-47
Dieses Dokument fasst den Stand der mathematischen Modellierung von
Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise
Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch
behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im
Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben
zunächst das Konzept. Die konkrete Realisierung wird im Folgenden
beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow,
MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs.
18-45
18-38
A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable
(2018)
We consider the following planning problem in public transportation: Given a
periodic timetable, how many vehicles are required to operate it?
In [9], for this sequential approach, it is proposed to first expand the periodic
timetable over time, and then answer the above question by solving a flow-based
aperiodic optimization problem.
In this contribution we propose to keep the compact periodic representation of
the timetable and simply solve a particular perfect matching problem. For practical
networks, it is very much likely that the matching problem decomposes into several
connected components. Our key observation is that there is no need to change any
turnaround decision for the vehicles of a line during the day, as long as the timetable
stays exactly the same.
18-16
Cycle inequalities play an important role in the polyhedral study of the periodic
timetabling problem. We give the first pseudo-polynomial time separation algo-
rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial
time separability of the change-cycle inequalities. Moreover, we provide several
NP-completeness results, indicating that pseudo-polynomial time is best possible.
The efficiency of these cutting planes is demonstrated on real-world instances of the
periodic timetabling problem.