[Back]


Diploma and Master Theses (authored and supervised):

A. Windbichler:
"A Heuristic Approach to Aircraft Trajectory Optimization with Constraints";
Supervisor: G. Raidl; Institute of Logic and Computation, 2019; final examination: 2019-03-13.



English abstract:
Air traffic is continuously increasing, and so is the airway network and the restrictions
controlling the flow. As a result computing the most efficient trajectory, which is
a subproblem of flight planning, gets harder. Airlines constantly need to consider
more parameters in the optimization to stay competitive. This brings currently used
algorithms to their limit. Therefore we present a heuristic method that keeps the necessary
extensibility from the start in mind.
We present a detailed problem definition which comes, to our knowledge, closer to
actual real-life scenario than any other in the literature. We extend an in the industry
widespread approach based on Dijkstra´s algorithm, which we embedded in a process
to cope with Air traffic control restrictions. For all restrictions whose application can
be decided based on the instance, we are adapting the graph s.t. those restrictions are
already respected. All other restrictions are evaluated lazily and subsequently avoided,
resulting in an iterated process. For our assumptions, this method guarantees to return
the optimum result. However, because of the underlying algorithm, it is hard to extend,
and the number of restrictions has a significant influence on the runtime. Therefore, we
propose a heuristic method, with the goal to overcome those shortcomings. We make
use of the fact that during the lifetime of a flight, the trajectory needs to be calculated
several times. We use those trajectories and iteratively adapt them, to fit the changed
situation best. If a solution violates a restriction, it will reflect negatively in its quality.
An additional heuristic allows to preliminary determine that for a given path exists an
altitude profile that does not violate any restrictions, which allows us to exclude this
path from the search.
We performed tests for city pairs within Europa, which is tightly packed with restrictions.
In our tests, the heuristic approach reached within a few iterations the same result as the
optimal method, but within significantly less computation time. We reached speedups
up to 10x and expect the margin to grow further with a growing number of restrictions.
Additionally, we already considered necessary extensions in the choice of our algorithm
which are necessary during the course of flight planning.

German abstract:
Der Flugverkehr nimmt kontinuierlich zu, was dazu führt, dass das Airway-Netwerk wächst
und die Anzahl der Restriktionen steigt. Dadurch wird die Berechnung der effizientesten
Flugbahn, einer Teilaufgabe der Flugplanung immer schwieriger. Die Fluggesellschaften
versuchen unter Konkurrenzdruck ständig mehr Variablen in die Optimierungen einfließen
zu lassen. Wir präsentieren deshalb eine heuristische Methode die von Beginn an die
Notwendigkeit von zukünftigen Erweiterungen berücksichtigt.
Wir präsentieren eine detalierte Problemdefinition, welche, unseres Wissens nach, näher
am realen Szenario liegt als frühere in der Literatur. Wir erweitern eine in der Industrie
verbreitete Methode basierend auf Dijkstra´s Algorithmus, welcher von uns in einen
Prozess eingebettet wurde der es erlaubt komplexe Restriktionen der Luftfahrtbehörden
zu berücksichtigen. Möglichst viele Restriktionen berücksichtigen wir bereits durch adaptierungen
im Graphen, alle weiteren werden durch Lazy Evaluierung in einem iterativen
Prozess berücksichtigt. Dieser Ansatz liefert, unter unseren Annahmen, garantiert die
beste Lösung, Jedoch ist er durch den zugrundeliegenden Algorithmus nur schwer zu
erweitern und die wachsende Anzahl an Restriktionen hat einen starken Einfluss auf
die Laufzeit. Deshalb entwickelten wir einen heuristischen Ansatz, mit dem Ziel diese
Probleme zu beseitigen. Wir machen uns die Tatsache zu nutze das die Flugbahn über den
Lebensyklus eines Fluges viele male neu berechnet werden muss und somit eine Vielzahl
an bereits berechneten Flugbahnen zur Verfügung steht. Diese werden von uns iterativ
adaptiert um sich der neuen Situation bestmöglich anzupassen. Sofern eine Lösung eine
Restriktionen verletzt, fließt dies negativ in deren Güte ein. Eine weitere Heuristik die die
Gültigkeit einer gegebenen Route (unabhaengig vom Höhenprofil) bezüglich Restriktionen
ausschließt, erlaubt es ganze Routen von der Suche auszuschließen.
Für unsere Tests haben wir Optimierungen zwischen europäischen Städten durchgeführt,
da dieser Luftraum die größte Anzahl an Restriktionen aufweist. In diesen Tests hat
der heuristische Ansatz innerhalb weniger Iterationen stets die gleichen Ergebnisse wie
der exakte geliefert, dies aber in deutlich kürzerer Rechenzeit. Wir erreichten einen
Speedup von bis zu 10x, und erwarten durch die steigende Anzahl von Restriktionen das
dieser Abstand wachsen wird. Weiters wurde bei dem Entwurf unserer Heuristik bereits
Rücksicht auf notwendige Erweiterungen genommen die im Zuge des Flightplannings
notwendig sind. Diese Erweiterungen lassen sich dadurch auf natüliche Art und Weise
integrieren.


Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_301816.pdf


Created from the Publication Database of the Vienna University of Technology.