Cost Minimal Aircraft Trajectories on Airway Networks
Invited abstract in session TA4: Graphs in Air Transportation, stream Graphs and Networks.
Thursday, 9:0010:30Room: WGS104
Authors (first author is the speaker)
1.  Pedro M. Casas

Zuse Institute Berlin  
2.  Marco Blanco

Lufthansa Systems  
3.  Ralf BorndÃ¶rfer

Optimization, ZuseInstitute Berlin  
4.  Nam Dung Hoang

Optimization, Zuse Institute Berlin 
Abstract
Given the departure and destination airports, the Flight Planning Problem (FPP) seeks to find cost minimal flight trajectories for commercial aircraft along the Airway Network (A.N.), which is modeled as a digraph.
In a static setting of the FPP, where time dependent components are neglected, the two main cost components for such a trajectory are fuel and overflight costs (OFC). While fuel costs can be defined as costs on the arcs of the A.N., there are many airspaces, such as the European ones, where OFCs do not depend on the chosen route within the airspace, but instead are linearly dependent on the greatcircle distance between entry and exit nodes for this airspace.
In this talk we will discuss the Shortest Path Problem with Crossing Costs (SPPCC), a generalization of the known Shortest Path Problem (SPP), which translates the described properties into a combinatorial problem. Crossing Costs are the general term used to refer to overflight costs.
The talk will begin with a brief analysis of the complexity of the SPPCC. The polynomial case described above can be solved using an algorithm called Two Layer Dijkstra (2LD), which yields a non satisfying runtime in practice.
Thus, during the talk, we will mainly focus on the analysis of different methods that can be used to distribute the exact OFCs over the arcs of the corresponding region. Finding good such methods allows us to reduce SPPCC instances to SPP instances, thus being able to approximate a solution to the original problem extremely fast. This reduction does not only perform well concerning the runtime of the algorithm (x708 faster in average than using the 2LD), but also concerning the quality of the approximated solutions: they differ by 0.09% from the optimal ones.
Keywords
 Airline Applications
 Combinatorial Optimization
Status: accepted
Back to the list of papers