2026-07-21T12:28:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14871 2024-03-06T10:31:34Z ddc:004 open_access

Forward Cycle Bases and Periodic Timetabling Lindner, Niels Liebchen, Christian Masing, Berenike Periodic Timetabling Cycle Bases Mixed Integer Programming Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance R1L1 of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niels Lindner and Christian Liebchen and Berenike Masing 2021 Is Part Of OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2021.2 urn:nbn:de:0030-drops-148719 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.2 eng https://creativecommons.org/licenses/by/4.0/legalcode