• search hit 1 of 12
Back to Result List

Finding Short Integral Cycle Bases for Cyclic Timetabling

Please always quote using this URN:urn:nbn:de:0296-matheon-225
  • 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. Hence, to formulate better solvable integer programs, we present algorithms that construct integral cycle bases of small width. 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 full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christian Liebchen
URN:urn:nbn:de:0296-matheon-225
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2003/12/22
Release Date:2003/12/18
Institute:Technische Universität Berlin
Preprint Number:16
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.