Die Studie untersucht, wie verschiedene Zeilensortierstrategien die Leistung einer inkrementellen Heuristik für das Periodic Event Scheduling Problem (PESP) beeinflussen. Die Heuristik, die ursprünglich von Lindner und Liebchen vorgeschlagen wurde, baut einen Zeitplan auf, indem sie einer wachsenden Teilinstanz Zeile für Zeile hinzufügt und jede Zwischeninstanz mit dem ConcurrentPESP-Löser löst. In der vorliegenden Arbeit untersuchten die Autoren 27 verschiedene Sortierregeln, die auf der Anzahl der Bögen, den Bogengewichten, der gewichteten Spannweite und den unteren Schranken basierende Maße kombinieren, sowie drei Konnektivitätsregeln, die entweder die Anzahl der Verbindungen zwischen der aktuellen Teilinstanz und den verbleibenden Linien minimieren oder maximieren. Die Sortierregeln werden auf die 16 Eisenbahninstanzen der Benchmark-Bibliothek PESPlib angewandt. Für jede Iteration der Heuristik wurden 60 Sekunden Wandzeit für die vollständige Optimierungsroutine (full_opt) zur Verfügung gestellt, während die Fixierungsroutine (fix_opt) ohne Einschränkung ausgeführt wurde. Die Experimente wurden auf einem Intel Xeon E3-1270 Prozessor mit 32 GB RAM durchgeführt.
Die Ergebnisse zeigen, dass Sortierstrategien, die Bogengewichte einbeziehen, durchweg besser abschneiden als Strategien, die auf unteren Grenzen oder rohen Bogenzahlen basieren. Insbesondere gewichtsbasierte Regeln wie w-t (Gewicht der Transferbögen), ws-o (gewichtete Spannweite der ausgehenden Bögen) und max-ws-dd (maximale gewichtete Spannweite der Transfer- und Verweilbögen) ergaben für die meisten Instanzen die besten Lösungen. Auch die Konnektivität spielt eine Rolle: Während Läufe mit minimaler Konnektivität nie die besten Lücken ergaben, lieferten Läufe mit maximaler Konnektivität für einige wenige Instanzen die besten Lösungen, was darauf hindeutet, dass eine frühzeitige Optimierung stark verbundener Subinstanzen von Vorteil sein kann. Abbildung 1 des Berichts veranschaulicht die relativ besten Lücken jeder Sortierung, und Abbildung 2 fasst die Lücken über alle Instanzen zusammen und bestätigt die Dominanz der gewichtsbasierten Sortierungen. Die Studie berichtet über fünf neue etablierte Lösungen für PESPlib, die die besten bekannten Zielwerte um bis zu 2 % verbessern. Die Verbesserungen sind in Tabelle 1 quantifiziert: R2L2 verbesserte sich um 0,54 % mit max-w-t, R2L4 um 0,06 % mit ws-o, R3L3 um 1,89 % mit ws-dd, R3L4 um 1,36 % mit max-ws-dd und R4L3 um 0,09 % mit ws-o. Diese Verbesserungen zeigen, dass selbst bescheidene Änderungen in der Linienanordnung zu messbaren Verbesserungen der Fahrplanqualität führen können.
An dieser Arbeit sind vier Forscher beteiligt: Patricia Ebert, Berenike Masing, Niels Lindner und Ambros Gleixner. Das Team ist am Zuse-Institut Berlin und an der Hochschule für Technik und Wirtschaft Berlin angesiedelt. Finanziert wurde das Projekt vom Bundesministerium für Bildung und Forschung (BMBF) über den Forschungscampus MODAL (Förderkennzeichen 05M20ZBM), der die Teilnahme von Berenike Masing unterstützt. Die Studie wurde im Jahr 2023 durchgeführt und baut auf früheren Veröffentlichungen auf, in denen der PESPlib-Benchmark und der ConcurrentPESP-Solver vorgestellt wurden. Die Autoren melden keine Interessenkonflikte. Die Arbeit trägt zu den laufenden Bemühungen bei, die praktische Fahrplanoptimierung durch die Verfeinerung des inkrementellen Konstruktionsprozesses zu verbessern und bietet eine Reihe von empirisch validierten Sortierheuristiken, die in zukünftige Fahrplanplanplanungssysteme übernommen werden können.