TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2002

COGA 5-Wheel


zur Navigation

Preprints 2002

A Case Study in Periodic Timetabling
Zitatschlüssel Report-736-2002
Autor Christian Liebchen and Rolf H. Möhring
Jahr 2002
Nummer 736
Notiz In Proceedings of ATMOS 2002, Electronic Notes in Theoretical Computer Science Vol. 66.6, Elsevier
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung In the overwhelming majority of public transportation companies, designing a periodic timetable is even nowadays largely performed manually. Software tools only support the planners in evaluating a periodic timetable, or by letting them comfortably shift sets of trips by some minutes, but they rarely use optimization methods. One of the main arguments against optimization is that there is no clear objective in practice, but that many criteria such as amount of rolling stock required, average passenger changing time, average speed of the trains, and the number of cross-wise correspondences have to be considered. This case study will demonstrate on the example of the Berlin underground (BVG) that all these goals can be met if carefully modeled, and that timetables constructed by optimization lead to considerable improvements. Our approach uses the Periodic Event Scheduling Problem (PESP) with several add-ons concerning problem reduction and strengthening. The resulting integer linear programs are solved with the CPLEX MIP-Solver. We have been able to construct periodic timetables that improve the current timetable considerably. For any of the above criteria, we have been able to identify global lower and upper bounds. Our favorite timetable improves the current BVG timetable in each of these criteria.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe