Internationales Verkehrswesen (71) 2 | 2019 82 TECHNOLOGIE Wissenschaft Methodik zur Erstellung robuster Airline-Schedules Umlauf- und Abflugplanung von Flugzeugen zur Verminderung von Sekundärverspätungen Robust Scheduling, Sekundärverspätungen, Flugverspätungen, Umlaufplanung Es wird eine Methodik zur Erstellung eines robusten Umlaufplans zur Verringerung von Folgeverspätungen vorgestellt. Der Umlaufplan einer Airlineflotte wird auf Basis eines Schedules erstellt und zusätzlich eine geringfügige zeitliche Verschiebung der Flüge durchgeführt. Zur Optimierung werden metaheuristische Algorithmen genutzt, die eine Reduzierung der Verspätungen zum Ziel haben. Neben dem Erstellen eines gegen Verspätungen robusten Flugplans ist es das Ziel, auf Basis realer Betriebsdaten einer Fluggesellschaft die Bewertung der Robustheit anhand eines Simulationsmodells zu ermitteln. Katrin Kölker, Marius Radde, Eva Lang, Klaus Lütjens, Judith Semar, Volker Gollnick V erspätungen im Luftverkehr haben in den vergangenen Jahren drastisch zugenommen [1] und führen zu hohen Kosten und Problemen bei den Flughäfen, den Fluggesellschaften und auch den Passagieren. Daher sind alle genannten Akteure an einer Reduzierung der Verspätungen interessiert. Auf Initiative des Bundesministeriums für Verkehr und digitale Infrastruktur (BMVI) fand am 5. Oktober 2018 hierzu ein Spitzengespräch Luftfahrt in Hamburg statt, bei dem u.a. folgende Maßnahme beschlossen wurde: „Verspätungsanfällige Flüge werden durch kurz- und langfristigen Abgleich des Flugplans mit den Ist-Werten ermittelt, um dann ggf. einen Teil der geplanten Flugzeugrotation herauszulösen und die Übernahme des Fluges durch ein anderes Flugzeug zu ermöglichen. […]“ [2]. In der vorliegenden Arbeit wird eine Optimierungsmethodik vorgestellt, um die genannte Maßnahme umzusetzen. Das Ziel der Methodik ist es dabei, auf Basis empirischer Daten die Flugverspätungen zu reduzieren ohne dabei die Produktivität des Flugbetriebs zu verringern. Das bedeutet, dass mit der gleichen Flotte und der gleichen Anzahl von Flügen ein Schedule mit weniger Verspätungen betrieben werden kann. Es wird hier das Wort Schedule statt Flugplan benutzt, um die Planung des Streckenangebotes einer Airline (Schedule) abzugrenzen von der Flugplanung im Sinne der Planung einer einzelnen Flugroute (Flugführung). In dem Projekt ROFL (Robuste Flugplanung) wurde in den Jahren 2016 bis 2018 untersucht, inwieweit unter den genannten Nebenbedingungen Verspätungen durch eine effizientere Planung vermindert werden können. Gerade für Fluggesellschaften sind Folgebzw. Sekundärverspätungen - also die Verspätungen, die durch verspätete Flugzeuge oder Personal der vorhergehenden Flüge entstehen - ein großes Problem, da die Verspätung eines Fluges (Primärverspätung) durch einen Dominoeffekt Verspätungen mehrerer Folgeflüge nach sich zieht. Aus Sicht der Fluggesellschaft lassen sich diese Verspätungen am ehesten durch eine bessere Planung des Schedules und die Optimierung von Pufferzeiten verhindern. Um eine bessere Planung zu ermöglichen, ist auch ein stabiler Planungsprozess notwendig. Stabilität bedeutet dabei, dass nachfolgende Änderungen am Schedule im sequentiellen Flugplanungsprozess die Robustheit der Planung nicht wieder reduzieren. Der Planungsprozess wurde ebenfalls im Projekt analysiert [3] und Vorschläge zur Stabilisierung ausgearbeitet. Die Entwicklung dieser neuen Methode zur Erhöhung der Robustheit erfolgt in Zusammenarbeit mit mehreren Fluggesellschaften. Dadurch war es möglich, die detaillierten Flugdaten mehrerer Jahre des Flugbetriebs verschiedener Fluggesellschaften im europäischen Umfeld auszuwerten und eine valide, bessere Kalibrierung der zu Grunde liegenden Modelle zu gewährleisten. Die Zusammenarbeit mit den Fluggesellschaften vereinfacht zusätzlich auch die zeitnahe Anwendung der Ergebnisse im realen Flugbetrieb. Das Projekt ist eine Zusammenarbeit des Deutschen Zentrums für Luft- und Raumfahrt (DLR) mit Lufthansa Systems, deren Kunden die Ergebnisse des Projektes in der Praxis nutzen. PEER REVIEW - BEGUTACHTET Eingereicht: 31.01.2019 Endfassung: 12.03.2019 Internationales Verkehrswesen (71) 2 | 2019 83 Wissenschaft TECHNOLOGIE Sekundärverspätungen im Flugbetrieb Das Ziel des ROFL-Projekts war die Gestaltung robuster Flugpläne. Der Fokus lag auf der robusten Lösung des Aircraft Routing Problems (ARP). Beim ARP werden für einen bestehenden Schedule Flugzeugumläufe einer Airlineflotte gestaltet. Die zur Verfügung stehenden Flugzeuge einer Fluggesellschaft werden dabei so auf die geplanten Flüge verteilt, dass jeder Flug genau einmal geflogen wird und darüber hinaus ein bestimmtes Optimierungsziel bestmöglich umgesetzt wird. Im Falle der Robustheit besteht das Ziel darin, die geplanten Flugzeugumläufe (auch Rotationen genannt) derart zu organisieren, dass auftretende Verspätungen möglichst gut abgefedert werden. Es wird also darauf abgezielt, die Verschleppung von Verspätungen zu minimieren und zeitliche Puffer in der Bodenzeit dementsprechend dort zur Verfügung zu stellen, wo sie am nötigsten sind. Das Prinzip der verschleppten Verspätung wird an Bild 1 verdeutlicht: Flug i fliegt nicht zum geplanten Zeitpunkt STD i (Scheduled Time of Departure) ab, sondern verspätet zum Zeitpunkt ATD i (Actual Time of Departure). Diese Verspätung könnte beispielsweise auf die Witterungsbedingungen zurückzuführen sein. Sie ist damit von der Airline nicht beeinflussbar und wird als Primärverspätung bezeichnet. Durch den verspäteten Abflug verschiebt sich nun auch der geplante Ankunftszeitpunkt STA i (Scheduled Time of Arrival) auf ATA i (Actual Time of Arrival). Die ursprünglich geplante Bodenzeit zwischen Flug i und Flug i+1 verkürzt sich durch die verspätete Ankunft. Die Zeit, die zur Durchführung der notwendigen Turn- Around-Prozesse am Boden mindestens notwendig ist (Minimum Ground Time, MGT), ist nun geringer als die verbleibende verfügbare Bodenzeit. Jedoch kann erst nach Vollendung der Bodenprozesse der Folgefluges STD i+1 abfliegen. Folglich entsteht durch die verspätete Ankunft von Flug i und die zu kurz geplante Bodenzeit eine Abflugverspätung bei Flug i+1, eine sog. verschleppte Verspätung (auch Sekundärverspätung genannt). Stochastische Simulation des Flugbetriebs Um die bei der Durchführung geplanter Flugzeugumläufe entstehenden Verspätungen bei Abflug und Ankunft zu quantifizieren, muss der Betrieb eines gegebenen Schedules simuliert werden. Hierfür wurden Modelle zur Schätzung von Boden- und Blockzeiten entwickelt, mit denen sich die erwarteten Abflugsbzw. Ankunftszeiten und somit auch die Verspätungen eines Fluges in Abhängigkeit seiner verschiedenen Charakteristika wie z. B. Abflughafen, Abflugzeit und Flugzeugtyp berechnen lassen. Das Bodenzeitmodell dient dabei zur Schätzung der Zeitdauer, die das Flugzeug zwischen zwei aufeinander folgenden Flügen am Gate steht, und umfasst dementsprechend die Zeiten für Bodenprozesse (Turn-Around) sowie Warte- und Pufferzeiten. Das Blockzeitmodell schätzt die Blockzeit eines Fluges, d. h. sowohl die eigentliche Flugzeit als auch die Rollzeiten am Start- und Zielflughafen. Die Modelle sind dynamisch und reagieren dadurch auf den bisherigen Verlauf der Rotationen, wobei keine Interdependenzen zwischen mehreren, zeitgleich durchgeführten Umläufen berücksichtigt werden. Die Modellkalibrierung muss mit historischen Daten aus dem Flugbetrieb derjenigen Airline durchgeführt werden, deren geplante Schedules simuliert werden. Bild-2 zeigt den Vergleich zwischen der tatsächlichen und der simulierten On-Time-Performance einer europäischen Fluggesellschaft aus der Sommerflugplanperiode 2016. Die Modelle wurden vorab mit Daten aus den Jahren 2014 und 2015 trainiert. Der Schedule wurde 10.000 Mal unter Berücksichtigung stochastischer Schwankungen, die sich in den historischen Daten finden, simuliert. „P0“ bezieht sich auf den Anteil der Flüge, die pünktlich oder sogar verfrüht abfliegen bzw. ankommen. „P3“ ist der Anteil der Flüge, die eine Verspätung zwischen null und einschließlich drei Minuten aufweisen. „P15“ ist analog zu interpretieren und „D15“ enthält alle Flüge, die eine Verspätung von mehr als 15 Minuten aufweisen. Der Vergleich zeigt, dass die Simulation ein sehr gutes Abbild der Realität erzeugt. Die Anteile der einzelnen Verspätungskategorien unterscheiden sich nur unwesentlich voneinander. Dies gilt im Übrigen nicht nur auf so stark aggregierter Ebene wie hier dargestellt, sondern beispielsweise auch auf der Ebene einzelner Teil-Flotten eines bestimmten Flugzeugtyps der gewählten Fluggesellschaft. Optimierung des Schedules Die oben vorgestellte Simulationsumgebung nimmt in den entwickelten Optimierungsverfahren eine zentrale Rolle ein. Da diese Umgebung bzw. die in ihr zum Einsatz kommenden Modelle keine Trennung zwischen Primär- und Sekundärverspätung vornehmen, liegt der Fokus der Optimierung konsequenterweise auf der Reduzierung von Gesamtverspätungen, worunter seitens der Fluggesellschaft sowohl in der Regel nicht beeinflussbare Primärverspätungen (etwa wetterbedingt) als auch beeinflussbare (verschleppte) Verspätungen zu verstehen sind. Unter der Prämisse, dass Primärverspätungen Bild 1: Wie werden Verspätungen verschleppt? Alle Abbildungen: Autoren Internationales Verkehrswesen (71) 2 | 2019 84 TECHNOLOGIE Wissenschaft durch die Fluggesellschaft nicht beeinflussbar sind, wird durch die Reduktion von Gesamtverspätungen automatisch eine Reduktion von verschleppten Verspätungen realisiert. Aus der Simulation von Schedules lassen sich verschiedene Performance-Kennziffern im Hinblick auf die Pünktlichkeit ableiten. Im Folgenden wird die Summe der mittleren Ankunftsverspätungen aller Flüge über alle Simulationsläufe als entsprechende Maßzahl verwendet. Im Rahmen verschiedener metaheuristischer Optimierungsmethoden kann diese Maßzahl wiederum als „Fitness“-Kriterium verwendet werden. Zwei dieser Methoden, Genetische Algorithmen einerseits und Binäre Partikelschwarmoptimierung andererseits, wurden im Projektverlauf eingesetzt, um die Steigerung der Robustheit von Airline-Schedules zu realisieren. Auf metaheuristische Verfahren muss hier zurückgegriffen werden, da das Problem zu komplex ist, um exakt gelöst zu werden. Bereits für eine kleine Flotte entstehen dafür zu viele Kombinationen verschiedener, möglicher Flugzeugumläufe. Eine Näherungslösung wird - im Gegensatz zu einer exakten Lösung - schnell gefunden und ist hinreichend robust, weswegen diese Vorgehensweise für die Anwendung im Betrieb optimal ist. Beide Verfahren beginnen im vorliegenden Anwendungsfall mit einer initialen Menge von Schedules. Diese Schedules unterscheiden sich hinsichtlich der Zuweisung einzelner Flüge zu den zur Verfügung stehenden Flugzeugen. Die Anzahl der möglichen Zuweisungen steigt exponentiell mit der Anzahl der Flugzeuge bzw. der Anzahl der Flüge. Über eine bestimmte Anzahl von Iterationen werden die verschiedenen Schedules, angefangen mit der Initialmenge, immer wieder hinsichtlich ihrer „Fitness“ beurteilt bzw. verglichen und anschließend durch vorgegebene Rechenoperationen in Abhängigkeit ihrer Fitness-Werte miteinander kombiniert. Ziel ist es, auf diese Weise höherwertige Schedules im Sinne der Fitness (also weniger Sekundärverspätungen) zu erzeugen. Im weiteren Verlauf des Artikels wird auf die Ergebnisse der Partikelschwarmoptimierung eingegangen, da diese Methode für das spezifische Problem effizienter ist. Für nähere Informationen zur Funktionsweise wird an dieser Stelle auf [4] verwiesen. Ergebnisse der robusten Umlaufplanung Bild 3 zeigt den Verlauf der Partikelschwarmoptimierung für einen Wochen-Schedule der Airbus A320-Flotte einer europäischen Airline. Die Woche (aus dem Sommerflugplan 2016) wurde seitens der Airline aufgrund des hohen Flugaufkommens als Testwoche empfohlen. Die Flotte umfasst 15 Flugzeuge, die in dieser Woche mehr als 600 Flüge absolviert haben. Die tatsächlich geflogenen Rotationen, die aus historischen Daten bezogen werden, werden als Original-Lösung des vorliegenden Routing-Problems bezeichnet. Der Algorithmus wird mit einer initialen Menge von 30 alternativen Routings begonnen. Diese Routings werden nun bei konstanter Schwarmgröße gemäß den Vorschriften der binären Partikelschwarmoptimierung über 50 Iterationen hinweg miteinander kombiniert. Für jede Iteration ist die geringste, mittlere und höchste Fitness des Schwarms dargestellt. Dabei entspricht der Fitness-Faktor der Summe der Ankunftsverspätungen in allen Rotationen. Ein Abfallen der dargestellten Kurven entspricht daher einer Steigerung der Fitness. Der initiale Schwarm, der willkürlich erzeugt wird, enthält bereits Lösungen, deren Fitness die ebenfalls simulierte Fitness der Original-Lösung übertrifft. Letztere liegt bei rund 4.700 Minuten. Im Verlauf des Algorithmus kann die Fitness kontinuierlich gesteigert werden (dies entspricht einer Reduktion der Summe der Ankunftsverspätungen). Die beste Lösung nach 50 Iterationen weist eine Fitness von rund 3.800 Minuten Ankunftsverspätung auf, was einer Reduktion um 19 % im Vergleich zur Original-Lösung entspricht. Ebenso ist deutlich zu erkennen, dass die Spannweite der Fitnesswerte im Schwarm mit jeder Iteration abnimmt, da sich die Lösungen bei der Partikelschwarmoptimierung abhängig von der jeweils besten Lösung annähern. Dadurch steigt auch die mittlere Fitness des Schwarms stark an. In [5] wird im Detail auf die Implementierung und Auswertung des Algorithmus eingegangen. Darüber hinaus wurde die Möglichkeit implementiert, nicht nur die Flugzeugumläufe, sondern auch die Abflug- und Ankunftszeiten der Flüge eines Schedules zu verändern, um Verspätungen abzubauen. Hierzu werden zunächst alle Flughäfen im Schedule identifiziert, die laut IATA slot-kritisch sind. Derart charakterisierte Flughäfen werden dauerhaft an ihren Kapazitätsgrenzen Bild 3: Verlauf der binären Partikelschwarmoptimierung Bild 2: Test der Simulationsqualität durch Vergleich mit historischer On-Time- Performance Internationales Verkehrswesen (71) 2 | 2019 85 Wissenschaft TECHNOLOGIE betrieben und verfügen über keine Reserven, um etwaige Verspätungen durch Umplanungen zu reduzieren. An diesen Flughäfen dürfen daher weder Abflüge noch Ankünfte verschoben werden. An allen anderen Flughäfen (und dem Hub) wird die Annahme getroffen, dass Veränderungen der Abflug- oder Ankunftszeit um ± fünf Minuten möglich sind. Um Blockzeiten konstant und somit Zeitänderungen kostenneutral zu gestalten, werden in jedem Fall sowohl die Abflugals auch die Ankunftszeit kongruent zueinander verschoben. Gemäß dieser Erweiterung ist das Ziel der Partikelschwarmoptimierung nun, Kombinationen aus Routing- und Timing-Entscheidungen zu finden, die eine besonders hohe Fitness aufweisen. Bild 4 stellt das Verbesserungspotenzial dieses kombinierten Ansatzes im Vergleich zu dem in Bild 3 dargestellten Ansatz dar, bei dem sich nur auf Routing-Entscheidungen konzentriert wird. Dabei zeigt sich, dass der kombinierte Ansatz letztlich eine Gesamtverbesserung von rund 24 % erzielt (gegenüber 19 % beim nichtkombinierten Ansatz). Eine sichtbare Überlegenheit entwickelt der kombinierte Ansatz nach etwa 15 Iterationen. Vor dieser Iteration sind keine deutlichen Unterschiede erkennbar. Die Rechenzeit des Ansatzes auf einem handelsüblichen Notebook (Prozessor: i7, RAM: 32GB) liegt je Tag (ca. 90 Flüge und 15 Rotationen im Mittel) bei ca. 20 Minuten. Zusammenfassung und Diskussion Insgesamt konnte gezeigt werden, dass sich Schedules mit den entwickelten Modellen für Boden- und Blockzeiten zuverlässig simulieren lassen und deren Robustheit in vertretbarem zeitlichem Aufwand mit den angewandten Heuristiken signifikant um bis zu 24 % erhöht werden kann. Die Algorithmen sind für den täglichen Einsatz im Airline-Betrieb ausgelegt, um auch Sekundärverspätungen zu vermeiden. Es können aber weitere, hier nicht beachtete Nebenbedingungen auftreten, die die Effektivität des Algorithmus im täglichen Einsatz mindern können. Zum Beispiel können Vorschriften bezüglich der Crew oder der Flugzeugwartung gewisse Umläufe unmöglich machen. Damit wäre eine so hohe Verspätungsreduzierung, wie in der Studie simuliert, in der Praxis nicht unbedingt reproduzierbar. Dennoch ist die theoretische Anzahl der möglichen Umläufe so groß, dass ein durchführbarer Umlaufplan, der annähernd dem simulierten entspricht, durchaus gefunden werden kann. Man kann von einer signifikanten Verbesserung der Sekundärverspätungen von Fluggesellschaften ausgehen. ■ Das diesem Bericht zugrundeliegende Vorhaben wurde mit Mitteln des Bundesministeriums für Wirtschaft und Energie unter dem Förderkennzeichen 20V1511B gefördert. Die Verantwortung für den Inhalt dieser Veröffentlichung liegt bei den Autoren. LITERATUR [1] Süddeutsche Zeitung (2018): Flugausfälle und Verspätungen nehmen drastisch zu, 28. Juni 2018 [2] https: / / www.bmvi.de/ SharedDocs/ DE/ Artikel/ LF/ gemeinsame-erklaerung.html, Abruf am 21.01.2019 [3] Radde, M.; Lütjens, K.; Gollnick, V. (2017): Analyzing Airline Scheduling Processes based on real Data. Air Transport Research Society Conference 2017, Antwerpen, Belgien [4] Poli, R.; Kennedy, J.; Blackwell, T. (2007): Particle swarm optimization - an overview. Swarm Intelligence, 1(1), 33-57. ISSN: 19353812 [5] Radde, M.; Lang, E.; Lütjens, K. (2018): Binary Particle Swarm Optimization for Solving the Aircraft Routing Problem. 22nd ATRS World Conference, Seoul, Südkorea Marius Radde, M.Sc. DLR Lufttransportsysteme, Hamburg marius.radde@dlr.de Eva Lang Senior Data Scientist, ZeroG eva@zerog.aero Katrin Kölker, Dipl.-Math. DLR Lufttransportsysteme, Hamburg katrin.koelker@dlr.de Klaus Lütjens, Dipl.-Vw. DLR Lufttransportsysteme, Hamburg klaus.luetjens@dlr.de Judith Semar Product Manager NetLine, Lufthansa Systems judith.semar@lhsystems.com Volker Gollnick, Univ. Prof. Dr.-Ing. DLR Lufttransportsysteme, Hamburg volker.gollnick@dlr.de Bild 4: Verlauf der binären Partikelschwarmoptimierung mit kombinierten Routing- und Timing-Entscheidungen