Cyclic timetabling for public transportation companies
is usually modeled by the periodic
event scheduling problem.
To deduce a mixed-integer programming formulation,
artificial integer variables have to be introduced.
There are many ways to define these
integer variables.
We show that the minimal number of integer variables required to
encode an instance is achieved by introducing an
integer variable for each element of some
integral cycle basis.
An integral cycle basis consists of |A|-|V|+1 oriented cycles
of a directed graph D=(V,A) that enable any oriented cycle of the
directed graph to be expressed as an integer linear combination.
The solution times for the originating application
vary extremely with different integral cycle bases.
However, our computational studies show that the width of
integral cycle bases is a good empirical measure
for the solution time of the MIP.
Clearly, integral cycle bases permit a much wider choice than
the former standard approach, in which integer variables
are associated with the co-tree arcs of some spanning tree.
To that end, we investigate classes of directed cycle
bases that are closely related to integral cycle bases,
namely (generalized) fundamental and undirected cycle bases.
This gives rise to both, a compact classification of directed
cycle bases and notable reductions of running times for
cyclic timetabling.
