Sorting Criteria for Line-Based Periodic Timetabling Heuristics

Patricia Ebert (), Berenike Masing (), Niels Lindner () and Ambros Gleixner ()
Additional contact information
Patricia Ebert: Zuse Institute Berlin
Berenike Masing: Zuse Institute Berlin
Niels Lindner: Zuse Institute Berlin
Ambros Gleixner: Zuse Institute Berlin

A chapter in Operations Research Proceedings 2024, 2025, pp 348-354 from Springer

Abstract: Abstract 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\%$$ 2 % .

Keywords: Public Transport; Timetabling; Periodic Event Scheduling (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-92575-7_50

Ordering information: This item can be ordered from
http://www.springer.com/9783031925757

DOI: 10.1007/978-3-031-92575-7_50

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().