direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints

Strong formulations for the Multi-module PESP and a quadratic algorithm for Graphical Diophantine Equation Systems
Zitatschlüssel Report-009-2010
Autor Laura Galli and Sebastian Stiller
Jahr 2010
Nummer 009
Monat april
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag