Please use this identifier to cite or link to this item:
For citation please use:
Main Title: On Cyclic Timetabling and Cycles in Graphs
Author(s): Liebchen, Christian
Peeters, Leon
Type: Research Paper
Abstract: 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.
Subject(s): periodic event scheduling problem
railway optimization
integral cycle basis
mixed integer programming
Issue Date: 2002
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 05C38 Paths and cycles
90B06 Transportation, logistics
90C11 Mixed integer programming
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2002, 761
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 304.16 kB
DownloadShow Preview
Format: Postscript | Size: 893.28 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.