Eine bodenständige Lösung: Anwendung eines robusten Simulations-Optimierungsansatzes zur Lösung von Problemen in der Luftfahrt

Die Herausforderung

von Paolo Scala und Miguel Mujica (Hochschule für angewandte Wissenschaften Amsterdam) und Daniel Delahaye (Ecole Nationale de l'Aviation Civile)

Vorgestellt auf der Winter Simulation Conference 2017

Dieser Beitrag befasst sich mit der Verbesserung der Robustheit von heuristischen Lösungen für Luftfahrtsysteme, die von Unsicherheit betroffen sind, wenn die Lösung von Konflikten implementiert wird. Es wird ein Rahmenwerk beschrieben, das die Verwendung von Optimierung und Simulation umfasst, die wiederum pseudo-optimale Zeitpläne erzeugt. Die anfängliche Lösung wird schrittweise verbessert, indem die Unsicherheit in den generierten Lösungen iterativ bewertet und in Übereinstimmung mit der Zielfunktion kalibriert wird. Die Simulation dient dazu, die Durchführbarkeit einer von einem Optimierungsalgorithmus generierten Lösung in einem von Unsicherheit geprägten Umfeld zu testen. Die Ergebnisse zeigen, dass die Methodik in der Lage ist, die Lösungen für die Szenarien mit Unsicherheit zu verbessern, so dass sie ausgezeichnete Kandidaten für die Umsetzung in realen Umgebungen sind.

Einleitung

Flughafensysteme werden als kritische Infrastrukturen betrachtet, die die Konnektivität und den Wert einer Region fördern und den Schlüssel zur Förderung der globalen Interaktion zwischen verschiedenen Ländern, Industrien und Menschen darstellen. Aus diesem Grund stellt das erwartete Wachstum eine Bedrohung für die derzeitigen Einrichtungen dar und es sollte nicht wünschenswert sein, das Wachstum durch die technischen Grenzen der Einrichtungen zu begrenzen. Darüber hinaus ist der Flughafen eine Verbindung von Elementen und Prozessen, die geeignete Werkzeuge für eine effiziente Verwaltung erfordern. Der Flughafenbetrieb kann in einen landseitigen und einen luftseitigen Betrieb unterschieden werden, wobei der landseitige Betrieb innerhalb der Terminals und der luftseitige Betrieb außerhalb der Terminals stattfindet. Bei den landseitigen Abläufen können die Passagiere als Entitäten und die Abfertigungsschalter, Gates oder sogar Freizeiteinrichtungen wie Geschäfte und Cafés als Ressourcen identifiziert werden. Bei den luftseitigen Vorgängen können die Flugzeuge als Entitäten und die Bodenabfertigung, die Start- und Landebahnen, die Rollwege und die Luftraumsektoren, um nur einige davon zu nennen, als Ressourcen identifiziert werden. Aus dieser Klassifizierung geht hervor, dass im Flughafensystem zwei Teilsysteme identifiziert werden, die sich stark voneinander unterscheiden und von einer völlig anderen Dynamik und Logik gesteuert werden. Außerdem interagieren diese beiden unterschiedlichen Teilsysteme miteinander und beeinflussen sich gegenseitig in ihrer Leistung. Die zuvor beschriebenen Merkmale eines Flughafensystems entsprechen also der zu Beginn dieses Abschnitts gegebenen Definition komplexer Systeme, und daher sollten Flughafensysteme bei ihrer Analyse als komplexe Systeme betrachtet werden. Ein weiteres Element, das Luftfahrtsysteme charakterisiert, ist die Stochastik. Luftfahrtsysteme sind von Natur aus stochastisch, und aus diesem Grund ist die Simulation eine Schlüsseltechnik, um den erforderlichen Einblick zu erhalten und die Vorhersagbarkeit zu erhöhen. Darüber hinaus ist die Luftfahrt in hohem Maße von Zeitplänen abhängig, was ihre Probleme ebenfalls für den Einsatz von Optimierungstechniken anfällig macht. Praktiker haben jedoch erkannt, dass Optimierungsverfahren allein nicht ausreichen, um Kapazitätsprobleme zu lösen (Scala, Mujica und Delahaye 2016). In diesem Zusammenhang ist ein grundlegendes Konzept zu berücksichtigen, nämlich die Robustheit von Lösungen aus Optimierungsmodellen. Aufgrund der Variabilität des Systems kann eine von einem Optimierungsmodell gelieferte Lösung mehrere Szenarien mit Unsicherheiten abdecken, so dass eine Lösung als robust definiert wird, wenn sie auf weitere unsichere Szenarien angewendet werden kann, ohne dass sich die Leistung wesentlich ändert.

In der Literatur gibt es viele Arbeiten, die sich mit der Robustheit von Lösungen für Luftfahrtprobleme befassen. Das Ergebnis dieser Arbeiten ist die Entwicklung vieler Werkzeuge und Methoden. Chandran und Balakrishnan (2007) schlugen einen dynamischen Programmieralgorithmus für die robuste Planung von Start- und Landebahnen vor. In ihrer Arbeit berücksichtigten sie Unsicherheiten bei den Ankunftszeiten der Flugzeuge und fanden einen Kompromiss zwischen dem Durchsatz auf der Start- und Landebahn und der Wahrscheinlichkeit einer Verletzung des Mindestabstands auf der Start- und Landebahn als Ziel. Kim und Feron (2011) befassten sich mit dem Problem der robusten Gate-Zuweisung, wenn stochastische Verspätungen eingeführt werden. Sie definierten die Robustheit als das Zeitintervall zwischen zwei Flugzeugen, die am selben Gate parken, d.h. je größer das Intervall ist, desto robuster ist die Lösung. Sie berechneten die Anzahl und das Ausmaß der gestörten Zuweisungen und lösten das Problem mit Hilfe eines linearen gemischten 0-1-Optimierungsmodells und der Tabu-Search-Meta-Heuristik, die im Vergleich zum ursprünglichen Zeitplan eine Verbesserung der Anzahl und des Ausmaßes der gestörten Zuweisungen von 92 % bzw. 95 % ergab. In der Arbeit von Arias, Guimarans, Mujica und Boosten (2013) wird das stochastische Flugzeugbergungsproblem durch die Anwendung des Paradigmas der Constraint-Programmierung in Kombination mit Simulationstechniken gelöst. Die Robustheit der Lösungen wird durch den Vergleich der Standardabweichung der simulierten Ergebnisse mit der Variation der Wahrscheinlichkeitsverteilung, die für die Erzeugung der stochastischen Verspätungen verwendet wird, und ihrer erwarteten Ausbreitung aufgrund der Problemgröße bewertet. In der Dissertation von Lee (2014) wurde das Problem der Überlastung der Flughafenoberflächen angegangen. In seiner Arbeit verwendete er die Optimierung für die Planung von Start- und Landebahnen und Rollwegen und anschließend die stochastische Simulation, um mit Unsicherheiten umzugehen. Narciso und Piera (2015) betrachteten das Problem der robusten Zuweisung von Flugsteigen und schlugen ein kausales Modell vor, das den Formalismus der farbigen Petri-Netze (CPN) verwendet, um die minimale Anzahl von Flugsteigen zu ermitteln, die für die Aufnahme des Verkehrs erforderlich ist.

Der Schwerpunkt dieses Papiers liegt auf der Verbesserung der Robustheit, wie sie zuvor definiert wurde, für Lösungen, die aus Optimierungsmodellen stammen, die durch Meta-Heuristiken gelöst wurden. Die Methodik ist iterativ und zielt darauf ab, Lösungen zu finden, die am besten in ein System passen, das von Unsicherheiten betroffen ist. In diesem Beitrag wird eine Anwendung dieser Methodik auf das Problem der Erkennung und Lösung von Flughafenkonflikten vorgestellt. Die Ergebnisse bestätigen, dass es nach zwei Iterationen möglich ist, durch Änderung der Parameter des Algorithmus, der für die Lösung dieses Problems implementiert wurde, eine Verbesserung der ursprünglichen Lösung zu erzielen. Der Beitrag ist wie folgt aufgebaut: In Abschnitt 2 wird das in diesem Beitrag behandelte Problem beschrieben, in Abschnitt 3 wird die Methodik zusammen mit der Beschreibung der Optimierung und des Simulationsmodells vorgestellt. In Abschnitt 4 wird die Implementierung der Methodik für das Problem der Erkennung und Lösung von Flughafenkonflikten gezeigt, und im selben Abschnitt werden die Ergebnisse dargestellt und diskutiert. Im letzten Abschnitt werden Schlussfolgerungen und zukünftige Arbeiten vorgestellt.

Problembeschreibung

Heutzutage befinden sich viele europäische Flughäfen am Rande ihrer Kapazitätsgrenzen, was auf das schnelle Wachstum des Luftverkehrs in den letzten Jahren zurückzuführen ist. Darüber hinaus wurde für die kommenden Jahre ein Anstieg des Luftverkehrs prognostiziert (Airbus 2016), weshalb in einem zukünftigen Szenario mit potenzieller Überlastung Lösungen zur Überwindung dieses Problems gefunden werden müssen. Eine Überlastung des Flughafens wird vor allem innerhalb des Luftraums, in der Terminal Manoeuvring Area (TMA) und am Boden in der Nähe der Start- und Landebahneinfahrt festgestellt. Der TMA ist ein Teil des Luftraums, der die Flughäfen umgibt; hier laufen die landenden Flugzeuge auf der Luftseite des Flughafens zusammen. Ein gutes Management der Ankunfts- und Abflugrate durch die Fluglotsen kann den Flughafen, den Luftraum und die Bodenseite, von potenziellen Überlastungssituationen entlasten und gleichzeitig den Durchsatz der Start- und Landebahn erhöhen (Frankovich 2012). Das in dieser Arbeit betrachtete Problem der Erkennung und Lösung von Flughafenkonflikten bezieht sich auf die Sequenzierung des Flugzeuglandeflusses und die Verwaltung der Bodenkapazität. Bei diesem spezifischen Problem werden Konflikte im Luftraum aufgrund von Einschränkungen der Mindestabstände und am Boden aufgrund von Kapazitätsüberlastungen erkannt. In den nächsten Abschnitten werden die Konflikte für den Luftraum, die Start- und Landebahnen und die Bodenkomponenten näher beschrieben. Ziel der Lösung dieses Problems ist es, die Sicherheit des Luftverkehrsflusses im Luftraum zu gewährleisten, indem die Luftraumkonflikte auf Null reduziert werden, und die Kapazitätsüberlastungen am Boden zu verringern. Weitere und detailliertere Informationen zu diesem Problem finden Sie in Ma, Delahaye und Sbihi (2016).

Luftraum- und Startbahnkonflikte

Was den Luftraum betrifft, so besteht das Hauptziel bei einigen Landestrecken, die an einem Endpunkt (Initial Approach Fix - IAF) zusammengeführt werden (siehe Abbildung 1), und einer Reihe von landenden Flugzeugen darin, die Reihenfolge der Flugzeuge so zu gestalten, dass sie am IAF zusammengeführt werden, ohne dass es zu Verstößen gegen das Trennungsminimum kommt. In Bezug auf die Start- und Landebahnen werden Konflikte erkannt, wenn der Abstand zwischen zwei aufeinanderfolgenden Flugzeugen, die die Start- und Landebahn überqueren, geringer ist als die erforderlichen Mindestabstände. Die Mindeststaffelungswerte werden für die verschiedenen Start- und Landebahnoperationen festgelegt, d. h. für Anflüge (Startbahn einwärts) und Abflüge (Startbahn auswärts), und basieren auf der Wirbelschleppenkategorie des vorausfliegenden und des nachfolgenden Flugzeugs. Die Mindestabstände für den Luftraum sind in den ICAO-Normen (ICAO 2007) festgelegt, die Mindestabstände für die Start- und Landebahn stammen von Frankovich (2012).

Bodenkonflikte

Was den Bodenbetrieb betrifft, so ist das entwickelte Modell ein High-Level-Modell, was bedeutet, dass der Bodenbetrieb nicht im Detail modelliert wird. Daher werden zunächst die Hauptkomponenten des Bodens identifiziert und dann wird jeder von ihnen eine Kapazität zugewiesen. Die wichtigsten Bodenkomponenten sind Rollbahnen und Terminals. Die Kapazität ist definiert als die Anzahl der Flugzeuge, die gleichzeitig eine der Komponenten nutzen. Sobald die Flugzeuge gelandet sind und die Start- und Landebahn verlassen haben, überqueren sie die Rollbahn, bis sie am Flugsteig parken. Wie bereits erwähnt, handelt es sich bei dem Modell des Geländes um ein übergeordnetes Modell, was bedeutet, dass die Rollwege nicht im Detail berücksichtigt wurden; daher wurde der Rollwegbetrieb anhand der durchschnittlichen Fahrzeit modelliert. Die Abfertigungszeiten wurden auf der Grundlage eines realen Flugplans ermittelt, und die Fahrzeit auf dem Rollweg vom Flugsteig bis zur Einfahrt in die Start- und Landebahn wurde anhand der durchschnittlichen Fahrzeit berücksichtigt. Ziel ist es, die Kapazität dieser Komponenten nicht zu überschreiten. Konflikte werden in diesem Fall durch die Summe aus maximaler Kapazitätsüberlastung und durchschnittlicher Kapazitätsüberlastung dargestellt. Tabelle 1 zeigt die Kapazität der wichtigsten Bodenkomponenten in Bezug auf das in dieser Arbeit betrachtete Beispiel.

Tabelle 1: Kapazität der wichtigsten Bodenkomponente.

Die Lösung

Rahmenwerk

Der Rahmen, der in diesem Abschnitt vorgestellt wird, ist die Kombination eines auf einem gleitenden Fenster basierenden Optimierungsmodells mit einem auf einer diskreten Ereignissimulation basierenden Modell, um den oben genannten Anwendungsbereich zu erreichen. Im weiteren Verlauf dieses Abschnitts wird die Struktur der Methodik vorgestellt, und anschließend werden sowohl der Optimierungsprozess als auch die Simulationsumgebung näher beschrieben.

Beschreibung der Methodik

Die in diesem Papier vorgeschlagene Methodik kann durch zwei Hauptschritte dargestellt werden, wie in Abbildung 2 gezeigt wird. Im ersten Schritt wird das zu untersuchende System einem Optimierungsprozess unterzogen, mit dem Ziel, optimale oder suboptimale Lösungen entsprechend einer bestimmten Zielsetzung zu erhalten. In dieser Arbeit wird diese Methodik auf das Problem der Erkennung und Lösung von Flughafenkonflikten angewandt, wobei das Ziel der Studie darin besteht, ein Szenario ohne Konflikte zu erreichen. Da der Optimierungsprozess zu einer exakten Lösung führt, bei der die meisten Betriebsparameter deterministisch sind, ist es wahrscheinlich, dass diese Lösung, wenn sie in einer realen Umgebung getestet wird, empfindlich auf geringfügige Änderungen aufgrund von Systemvariabilität reagieren wird. Im zweiten Schritt der Methodik wird die Simulation eingesetzt, um die Variabilität des Systems einzuführen und die Robustheit der durch den Optimierungsprozess bereitgestellten Lösung zu testen. In der Simulationsumgebung dürfen einige relevante Parameter, die sich in der Realität auf die Lösung auswirken, unsichere Werte haben. Diese Methode ist iterativ, was bedeutet, dass diese beiden Schritte so lange angewendet werden, bis die Robustheit bis zu einem bestimmten Zufriedenheitsgrad verbessert wird, der die Abbruchbedingung des iterativen Prozesses darstellt. In dieser Arbeit wird die Robustheit als die Abweichung der Leistung der simulierten Lösung vom idealen Szenario gemessen, wobei die Leistung als Anzahl der Konflikte bewertet wird und das ideale Szenario eine Lösung ist, die null Konflikte ergibt. In diesem Zusammenhang ist die Robustheit verbessert, wenn diese Abweichung minimiert wird.

Optimierungsprozess

Der Optimierungsprozess, der in dieser Methodik und speziell für das Problem der Erkennung und Lösung von Flughafenkonflikten angewandt wurde, basiert auf einem Gleitfensteransatz. Die Hauptvorteile dieser Methode bestehen darin, dass die Teilprobleme einfacher zu lösen sind und weniger Rechenzeit benötigen, und dass das Problem dynamisch angegangen wird, indem die Entscheidungsvariablen aktualisiert werden, während das Fenster entlang des Zeithorizonts gleitet, was zu einer Verbesserung der Lösungsqualität führt. Dieser Ansatz wurde bereits bei ähnlichen Problemen eingesetzt und hat gute Ergebnisse geliefert (Hu und Chen 2005, Zhan, Zhang, Li, Liu, Kwok, Ip und Kaynak 2010, Furini, Kidd, Persiani und Toth 2015, Toratani, Ueno und Higuchi 2015, Man, Delahaye und Xiao-hao 2015, Ma, Delahaye, Sbihi und Mongeau 2016). Bei diesem Ansatz wird jedes Objekt (Flugzeug) entsprechend seiner Position relativ zum aktuellen Fenster mit einem bestimmten Status verknüpft. Folglich kann der Status eines Objektsvollständigsein, wenn es sich außerhalb des aktuellen Fensters befindet;laufend, wenn sich das Objekt zwischen dem vorherigen und dem aktuellen Fenster befindet;aktiv, wenn sich das Objekt innerhalb des aktuellen Fensters befindet;geplant, wenn sich das Objekt im nächsten Fenster befindet. Im aktuellen Fenster werden Entscheidungen nur für die Entitäten mit laufendem und aktivem Status getroffen, während sie für die abgeschlossenen Entitäten bereits getroffen wurden. Für die geplanten Entitäten werden die Entscheidungen im nächsten Fenster getroffen (siehe Abbildung 3).

Die wichtigsten Parameter des Sliding-Window-Ansatzes sind die Fenstergröße und die Shift-Größe. Sie beeinflussen die Leistung des Optimierungsprozesses in Bezug auf die Rechenzeit und die Qualität der Lösung, so dass es entscheidend ist, diese beiden Parameter mit den richtigen Werten einzustellen, um gute Lösungen zu erhalten. Ein kleines Fenster führt zur Lösung kleiner Teilprobleme, wobei einige Fluginformationen möglicherweise nicht berücksichtigt werden. Ein großes Fenster führt zur Lösung größerer Probleme, aber gleichzeitig können einige Fluginformationen zu früh berücksichtigt werden. In beiden Fällen wird die Effektivität der Lösung beeinträchtigt. Eine kleine Verschiebung führt dazu, dass viele Entscheidungsvariablen bei jeder Fensterverschiebung aktualisiert werden, eine große Verschiebung führt dazu, dass mehr Entscheidungsvariablen festgelegt und weniger Entscheidungsvariablen bei jeder Fensterverschiebung aktualisiert werden, was die Leistung des Algorithmus beeinträchtigt.

Der Lösungsraum dieses Problems gilt als NP-hart (Beasley, Krishnamoorthy, Sharaiha und Abramson 2000), was den Einsatz einer Meta-Heuristik rechtfertigt, um das Problem zu lösen und eine (sub)optimale Lösung zu erhalten. Zu diesem Zweck wurde jedes Teilproblem, das durch den Sliding-Window-Ansatz definiert wurde, mit Hilfe der Meta-Heuristik des Simulated Annealing gelöst (Kirkpatrick, Gelatt und Vecchi 1983). Diese Meta-Heuristik hat sich bei der Behandlung ähnlicher Probleme als sehr effizient erwiesen (Man, Delahaye und Xiao-hao 2015, Ma, Delahaye, Sbihi und Mongeau 2016). Die Definitionen und detaillierten Erklärungen des Sliding-Window-Ansatzes und der Meta-Heuristik liegen außerhalb des Rahmens dieses Papiers. Für detailliertere Informationen und ein besseres Verständnis dieses Optimierungsverfahrens, das auf diese spezielle Art von Problem angewandt wird, wird auf Ma, Delahaye und Sbihi (2016) verwiesen.

Simulationsumgebung

Die diskrete Ereignissimulation (DES) wurde zur Bewertung der Auswirkungen der Ungewissheit in den vom Optimierungsalgorithmus vorgeschlagenen Lösungen in den Kreislauf eingebunden. In diesem Abschnitt werden die Vorteile der Verwendung der Simulation für diesen Zweck beschrieben. Der Einsatz von DES erlaubt es, die Ungewissheit in die Szenarien einzubeziehen, was mit anderen Techniken nicht möglich oder sehr kompliziert ist. In diesem Zusammenhang macht die Einführung der Unsicherheit mit der Simulation die Situation näher an der Realität und mit der Definition der Robustheit ist es möglich, eine Lösung zu erreichen, die vielleicht nicht mathematisch optimal ist, aber widerstandsfähiger gegen Störungen im realen System. DES wird bereits seit den letzten Jahrzehnten in vielen Bereichen eingesetzt, von der Fertigung bis zum Transportwesen, und hat sich als nützlich für Was-wäre-wenn-Analysen, Szenariotests und als Entscheidungshilfe erwiesen (Banks 1998, Brunner, Cross, McGhee, Levis und Whitney 1998, Negahban und Smith 2014). Bei DES vergeht die Zeit entsprechend dem Auftreten bestimmter Ereignisse, und die Abfolge der Handlungen, die die Entitäten vornehmen, ist bereits im Voraus bekannt. Die Verwendung dieses Modellierungsansatzes ist besser als andere, wie z. B. agentenbasierte oder systemdynamische Ansätze, da die modellierten Prozesse sequenziellen Abläufen folgen, die unter diesem Paradigma angemessen modelliert werden können. Andere Ansätze, wie z. B. der agentenbasierte Ansatz, eignen sich eher für Situationen, in denen die modellierten Entitäten mehr Freiheitsgrade haben und es notwendig ist, die Logik hinter dem Entscheidungsfindungsprozess, den die Entitäten durchlaufen, zu implementieren. In dem System, das in dieser Arbeit modelliert wird, ist dies nicht erforderlich, was uns einen flexibleren, leichter zu wartenden und schnelleren Rahmen gibt, als der, der mit einer anderen Technik erreicht werden kann.

Umsetzung

Die in Abschnitt 3.1 vorgestellte Methodik wurde auf das Problem der Erkennung und Lösung von Flughafenkonflikten angewandt. In den nächsten Abschnitten werden die wichtigsten Parameter des Simulations- und Optimierungsmodells und zwei Iterationen der Methodik mit den entsprechenden Ergebnissen vorgestellt.

Parameter der Methodik

Die Parameter dieser Methode lassen sich in drei Gruppen einteilen: kontrollierbare Parameter, Randparameter und stochastische Parameter. Die ersten beziehen sich auf Parameter, die mit dem untersuchten Problem zusammenhängen und daher problemspezifisch sind. Die Randparameter beziehen sich auf den Optimierungsprozess selbst, sie hängen also von der Art der Optimierung ab. Die steuerbaren Parameter sind Teil des Optimierungsmodells, da sie die Entscheidungsvariablen des Problems darstellen. Stochastische Parameter stellen die Quellen der Stochastizität des Systems dar und hängen daher von dem untersuchten System ab. In den folgenden Abschnitten werden diese Parameter vorgestellt und diskutiert. Die steuerbaren Parameter und die Randparameter sind sehr wichtig, da sie die treibenden Kräfte bei der Umsetzung der Methodik sind. Jede Iteration der Methodik basiert auf einer anderen Einstellung dieser Parameter. Stochastische Parameter werden durch das Simulationsmodell implementiert, was zu Schlüsselfaktoren für die Güte der Methodik führt. Es ist wichtig, sie richtig auszuwählen und zu kalibrieren; in dieser Arbeit wurde eine erste Schätzung für sie vorgenommen.

Steuerbare Parameter und Randbedingungen

Die in dieser Arbeit betrachteten kontrollierbaren Parameter des Problems der Erkennung und Lösung von Flughafenkonflikten sind:

• Eintrittsgeschwindigkeit in den Luftraum: Erhöhung oder Verringerung der Geschwindigkeit des Flugzeugs beim Eintritt in den Luftraum für den Endanflug.
• Eintrittszeit in den Luftraum: Verzögerung oder Vorverlegung des Eintritts von Flugzeugen in den Luftraum für den Endanflug.
• Pushback-Zeit: Verzögerung von Flugzeugen an ihren Gates, bevor sie zum Abflug starten.

Die Randparameter beziehen sich auf die Parameter des Schiebefensters:

• Fenstergröße: Festlegung der Größe für jedes vom Algorithmus gelöste Teilproblem.
• Verschiebungsgröße: Definiert die Größe der Verschiebung für das Fenster und damit die Anzahl der Entscheidungsvariablen, die für jedes Teilproblem aktualisiert werden.

In Tabelle 2 sind die steuerbaren Parameter und die Randparameter mit ihren jeweiligen Werten, die für die erste optimierte Lösung verwendet wurden, zusammengefasst. Beachten Sie, dass die Werte der Parameter Eintrittszeit in den Luftraum und Pushback-Zeit in 5-Sekunden-Intervallen diskretisiert sind, während die Eintrittsgeschwindigkeit in den Luftraum in 1-Prozent-Intervallen diskretisiert ist. Die Optimierungsparameter sind kontinuierlich.

Stochastische Parameter

Die stochastischen Parameter des in dieser Arbeit betrachteten Problems der Erkennung und Lösung von Flughafenkonflikten sind:

Tabelle 2: Kontrollierbare Parameter und Randbedingungen.

• Abweichung von der Einflugzeit in den Luftraum
• Abweichung von der Rollbahnfahrzeit
• Abweichung von der Pushback-Zeit

In Tabelle 3 sind die stochastischen Parameter mit ihren jeweiligen im Simulationsmodell verwendeten Werten zusammengefasst. Beachten Sie, dass die stochastischen Parameter kontinuierlich sind.
Tabelle 3: Stochastische Parameter.

Experimente

Die in dieser Arbeit vorgeschlagene Methode wurde auf das Problem der Erkennung und Lösung von Flughafenkonflikten angewandt, wobei zwei Iterationen der Methode vorgestellt werden. Zu Beginn wird eine Lösung präsentiert, die den ursprünglichen Zeitplan darstellt, dann wird eine andere Lösung, diesmal unter Anwendung des Optimierungsprozesses, präsentiert und die beiden Lösungen werden miteinander verglichen. Nachdem durch den Optimierungsalgorithmus eine optimierte Lösung gefunden wurde, wird die Unsicherheit mit dem Simulationsmodell eingeführt, wobei 50 Replikationen für jeden Lauf durchgeführt wurden. Die Ergebnisse der Simulation werden dann analysiert, um die Robustheit der optimierten Lösung zu testen. Auf die gleiche Weise wurde eine zweite Iteration durchgeführt, bei der das Optimierungsmodell unter Änderung einiger der in 4.1.1 vorgestellten Methodikparameter ausgeführt und dann die neu generierte Lösung mit dem Simulationsmodell getestet wurde. Der ursprüngliche Zeitplan basiert auf den realen Verkehrsdaten eines Tages (7. Februar 2016) am Flughafen Paris-Charles de Gaulle, da sowohl das Optimierungs- als auch das Simulationsmodell den Betrieb dieses speziellen Flughafens modelliert haben. In den folgenden Diagrammen werden die Ergebnisse des ursprünglichen Plans veranschaulicht. Sie zeigen viele Konflikte für den Luftraum, die Start- und Landebahnen und eine große Kapazitätsüberlastung des Rollwegenetzes und der Terminals.

Die Konflikte im Luftraum und auf den Start- und Landebahnen wurden auf stündlicher Basis berechnet, so dass ersichtlich ist, in welchem Teil des Tages sie konzentriert sind. Abbildung 4(a) zeigt, dass die Konflikte im Luftraum zu den Spitzenzeiten um 8, 9, 12, 13 und 20 Uhr auftreten und zwischen 80 und 90 Konflikte umfassen. Was die Konflikte auf den Start- und Landebahnen (in und out) angeht, so zeigen die Abbildungen 4(b) und 4(c), dass es hier viele Konflikte gibt. In der Tendenz der Start- und Landebahnkonflikte gibt es Spitzen zwischen 8 und 10 Uhr sowie um 20 Uhr, in der Tendenz der Start- und Landebahnkonflikte gibt es Spitzen zwischen 11 und 12 Uhr sowie um 14 Uhr.

Bei den Rollkonflikten ist in Abbildung 5(a) zu erkennen, dass die Kapazität, die mit 18 angesetzt ist, von 9 bis 14 Uhr und von 19 bis 21 Uhr überlastet ist, mit einer maximalen Spitze von 25 um 21 Uhr. Abbildung 5(b) zeigt die Belegung für die drei betrachteten Terminals, wobei insbesondere für das Terminal 1 (Kapazität 11) eine konstante Überlastung von 6 bis 21 Uhr besteht.

Erste Iteration

Gemäß dem methodischen Vorgehen wird im ersten Schritt jeder Iteration das Optimierungsmodell ausgeführt und daraus eine optimierte Lösung ermittelt. In diesem Fall wurde nach der Ausführung des Optimierungsmodells ein Szenario mit null Konflikten sowohl für die Luftraum- als auch für die Bodenkomponenten gefunden. Die Abbildungen 6(a) und 6(b) zeigen

die Belegungsentwicklung während des Tages für das Rollwegenetz und die Terminals, wobei festzustellen ist, dass es keine Kapazitätsüberlastung gibt.

Die erste Iteration ist abgeschlossen, wenn die optimierte Lösung im Simulationsmodell ausgeführt wird; in Abbildung 7 sind die stündlichen Konflikttrends für Luftraum und Start- und Landebahnen dargestellt.

Bei Einbeziehung der Unsicherheit ist zu erkennen, dass trotz der Optimierungslösung, die ein konfliktfreies Szenario ergibt, neue Konflikte auftreten. Speziell für den Luftraum gibt es eine Spitze von 5 durchschnittlichen stündlichen Konflikten um 9 Uhr, und einige andere Konflikte verteilen sich über den Tag (siehe Abbildung 7(a)). Für die Start- und Landebahn in ist zu erkennen, dass sie von der Unsicherheit nicht sehr betroffen ist, da die durchschnittliche stündliche Konfliktspitze bei fast 2 liegt (siehe Abbildung 7(b)). Die Start- und Landebahn ist dagegen stärker von der Unsicherheit betroffen, hier gibt es viele durchschnittliche stündliche Konfliktspitzen während des Tages, 10 zwischen 11 und 12 Uhr, 12 zwischen 14 und 15 Uhr und 9 um 22 Uhr (siehe Abbildung 7(c)). Was die Überlastung der Bodenkomponente betrifft, so waren die Terminals von der Unsicherheit nicht betroffen, da es für sie keine Kapazitätsüberlastung gab; die durchschnittliche maximale Kapazitätsüberlastung der Rollwege betrug 2,05.

Zweite Iteration

Eine zweite Iteration wird durchgeführt, da die Ergebnisse der ersten Iteration das Vorhandensein von Konflikten nach der Einbeziehung von Unsicherheiten zeigten. In dieser zweiten Iteration wurde das Optimierungsmodell ausgeführt, wobei einige der kontrollierbaren oder begrenzten Parameter angepasst wurden, um eine neue Lösung zu erhalten, die mit dem Simulationsmodell getestet werden kann. In diesem Fall wurde bei der Ausführung des Optimierungsmodells eine neue Lösung erzielt, indem die Fenstergröße des Gleitfenster-Optimierungsansatzes von einem Fenster von 3 Stunden auf ein Fenster von 2 Stunden geändert wurde. Diese Entscheidung wurde damit begründet, dass der Algorithmus bei einer zu großen Fenstergröße häufig die Informationen einiger Flüge, die im Zeitplan weit voraus sind, zu früh berücksichtigt, was zu einem Verlust der dynamischen

Vorteil des Ansatzes, der sich auf die Qualität der Lösung auswirkt. Das Testen einer kleineren Fenstergröße könnte also zu einer robusteren Lösung führen. Die Ergebnisse der neuen Lösung sind in Tabelle 4 dargestellt.

Tabelle 4: Ergebnisse der Optimierung, zweite Iteration.

Wie man sieht, bietet diese Lösung ein fast konfliktfreies Szenario, da einige Konflikte für die Start- und Landebahnen und für die Terminals auftreten. Unter dem Gesichtspunkt der Optimierung ist diese Lösung also nicht optimal, sondern suboptimal. In den Abbildungen 8(a), 8(b) und 8(c) sind die Ergebnisse dargestellt, die nach der Prüfung dieser Lösung mit Hilfe des Simulationsmodells erzielt wurden. In Abbildung 8(a) ist zu erkennen, dass die drei Spitzenwerte von 4, 5 und 7 Konflikten pro Stunde im Luftraum um 6, 10 bzw. 12 Uhr erreicht werden. Für die Start- und Landebahn in sind in Abbildung 8(b) zwei Spitzenwerte von 1,6 und 2,1 Konflikten pro Stunde um 8 bzw. 12 Uhr zu erkennen. Die Ergebnisse für die Start- und Landebahn "out" weisen nur einen Spitzenwert von 14 durchschnittlichen stündlichen Konflikten um 14 Uhr auf.

In Tabelle 5 sind die Ergebnisse der beiden Iterationen zusammengefasst. Betrachtet man die zweite und dritte Spalte im Vergleich zur ersten und zweiten Iteration, so ist festzustellen, dass die zweite Iteration die durchschnittlichen Konflikte auf der Start- und Landebahn von 89,9 auf 85,32 verbessert, während die durchschnittlichen Luftraumkonflikte nicht verbessert werden. Die Werte der anderen Komponenten, Start- und Landebahn innen, Rollbahn und Terminals, sind zwischen der ersten und zweiten Iteration stabil.

Das erwartete Ergebnis der Methodik sollte darin bestehen, dass die Anzahl der Konflikte nach jeder Iteration schrittweise abnimmt und gleichzeitig eine Lösung erreicht wird, bei der die Konflikte zwischen allen Komponenten ausgeglichen sind.

Tabelle 5: Vergleich zwischen den Ergebnissen der beiden Iterationen.

die Komponenten. In diesem Fall ist nach zwei Iterationen festzustellen, dass für einige Teile der Systeme, insbesondere für die Start- und Landebahn, Verbesserungen erzielt wurden, während die Methodik für den Luftraum keine Verbesserungen bewirken konnte. Was die Bodenkomponenten betrifft, so bestätigten die Ergebnisse, dass sie kaum von der Variabilität betroffen sind, was bedeutet, dass sie gut vorhergesagt werden können. Die Interpretation der Ergebnisse nach zwei Iterationen, wenn die Gesamtleistung des Flughafensystems betrachtet wird, zeigt jedoch, dass die Lösung der zweiten Iteration ausgewogener ist als die Lösung der ersten Iteration, was eine Verbesserung in Bezug auf die Robustheit darstellt. Es wird erwartet, dass weitere Iterationen dieser Methode zu einer noch besseren Robustheit der Lösungen führen werden.

Die Auswirkungen auf das Unternehmen

Fazit und weitere Schritte

In diesem Beitrag wurde ein Rahmen für die Verbesserung der Robustheit von optimierten Lösungen für das Problem der Erkennung und Lösung von Konflikten auf Flughäfen vorgestellt. Die Ergebnisse zeigen die Durchführbarkeit des Konzepts der Kombination der beiden Methoden zur Bereitstellung robusterer Lösungen. Es wurde bestätigt, dass Unsicherheiten bei der Anwendung auf eine optimierte Lösung sehr störend sind. Luftraum- und Startbahnkonflikte waren am stärksten betroffen, nachdem die Variabilität in das System einbezogen wurde, während die Bodenkomponenten weniger empfindlich darauf reagierten. Die iterativ umgesetzte Methode konnte die Konflikte für die Start- und Landebahn verringern, war jedoch bei den Konflikten im Luftraum nicht sehr effektiv. Im Allgemeinen erreichte die Methode nach zwei Iterationen eine ausgewogenere Lösung. Weiter zu diskutieren wäre, wie ein zyklischer Ansatz umgesetzt werden kann, damit wir die Robustheit der durch die Kombination der beiden Ansätze erzielten Lösung feinabstimmen können. Weitere Studien können zur Wahl der Parameter durchgeführt werden, die bei jeder Iteration angepasst werden müssen, um sie effektiver und effizienter zu machen. Ein weiterer Aspekt, der als zukünftige Entwicklung der Methodik untersucht werden kann, ist die Wahl der Werte für die stochastischen Parameter, die beispielsweise durch die Verarbeitung historischer Daten erfolgen kann.

DANKSAGUNGEN

Die Autoren danken der Aviation Academy der Fachhochschule Amsterdam sowie der Dutch Benelux Simulation Society und EUROSIM für die Verbreitung der Ergebnisse dieser Arbeit.