Experimentelle Evaluierung heuristischer Suchalgorithmen zur Optimierung von Abflugreihenfolgen im Air Traffic Flow Management

Das Projekt SlotMachine verfolgt das Ziel, die Zuteilung von Flugverkehrsmanagement-Slots im Falle von Kapazitätsengpässen zu optimieren. Insbesondere beschäftigt sich das Projekt mit der Frage, wie die Abflugreihenfolge von Flügen im Falle von Kapazitätsengpässen optimiert werden kann. Um die Vertraulichkeit der Daten zu gewährleisten werden die Suche nach optimalen Lösungen und die Evaluierung der gefundenen Lösungen von getrennten Komponenten durchgeführt. Die Evaluierung gefundener Lösungen erfolgt mittels Multi-Party-Computation. Die Suche nach optimalen Lösungen erfolgt mittels heuristischer Suche.

In dieser Arbeit werden verschiedene Methoden zur heuristischen Suche von optimalen Abflugreihenfolgen in Bezug auf ihre Eignung für das Projekt SlotMachine experimentell untersucht. Experimente sollen zeigen, inwiefern verschiedene Optimierungsalgorithmen für die Optimierung von Abflugreihenfolgen geeignet sind. Insbesondere werden genetische Algorithmen und diverse lokale Suchalgorithmen untersucht. In den Experimenten werden existierende Open-Source-Frameworks mit unterschiedlichen Einstellungen verwendet, um optimale Abflugreihenfolgen in unterschiedlichen Szenarien in Bezug auf die Beschaffenheit der Präferenzen der Flüge zu ermitteln.

Die in dieser Arbeit durchgeführten Experimente zeigen, dass die mittels heuristischer Suche gefundenen Ergebnisse im Allgemeinen nahe der optimalen Lösung sind, wie sie von der (exakten) Ungarischen Methode gefunden wird.

The SlotMachine project aims to optimize the allocation of air traffic management slots in the event of capacity bottlenecks. In particular, the project addresses the question of how the departure sequence of flights can be optimized in the event of capacity bottlenecks. To ensure the confidentiality of the data, the search for optimal solutions and the evaluation of the solutions are carried out by separate components. The evaluation of the found solutions is performed by means of multi-party computation. The search for optimal solutions is performed using heuristic search.

In this work, different methods for the heuristic search of optimal departure sequences are experimentally investigated with respect to their suitability for the SlotMachine project. Experiments determine to what extent different optimization algorithms are suitable for the optimization of departure sequences. In particular, genetic algorithms and various local search algorithms will be investigated. In the experiments, existing open source frameworks with different settings are used to determine optimal departure sequences in different scenarios with respect to the nature of the preferences of the flights.

The experiments conducted in this work show that the results found using heuristic search are generally close to the optimal solution as found by the (exact) Hungarian method.