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

New Perspectives on PESP: T-Partitions and Separators

  • In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time.
Metadaten
Author:Niels LindnerORCiD, Christian LiebchenORCiD
Editor:Valentina Cacchiani, Alberto Marchetti-Spaccamela
Document Type:In Proceedings
Parent Title (English):19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Volume:75
First Page:2:1
Last Page:2:18
Series:OpenAccess Series in Informatics (OASIcs)
Publisher:Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication:Dagstuhl, Germany
Year of first publication:2019
Preprint:urn:nbn:de:0297-zib-73853
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2019.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.