A Heuristic approach to aircraft trajectory optimization with constraints

Abstract

Air traffic is continuously increasing, and so is the airway network and the restrictions controlling the flow. As a result computing the most efficient trajectory, which is a subproblem of flight planning, gets harder. Airlines constantly need to consider more parameters in the optimization to stay competitive. This brings currently used algorithms to their limit. Therefore we present a heuristic method that keeps the necessary extensibility from the start in mind. We present a detailed problem definition which comes, to our knowledge, closer to actual real-life scenario than any other in the literature. We extend an in the industry widespread approach based on Dijkstras algorithm, which we embedded in a process to cope with Air traffic control restrictions. For all restrictions whose application can be decided based on the instance, we are adapting the graph s.t. those restrictions are already respected. All other restrictions are evaluated lazily and subsequently avoided, resulting in an iterated process. For our assumptions, this method guarantees to return the optimum result. However, because of the underlying algorithm, it is hard to extend, and the number of restrictions has a significant influence on the runtime. Therefore, we propose a heuristic method, with the goal to overcome those shortcomings. We make use of the fact that during the lifetime of a flight, the trajectory needs to be calculated several times. We use those trajectories and iteratively adapt them, to fit the changed situation best. If a solution violates a restriction, it will reflect negatively in its quality. An additional heuristic allows to preliminary determine that for a given path exists an altitude profile that does not violate any restrictions, which allows us to exclude this path from the search. We performed tests for city pairs within Europa, which is tightly packed with restrictions. In our tests, the heuristic approach reached within a few iterations the same result as the optimal method, but within significantly less computation time. We reached speedups up to 10x and expect the margin to grow further with a growing number of restrictions. Additionally, we already considered necessary extensions in the choice of our algorithm which are necessary during the course of flight planning.