Finding Short Integral Cycle Bases for Cyclic Timetabling

in Guiseppe Di Battista and Uri Zwick (eds.): Algorithms - ESA 2003, LNCS 2832, Springer: Berlin, 2003, 715-726, Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03)

not available

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.

Download as [PDF] [ps.gz]