Periodic timetable optimization in public transport

„The timetable is the essence of the service offered by any provider of public transport.“ (Jonathan Tyler, Philosophies of timetabling, definitions of bottlenecks and the usefulness of spreadsheets: the experience of a practical strategic timetable planner, CASPT 2006, CD-ROM) Despite this observation, in the practice of planning public transportation, only a few months ago OR decision support has still been limited to operations planning (vehicle scheduling, duty scheduling, crew rostering). The present thesis describes the optimization techniques that were deployed in computing the very first optimized timetable that went into daily service: the 2005 timetable of Berlin Underground. Compared to the former timetable, with our timetable the passengers of Berlin Underground are offered simultaneously improvements in three key criteria, which typically are conflicting: transfer waiting time, dwell time of trains, and number of trains that are required for the operation. The basic graph model, the Periodic Event Scheduling Problem (PESP), is known for 15 years and it had attracted many research groups. Nevertheless, this thesis collects significant progress that has been made only recently on issues like solution strategies or modeling capabilities. The latter include additional timetabling modeling features (train coupling/train sharing, bundling of lines of similar speed in order to increase track capacity), theoretical evidence that the symmetry requirement for periodic timetables cannot be expressed by only using (integer-valued) PESP constraints, and even the integration of further planning tasks in public transport, such as line planning. On the theory side, a more precise notion of the asymptotical complexity of the PESP is given, by providing a MAXSNP-hardness proof as a kind of negative result. On the positive side, the design of more efficient algorithms gave rise to a much deeper understanding of cycle bases of graphs, another very hot topic in discrete mathematics during the last three years. In 2005, this culminated in both, drawing the complete map for the seven relevant classes of cycle bases, and the design of the fastest algorithms for the Minimum Directed Cycle Basis Problem and for the Minimum 2-Basis Problem. These theoretical considerations are complemented by an exhaustive computational study. For the first time, the performance of a Cut-and-Branch Algorithm, Constraint Programming, and even a Genetic Algorithm was compared for periodic timetable optimization. The Cut-and-Branch Algorithm and the Genetic Algorithm turned out to be most convincing. On the one hand, the Genetic Algorithm has a slight advantage with respect to independence of parameter settings. On the other hand, the quality of the solutions obtained by the Cut-and-Branch Algorithm was somewhat better.