direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 761-2002

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

On Cyclic Timetabling and Cycles in Graphs
Christian Liebchen and Leon Peeters
Accepted for publication in Discrete Optimization.
primary: 05C38 Paths and cycles
secondary: 90B06 Transportation, logistics
90C11 Mixed integer programming
periodic event scheduling problem, railway optimization, integral cycle basis, mixed integer programming
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.
Created on December 30 2002 | Last modified on April 07 2003
Download as [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe