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.
