Robuste Diensteinsatzplanung im Flugverkehr und im öffentlichen Personennahverkehr
Final Report Abstract
Das Forschungsprojekt beschäftigte sich mit der Dienstplanung von Piloten und Kabinenbesatzungen in Linienfluggesellschaften sowie Fahrern von Bussen im öffentlichen Personennahverkehr. Bei der Generierung von Dienstplänen wurden in beiden Fällen Optimierungsmethoden des Operations Research eingesetzt, wodurch in den letzten Jahrzehnten Kostenerspamisse nicht selten in Millionenhöhe erzielt wurden. Diese gingen bisher jedoch teilweise dadurch veloren, dass während der Ausführung aufgrund von Störungen kostenintensive Änderungen und Modifikationen der optimierten Dienstpläne notwendig wurden. Das Ziel des Forschungsprojektes bestand daher darin, Planungsmethoden und -algorithmen für die robuste Planung zu entwickeln, so dass die generierten Dienstpläne bei Störungen und kurzfristigen Änderungen weniger betroffen sind. Zunächst wurde der Begriff Robustheit für Zwecke des Forschungsprojekts definiert und messbar gemacht. Es wurden verschiedene Maße für die Robustheit der Pläne entwickelt, wie z.B. Anzahl und Schweregrad sekundärer Verspätungen, Anzahl der Ressourcenbelegungskonflikte oder verletzter Dienstregeln. Diese Maße haben sich als wertvoll für eine Abschätzung der erwarteten Kosten des tatsächlichen Ressourceneinsatzes herausgestellt, die es bei der Robusten Planung zu minimieren gilt. Die entwickelte stochastische Optimierungskomponente ist ein neuer Beitrag in der wissenschaftlichen Literatur. Zuvor veröffentlichte Forschungsergebnisse berücksichtigen vereinfachte Modelle, die u.a. wegen des hohen Rechen- und Datenaufwands viele praxisrelevante Aspekte ignorieren. In diesem Projekt wurden diese Modelle in technischer Hinsicht erweitert, um dem realen Komplexitätsgrad aus der Praxis zu begegnen. Zudem wurden die Modelle auf europäische Verhältnisse angepasst. Als Ausgangspunkt für das Projekt diente das am Lehrstuhl entwickelte Crew-Scheduling-System fiir den ÖPNV, wobei die Pairing-Optimierung auf einem Set-Partitioning-Modell und Column-Generation basiert. Es wurde eine neuer Ansatz zur stochastischen Column-Generation entwickelt, der es ermöglicht, große praxisrelevante Modelle zu lösen. Die Aufgabenstellung wird alternativ als ein duales Lagrange-Problem formuliert und mit einem Subgradientenverfahren gelöst oder als ein lineares Optimierungsmodell formuliert und mit Standardsoftware für Lineare Programmierung gelöst. Für das MIP-Modell wurde ein spezieller mehrkriterieller Branch&Price&Cut-Algorithmus angewandt. Weiterhin wurden mehrkriterielle Metaheuristiken, insbesondere SANE und MOEA für den Einsatz in der ÖPNV-Planung implementiert und bewertet. Zur Evaluierung der Robustheit der generierten Dienstpläne wurde ein diskreter ereignisorieniierter Simulator konzipiert und entwickelt. Die Simulationssoftware besilzt neben einem Event-Prozessor, der den Zeitfortschritt simuliert und Ereignisse aus der Warteschlange verarbeitet, eine Störungsgenerierungs- und eine Störungsmanagementkomponente. Die Architektur des Simulalionssystems ist generisch, so dass die beiden letzteren Komponenten in unterschiedlicher Genauigkeit und Komplexität eingesetzt werden können. Je nach Verwendungszweck des Simulators - einmalig zur Evaluation fertiger Einsatzpläne oder mehrfach - in jeder Iteration eines stochastischen Optimierungs Verfahrens - ist ein anderer Detaillierungsgrad der beiden Komponenten erforderlich. Zukünftige Arbeiten können sich insbesondere mit der Berücksichtigung der Flexibilität als zweiten Einflussfaktor der Robustheit konzentrieren. Dabei stehen Überlegungen im Vordergrund, wie stabile Einsatzpläne gleichzeitig auch ein hohes Maß an Flexibilität aufweisen können, um Störungen während Ausführung durch kostengünstige und einfache Eingriffe abzufedern. Eine Untersuchung des Zusammenspiels von Stabilität und Flexibilität greift dabei die Frage auf, ob eine Gegenläufigkeil dieser beiden Aspekte herrscht. Zusätzlich ist die Verfeinerung des Verspätungsgenerators sinnvoll, um den Methoden zur robusten Ressourcen-Einsalzplanung eine realistische Grundlage zu verliehen. Mit der Analyse historischer Verspätungsdaten können Verspätungsrisiken an unterschiedlichen Orten und zu unterschiedlichen Zeiten bestimmt werden. Erkenntnisse wie auch resultierende statistische Verteilungen können anschließend in der langfristigen Planung berücksichtigt werden.
Publications
-
Crew recovery with flight retiming. Operations Research Proceedings, S. 295-300,2008
Pottmeyer F., Dück V., Kliewer N.
-
Eine heuristische Methode zur Erhöhung der Robustheit von Mehrdepot-Umlaufplänen im ÖPNV. Operations Research Proceedings, S. 277-282, 2008
Kramkowski S., Meier C, Kliewer N.
-
Stability of airline schedules. Operations Research Proceedings, S. 265-270, 2008
Dück v., Kliewer N., Suhl L.
-
Heuristic Methods for Increasing Delay-Tolerance of Vehicle Schedules in Public Bus Transport. MIC 2009 Proceedings, Metaheuristic International Conference VIII, 2009
Kramkowski S., Kliewer N., Meier C
-
A Branch-and-Price-and-Cut Framework for Crew Pairing Optimization. Public Transport 3(I):43-64, 2011
Dück v., Wesselmann F., Suhl L.
-
A stochastic programming approach for robust vehicle scheduling in public bus transport, Procedia - Social and Behavioral Sciences, Vol. 20, pp. 826-835,2011
Naumann M., Suhl L., Kramkowski S.
-
Increasing delay-tolerance of vehicle and crew schedules in public transport by sequential, partial-integrated and integrated approaches. Procedia - Social and Behavioral Sciences, Vol. 20, pp. 292-301, 2011
Amberg B., Kliewer N.
-
Increasing stability of crew and aircraft schedules. Transportation Research C 20(1):47-61, 2012
Dück v., lonescu L., Kliewer N., Suhl L.
-
Multiple depot vehicle and crew scheduling with time windows for scheduled trips. Public Transport 3(3):213-244, 2012
Kliewer N., Amberg B., Arnberg B.
