The Flight Planning Problem is a type of Shortest Path Problem that deals with calculating a minimal-cost flight trajectory between two airports. This trajectory must take into account various types of operative restrictions constraining it both horizontally and vertically. Further factors such as weather (in particular wind), aircraft performance, and fuel on board must be considered. The goal is to minimize the sum of fuel costs, time costs, and overflight costs.
Despite the complexity of this problem, which requires the processing of large amounts of data, real-world applications demand that it be solved within minutes or even seconds. This creates the need for fast solution algorithms yielding high-quality – ideally optimal – solutions. In this thesis, we explore various aspects of the Flight Planning Problem and propose several novel algorithms. Our tests on real-world data show that they significantly improve the state-of-the art. In some cases, they are the first of their kind.
We present a method to reliably underestimate air distance which allows for the creation of an A* algorithm to solve a variant of the Flight Planning Problem that assumes constant altitude. This algorithm, which generalizes the Time-Dependent Shortest Path Problem (TDSPP), is guaranteed to be optimal under assumption of the First-In-First-Out property, and is on average 20 times faster than the Dijkstra algorithm. In a classical TDSPP setting with piecewise-linear travel time functions, our A* outperforms the state-of-the-art approach by a factor of 15.
We also propose a "pruning" technique for significantly reducing the search space of the problem while preserving optimality. We show that a Dijkstra algorithm running on this reduced space is up to 6 times faster than one based on a naive search space reduction. To the best of our knowledge, this is the first work in the literature that presents a highly performant algorithm for solving the Flight Planning Problem with variable altitude, under consideration of not only fuel and time, but also overflight costs.
We also extend our first A* algorithm to a version that runs on the three-dimensional version of the problem by defining a sophisticated potential function based on "idealized vertical profiles". This potential is proven to be both admissible and consistent under reasonable assumptions, ensuring optimality. Additionally, we introduce two preprocessing techniques to speed up the calculation of the queries and show that our algorithm algorithm outperforms the A* algorithm that previously yielded the best results, resulting in a speed-up of up to 40%.
The importance of overflight costs in flight planning is often overlooked in the literature. We introduce a heuristic that transforms route-based overflight costs into arc-based costs and integrate them into a classical Dijkstra algorithm. The required preprocessing step is fast enough to be practical in applications. A Dijkstra algorithm using the calculated arc costs is faster than the best known exact algorithm by a factor of over 350, with an optimality gap of less than 1%.
Finally, we conduct a polyhedral analysis of the Path Avoiding Forbidden Pairs polytope, motivated by the study of complex traffic restrictions present in the Flight Planning Problem. Under certain conditions, we are able to provide a complete linear description of the polytope, together with a polynomial-time separation routine.
