Loading…
Strong formulations for the Multi-module PESP and a quadratic algorithm for Graphical Diophantine Equation Systems
Galli, Laura; Stiller, Sebastian
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
The Periodic Event Scheduling Problem (PESP) is the method of choice for real-world periodic timetabling in public transport. Its MIP formulation has been studied intensely for the case of uniform modules, i.e., when all events have the same period. In practice, multiple modules are equally important. The strength of current methods for uniform modules rests on three ingredients: Every feasible instance allows for an optimal solution with a certain structure. Therefore, it can be reformulated with the use of an integral cycle basis. Finally, a certain type of rounding cuts arising from cycles has proven very powerful. All of this fails in the multi-module case. Therefore, applications with multiple periods were hardly solvable so far. We analyze a certain type of Diophantine equation systems closely related to the multi-module PESP. Thereby, we identify a structure, so-called sharp trees, that allows to solve the system in O (n^2) time. We show, a sharp tree is guaranteed to exist and found by a similar algorithm, if the modules form a linear lattice. Based on this we develop the machinery to solve multi-module PESPs on real-world scale. In particular, we recover all three ingredients for the multi-module case. In our computational results the new MIP-formulations drastically improve the solvability of multi-module PESPs. We also demonstrate that without sharp trees no similar approach can be hoped for.
