On Cyclic Timetabling and Cycles in Graphs

Christian Liebchen and Leon Peeters

Accepted for publication in Discrete Optimization.

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]