Flight Trajectory Optimization on Airway Networks

In this project, we concern ourselves with the problem of efficiently computing a minimum-cost flight trajectory between a given pair of airports. To achieve this, we combine classical shortest-path algorithms with techniques from integer programming and combinatorial optimization.

Background:

An important problem in airline operations is that of determining the exact trajectory to be flown by an aircraft, as well as the amount of fuel to be loaded, prior to take-off. The associated costs are a function of fuel consumption, overflight charges and travel time, among others. These costs themselves are highly dependent on factors such as weather conditions, aircraft performance, take-off time and take-off weight.

Furthermore, there exist several operational and safety constraints that must be met. In particular, trajectories are restricted horizontally by an airway network and vertically by the available flight levels on most regions. Aditionally, there is a swiftly growing number of restrictions imposed by the regional air traffic control authorities, which have the objective of inducing a more balanced use of the airway network. These restrictions have the effect that even finding a feasible trajectory is an NP-hard problem. Since their introduction is relatively recent, state-of-the art flight planning tools have difficulties handling them efficiently.

In practice, the flight plan is computed a few hours before take-off, in order to have a reliable weather forecast. This generates the additional need for extremely fast computation times. 

Goal:

The goal of this project is to develop fast, reliable algorithms to solve the flight planning problem and integrate them into a prototype tool. This will be done in close cooperation with our industry partner, who plans to use our tool as the basis for the new generation of their flight planning system.

Optimization:

From a mathematical point of view, the flight planning problem can be partially modeled as a resource-constrained shortest path problem with dynamic, non-additive costs and side constraints. We are developing exact algorithms based on classical methods for the shortest path problem, such as the Dijkstra and A* algorithms, combined with lagrangian relaxation and linear programming techniques to cope with the side constraints. Since even simplified versions of this problem are NP-hard, in addition to the exact approaches we plan to develop heuristics to obtain good-quality solutions quickly. 

Partner:

Lufthansa Systems GmbH & Co. KG