direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 736-2002

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

A Case Study in Periodic Timetabling
In Proceedings of ATMOS 2002, Electronic Notes in Theoretical Computer Science Vol. 66.6, Elsevier
primary: 90B20 Traffic problems
secondary: 90C27 Combinatorial optimization
90B90 Case-oriented studies
not available
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.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe