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

Sorting Criteria for Line-based Periodic Timetabling Heuristics

Please always quote using this URN: urn:nbn:de:0297-zib-97826
accepted for publication
  • It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2%.

Download full text files

Export metadata

Metadaten
Author:Patricia Ebert, Berenike MasingORCiD, Niels LindnerORCiD, Ambros GleixnerORCiD
Document Type:ZIB-Report
Tag:Periodic Event Scheduling; Public Transport; Timetabling
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:J. Computer Applications
Date of first Publication:2024/10/09
Series (Serial Number):ZIB-Report (24-07)
ISSN:1438-0064
Published in:to appear in Operations Research Proceedings 2024
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.