OR2017 Abstract Submission

Cost Minimal Aircraft Trajectories 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. Pedro M. Casas
Zuse Institute Berlin
2. Marco Blanco
Lufthansa Systems
3. Ralf Borndörfer
Optimization, Zuse-Institute Berlin
4. Nam Dung Hoang
Optimization, Zuse Institute Berlin


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 great-circle 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.


Status: accepted

Back to the list of papers