Heuristic optimization methods for seasonal airport slot allocation

Abstract

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-, Passagier- und 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 involves 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.