Flight Route Optimization

A crucial component of a flight plan to be submitted for approval to a control authorityin the pre-flight phase is the flight route. The flight route is a path in a flight networkthrough a sequence of airways and waypoints that the aircraft follows in order to travelfrom one airport to another. Due to a large strain on the European flight network, alarge amount of side-constraints is used to regulate traffic flow and ensure safe flights.The constraints generally state that if a set of waypoints or airways is visited thenanother set of waypoints or airways must be avoided or must be visited. Paths areselected on the basis of cost considerations. The cost of traversing an airway depends,directly, on fuel consumption and on flight time, and, indirectly, on weight and onweather conditions.
Classic pathfinding algorithms such as Dijkstra’s algorithm and A∗search arecommonly used in automatic planning. However, the constraints and the dependencystructure of the costs invalidate the domination criterion used in these algorithms,since the FIFO property no longer holds true. Additionally, costs on arcs cannotbe computed before the search due to the dependency structure. Along with theimmense size of flight networks, these difficulties make the generation of flight routes acomputationally expensive task. A common approach to reduce computation time is todecompose the problem into a sequence of horizontal and vertical route optimizations.
We study the feasibility of addressing flight routing directly as a 3D problem. Bothstages of the decomposed problem were implemented and the combination of theseis compared with the direct 3D approach. Several improvements were implementedand tested for both approaches. We consider the complicated problem of determiningefficient A∗estimates in a setting with a complex cost function. We provide a framework,usable in both settings, for the description, representation and propagation of theconstraints during the search in pathfinding algorithms. In addition, we study lazyapproaches for dealing with the constraints and the use of geographic considerationsto ignore them. We further enhance our algorithms with heuristics that exploit theexpected vertical profile of flight routes to reduce the search space. Real-life datais used for experimental analysis. We find that, in the vertical setting, the FIFOproperty can be assumed on cost with only a negligible reduction in solution quality.We also find that our techniques for constraint propagation work best together withan iterative search approach, in which only constraints that are violated in previouslyfound routes are introduced in the constraint set before the search is restarted. Finallywe conclude that the direct 3D approach is computationally feasible and leads to flightroutes of better quality than the decomposition approach.