Development and Evaluation of Novel Algorithms for Enhanced Aircraft Routing on Ground

Abstract: The process of Aircraft Routing on Ground corresponds to the surface movement of aircraft on an airport’s taxiway network, from a runway exit to a parking stand (arrivals) and from a parking stand to a runway entrance (departures). Given such a pair of terminal points and depending on the taxiway network structure, there can be one or more alternative routes that the aircraft can follow to its destination. From a functional perspective, this surface movement is the link between the airborne movement and the turnaround process for each aircraft. As the size, the operational complexity and the traffic of an airport increases, the sequence of “landing-taxiing-turnaroundtaxiing-taking-off” can become tight and the satisfaction of temporal constraints can become critical in terms of cost-effectiveness, both for the airlines and the airport operators.

From the discussion above we can deduce that the choice of an optimal route on the taxiway network for each aircraft depends also on the dimension of time, since the traffic load on each taxiway is a dynamic parameter. The problem that this thesis is concerned with can therefore be called “4D Taxi Routing on Ground”. The work for this thesis was done at Jeppesen GmbH in Neu-Isenburg, Germany.

The main focus of this work is the definition, analysis and modeling of the problem of “4D Taxi Routing on Ground”. The entities that constitute the essence of the problem are described: the Taxiway Network as a directed, bimodal graph with weights that are functions of time; the Aircraft as moving agents with a finite set of states; and the Airport Operations as the environment. A set of objectives that determine the quality of a routing solution is also defined: minimization of taxi time, hold time and speed changes for each aircraft. Based on these definitions, a mathematical model is built.

In order to test the soundness of the defined model and its applicability to the problem of “4D Taxi Routing on Ground”, an optimization algorithm is designed and implemented, based on a combination of Dijkstra’s SPP algorithm and a Linear Programming formulation. The evaluation of the algorithm is realized using simulations of a 2-day actual flight schedule and the results support the assumption of correctness for most of the model design choices, while they also show the inefficiencies of a static SPP algorithm when applied to a dynamic or “4D” routing problem, thus indicating directions for further research or potential areas of improvement.