[Zurück]

S. Kuran:
"Heuristische Optimierungsverfahren für die Koordinierung von Flughafenslots";
Betreuer/in(nen): G. Raidl, A Chwatal; Institute of Logic and Computation, 2020; Abschlussprüfung: 03/2020.

Die vorliegende Arbeit beschäftigt sich mit der Erstkoordinierung von Flughafenslots. In
Europa unterliegt es der Verantwortung des jeweiligen Flughafenkoordinators zu Beginn
einer Saison einen initialen Flugplan zu erstellen. Dies ist eine komplexe Aufgabe und
bietet hohes Potential für Optimierungsverfahren. Der Fokus dieser Arbeit liegt in der
vollständig automatisierten Erstellung eines initialen Flugplans anhand heuristischer
Algorithmen.
Diese Arbeit wurde in engem Kontakt mit der Schedule Coordination Austria entwickelt
und ein großer Schwerpunkt liegt daher in der praktischen Anwendbarkeit. Aufgrund
der großen Menge an Flugdaten wurde ein heuristischer Ansatz gewählt. Erstmals
wird eine Konstruktionsheuristik vorgestellt, die die Koordinierung von Flughafenslots in
relativ kurzer Laufzeit ermöglicht. Zusätzlich werden heuristische Verbesserungsmethoden
vorgestellt, um die Ergebnisse weiter zu optimieren.
Die Erstkoordinierung basiert auf initialen Anfragen der Fluglinien für Ankunfts- und
Abflugslots an den jeweiligen Flughäfen für die nächste Saison. Im Allgemeinen ist es das
Ziel, so viele dieser Anfragen wie möglich zu bestätigen und so wenig wie möglich von der
angefragten Zeit abzuweichen. Allerdings unterliegt die Koordinierung zahlreichen Beschränkungen.
Zum einen müssen die IATA Vorgaben, sowie europäische Bestimmungen,
eingehalten werden. Dies beinhaltet under anderem Bestandsrechte (sog. "Großvaterrechte"),
sowie Prioritätsregeln. Zum anderen unterliegen die Ressourcen des Flughafens für
gewöhnlich zahlreichen Kapazitätsbeschränkungen. In dieser Arbeit wird ein umfangreiches
Konzept mit vielen Konfigurationsmöglichkeiten vorgestellt, um Pisten-, Passagierund
Vorfeldbeschränkungen einzuhalten. Des Weiteren muss eine bestimmte Bodenzeit
zwischen Ankunft und Abflug eingehalten werden.
Überdies erfolgt die Anfrage von Flughafenslots in Serien, bestehend aus mehreren
Anfragen gleichartiger Flüge im Verlauf einer Saison. Die Slots einer solchen Serie sollten
möglichst einheitlich zugewiesen werden. Das entspricht einem weiteren Optimierungsziel.
Die Optimierung besteht aus zwei wesentlichen Komponenten: einer Konstruktionsheuristik
und darauf folgende Verbesserungsmethoden. Mit dem Konstruktionsalgorithmus wird
die Anzahl der bestätigten Anfragen maximiert. Die Verbesserungsmethoden dagegen
approximieren die Pareto Front des mehrdimensionalen Optimerungsproblems. Auf diese
Weise erzeugt der Algorithmus mehrere Pareto-effiziente Lösungen mit unterschiedlicher Zeitabweichung und Fragmentierung, einem Maß für die einheitliche Zuweisung von
Serien.
Die Algorithmen werden anhand von operativen Daten des Wiener Flughafens sowohl
in Bezug auf die Zeitabweichung zur angefragten Wunschzeit, als auch in Bezug auf die
Fragmentierung evaluiert und getestet. Außerdem werden die Ergebnisse der Algorithmen
mit Daten aus der angewandten Praxis der letzten Saisonen verglichen.
Die Ergebnisse sind hinsichtlich der betrachteten Optimierungsziele mit den manuell
erzeugten Flugplänen vergleichbar, bzw. in manchen Situationen sogar besser. Somit
können die Algorithmen die Erstkoordinierung von Flughafenslots mit hoher Flexibilität
unterstützen und ermöglichen es, den manuellen Aufwand bei der Erstellung eines initialen
Flugplans zu reduzieren.

This work deals with long-term airport slot allocation. In Europe, local coordination
authorities are responsible to create an initial flight schedule in advance of a season. This
is a sophisticated problem and bears great potential for optimization methods. The focus
of this work is to create an initial flight schedule in a fully automated way by heuristic
algorithms.
This thesis is developed with high emphasis on practical applicability. It was carried
out in close contact with Schedule Coordination Austria. Due to the high amount of
flight data, a heuristic approach is taken. For the first time, a construction heuristic
is proposed to solve the airport slot allocation problem within relatively short running
times. Additionally, heuristic improvement methods are presented to further optimize
the results.
The coordination process is based on air carriers requesting arrival and departure slots
for certain airports for the upcoming season. In general, the aim is to confirm as many
such submissions as close as possible to the initially requested times. However, the
airport slot allocation process is restricted by several respects. For once, the IATA
guidelines and European regulations must be met. This involes inter alia compliance to
the grandfather rights and consideration of priority rules. For another, the resources of
the airport are usually constrained by several capacity limitations. Within this thesis an
extensive framework is introduced, to respect runway limitations as well as passenger and
apron restrictions in a highly configurable way. Furthermore, to allow for refueling and
cleaning, interdependencies between arrivals and departures must be taken into account.
In particular, a certain ground time must be met.
Moreover, the requests of the initial submission are treated as series comprising the
requests of similar flights over the course of the season. The slots for such series should
be assigned as uniformly as possible, which is a further optimization objective. The
optimization framework consists of two major components: a construction algorithm
and a subsequent improvement process. Whereas the construction algorithm attempts
to maximize the number of confirmed requests, the improvement step approximates the
pareto frontier of the multi-objective problem. Thus, the algorithm yields multiple pareto
efficient solutions with different time deviations and fragmentations, i. e. the degrees of
uniformity of the assigned series of slots.The developed algorithms are evaluated and benchmarked by real world data of the
Vienna airport with regard to both objectives, low time deviation regarding the initially
requested times as well as good fragmentation. Furthermore, the computational results
are compared to applied practice of historic seasons.
Regarding the considered objective function the results are comparable, and in some
situations even better than the manually obtained schedules. This allows to solve the
assignment problem of the initial submission with higher flexibility and less manual effort.

https://publik.tuwien.ac.at/files/publik_294889.pdf