Robuste Optimierungsmodelle für den Flugverkehr

In this work, we study the runway scheduling problem from a mathematical modeling and optimization point of view. We consider exclusively the tactical planning phase, which is about two hours before arrival/ departure to touch-down/ take-off. Furthermore, a simulation environment was developed. The task of the runway scheduling problem is to optimally schedule a set of arriving and departing aircraft with given earliest, schedule and latest times. The aircraft have different weight classes and minimum separation times have to hold between two consecutive aircraft, which depend on the weight classes of both predecessor and follower. With the help of mathematical models and solution algorithms, we try to end an optimal sequence for the aircraft under different aspects. This work is tripartite. The first part considers the nominal runway scheduling problem without explicitly incorporating the knowledge of uncertainty. We analyze two different mathematical optimization models, which are structurally different. To this end we compare these mathematical models with different algorithms from the German Aerospace Center (DLR) using real-world as well as random data. In the second part, we take uncertainty and disturbances into account, which often occur in the Air Traffic Management (ATM) context. Before starting with modeling, we give a definition for robustness in ATM. According to this, we are interested in robust optimization models, which integrate the structure of uncertainty into our planning and protects against uncertainty. Thereby, strict robust approaches are applied, which immunize to 100% against predefined uncertainties. Nevertheless, with increasing the protection, the strict robust models might have bad objective function values or even get infeasible. In order to cope with this problem and to get more exible, advanced robust approaches are considered, namely recoverable and light robustness. These concepts have been established in railway and are transferred to the runway scheduling problem in this work. Then, statements are given regarding the relation between the advanced models, the strict robust and the nominal one. To this end we discuss computational results which are consistent to the statements. In part three, a simulation environment was developed for the tactical planning phase. The simulation is able to include uncertainties and different flight maneuver like go-arounds, holdings and departure drops are integrated. Over a time-horizon up to two hours before take-off/ touch-down, the developed models are tested under the occurrence of disturbances. The considered measurements are changes in target times, number of position changes, the mentioned ight maneuver as well as punctuality. The work is finalized by an evaluation of the obtained results.In dieser Arbeit betrachten wir das Problem der Landebahnplanung (Runway Scheduling Problem) aus der Sichtweise der mathematischen Modellierung und Optimierung. Wir widmen uns ausschließlich dem taktischen Planungsbereich, das heißt ab etwa zwei Stunden vor Landung/ Abflug, und entwickeln eine Simulationsumgebung für diesen Zeitraum. Beim Landebahnplanungsproblem ist es die Aufgabe, Flugzeuge optimal auf Landebahnen zu planen. Zu einer gegebenen Anzahl an ankommenden und abfliegenden Flugzeugen sind jeweils das Intervall aus frühest und spätest möglicher Ankunfts- beziehungsweise Abflugzeit sowie die ursprünglich geplante Zielzeit, welche auch auf dem Flugticket steht, gegeben. Zudem werden die Flugzeuge in unterschiedliche Gewichtsklassen gegliedert, welche Einfluss auf einzuhaltende Mindestabstände zwischen je zwei Flugzeugen haben. Mit Hilfe von mathematischen Modellen und Lösungsalgorithmen bestimmen wir unter verschiedenen Gesichtspunkten Lösungen des Problems, nämlich eine optimale Sequenz der Flugzeuge. Diese Arbeit ist dreigeteilt. Im ersten Teil untersuchen wir das nominale Runway Scheduling Problem, das heißt ohne Auftreten und Berücksichtigung von Unsicherheiten. Hierbei betrachten wir zwei mathematische Modelle, welche strukturell unterschiedlich sind. Diese werden untereinander und mit verschiedenen Algorithmen des Deutschen Zentrums für Luft- und Raumfahrt (DLR) unter Zugrundelegen von sowohl realen als auch Zufallsdaten verglichen. Im zweiten Teil nehmen wir Störungen, die im Flugverkehr häufig auftreten, mit in unsere Planung auf. Zuerst führen wir eine Definition von Robustheit im Air Traffic Management (ATM) Kontext ein und gehen dann bezugnehmend auf diese Definition auf unterschiedliche mathematische Robustheitskonzepte ein. Hierbei werden strikt robuste Ansätze angewandt, welche sich zu 100% gegenüber vorher definierten Unsicherheiten absichern. Mit Vergrößerung der Absicherung gegenüber Unsicherheiten können die robust optimalen Lösungen erwartungsgemäß konservativ oder die strikt robusten Modelle sogar unzulässig werden. Um demgegenüber flexibler reagieren zu können, wenden wir sogenannte fortgeschrittene robuste Ansätze, nämlich light und recoverable robust, auf das Runway Scheduling Problem an. Diese Konzepte wurden im Bahnverkehr angewandt und in dieser Arbeit auf den Flugverkehr übertragen. Es werden Aussagen bezüglich dem Zusammenhang beider Modelle zum nominalen sowie zum strikt robusten Modell gegeben und abschließend durch Rechenergebnisse unterstrichen. Im dritten Teil entwickeln wir eine Simulation, welche Störungen in den taktischen Planungsbereich mit einbeziehen kann. Zudem sind verschiedenste Flugmanöver, wie Go-arounds, Holdings und Departure drops integriert. Über einen Zeitraum von bis zu zwei Stunden vor Landung/ Abflug werden die erwähnten Modelle unter auftretenden Störungen getestet und anschließend die Anzahl der Umplanungen, die Veränderung der Zielzeiten, die genannten Flugmanöver sowie die Pünktlichkeit gemessen. Eine Auswertung der Ergebnisse schließt diese Arbeit ab