OR2017 Abstract Submission

The Free Route Flight Planning Problem on Airway Networks

Invited abstract in session TA-4: Graphs in Air Transportation, stream Graphs and Networks.

Thursday, 9:00-10:30
Room: WGS|104

Authors (first author is the speaker)

1. Adam Schienle
Zuse Institut Berlin
2. Marco Blanco
Lufthansa Systems
3. Ralf Borndörfer
Optimization, Zuse-Institute Berlin
4. Nam Dung Hoang
Optimization, Zuse Institute Berlin


The Flight Planning Problem (FPP) deals with finding a minimum cost flight trajectory subject to initial conditions such as departure and destination airport, fuel cost and weather conditions. Traditionally, an aircraft's horizontal route is restricted to the Airway Network, a directed graph. Time dependent weather conditions allow us to model the FPP as a Time-Dependent Shortest Path Problem. Since the Airway Network is prevalent almost everywhere on earth, this structure renders combinatorial shortest path algorithms, such as Dijkstra's algorithm and algorithms derived from it, a natural choice for solving FPP.
Wishing to give the users of the Airway Network more freedom in planning their routes, together with easing congestion in parts of the network, gives rise to an increasing number of Free Route areas. Essentially, these are regions where there is no network defined at all, or where it is allowed to travel directly between any two points of the network, thus corresponding to cliques in the directed graph. This leads to the Free Route Flight Planning Problem, whose altered network structure impacts the performance of combinatorial shortest path algorithms. In the talk, we shall discuss different algorithmic approaches to solve the Free Route Flight Planning Problem.


Status: accepted

Back to the list of papers