An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles
| Autor: | Blanco, Marco, Borndörfer, Ralf, Maristany de las Casas, Pedro |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Mathematics of computing → Discrete optimization
Mathematics of computing → Paths and connectivity problems a-star algorithm Mathematics of computing → Graph algorithms flight trajectory optimization Mathematics of computing → Combinatorial optimization flight planning heuristics shortest path problem |
| DOI: | 10.4230/oasics.atmos.2022.1 |
| Popis: | The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A* heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances. OASIcs, Vol. 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), pages 1:1-1:15 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|