The Free Route Flight Planning Problem on Airway Networks
Authors (first author is the speaker)
|Zuse Institut Berlin|
|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.
- Dynamic Programming
- Graphs and Networks
Back to the list of papers