Lecture series »Felix-Klein-Colloquium« / 12. Juli 2016, 17:15 – 18:30 h
Lines, Timetables, Schedules: Integrated Optimization of Public Transport
How to plan a public transportation system such that it is well-designed for the passengers and at the same time not too costly? In theory and in practice, planning of a public transportation system is usually done in a sequential way: After the network design, the bus or train lines are established. Based on the line plan, a timetable is set up, and finally the vehicles’ schedules and the drivers’ schedules can be planned. From an optimization point of view such a sequential planning procedure can be regarded as a Greedy approach: in each planning stage one aims at the best one can do. This usually leads only to suboptimal solutions for the whole system. On the other hand, many of these single steps are already NP hard such that solving the integrated problem to optimality seems to be out of scope. In this talk we argue that public transportation as well as many other sequential processes will benefit from an integrated planning, and we show solution approaches on how to tackle sequential processes in an integrated way.
The talk consists of two parts: In the first part, we give a short overview on the state of the art in optimizing public transportation. We show models and algorithms for line planning, timetabling, and vehicle scheduling and discuss their different goals. In the second part ongoing research on integrated optimization will be presented. We propose an eigenmodel for designing iterative algorithms for integrated optimization and analyze its convergence. We then show how the eigenmodel can be applied to the planning phases in public transportation. We also discuss other approaches for integrative planning in public transportation.