TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2002

COGA 5-Wheel


zur Navigation

Preprints 2002

On Cyclic Timetabling and Cycles in Graphs
Zitatschlüssel Report-761-2002
Autor Christian Liebchen and Leon Peeters
Jahr 2002
Nummer 761
Notiz Accepted for publication in Discrete Optimization.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung The cyclic railway timetabling problem (CRTP) essentially is defined by some constraint graph together with a cycle period time. We point out the relevance of cycles of the constraint graph for the CRTP. This covers valid inequalities for a Branch and Cut approach and special cases in that CRTP becomes easy. But emphasis will be put on the problem formulation. The most intuitive model for cyclic timetabling involves node potentials. Modelling the cyclicity appropriately immediately results in an integer variable for every restriction, or arc of the constraint graph. A more sophisticated model regards the corresponding (periodic) tension. This well-established approach only requires an integer variable for every co-tree arc. The latter may be interpreted as representants for the elements of (strictly) fundamental cycle bases. We introduce the more general concept of integral cycle bases for characterizing periodic tensions. Whereas the number of integer variables is still limited to the cyclomatic number of the constraint graph, there is a much wider choice for the cycle basis. One can profit immediately from this, because there are box constraints known for every integer variable that could ever appear.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe