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%.
| 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 |

