Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Forward Cycle Bases and Periodic Timetabling

Please always quote using this URN: urn:nbn:de:0297-zib-82756
  • 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 \texttt{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.

Download full text files

Export metadata

Metadaten
Author:Niels LindnerORCiD, Christian LiebchenORCiD, Berenike MasingORCiD
Document Type:ZIB-Report
Tag:Cycle Bases; Mixed Integer Programming; Periodic Timetabling
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:G. Mathematics of Computing
J. Computer Applications
Date of first Publication:2021/07/03
Series (Serial Number):ZIB-Report (21-18)
ISSN:1438-0064
Published in:appeared in 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2021.2
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.