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.
