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

Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times

  • The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.
Metadaten
Author:Enrico BortolettoORCiD, Niels LindnerORCiD
Editor:Guido Voigt, Malte Fliedner, Knut Haase, Wolfgang Brüggemann, Kai Hoberg, Jörn Meissner
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2023
First Page:397
Last Page:402
Series:Lecture Notes in Operations Research
Year of first publication:2025
Preprint:urn:nbn:de:0297-zib-92315
DOI:https://doi.org/10.1007/978-3-031-58405-3_51
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.