Inhalt des Dokuments
Preprint 736-2002
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- A Case Study in Periodic Timetabling
- Authors
- Publication
- In Proceedings of ATMOS 2002, Electronic Notes in Theoretical Computer Science Vol. 66.6, Elsevier
- Classification
-
MSC: primary: 90B20 Traffic problems secondary: 90C27 Combinatorial optimization 90B90 Case-oriented studies - Keywords
-
not available
- Abstract
-
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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe