2026-08-19T07:06:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17105 2024-03-06T10:31:51Z ddc:004 open_access

An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles Blanco, Marco Borndörfer, Ralf Maristany de las Casas, Pedro shortest path problem a-star algorithm flight trajectory optimization flight planning heuristics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marco Blanco and Ralf Borndörfer and Pedro Maristany de las Casas 2022 Is Part Of OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2022.1 urn:nbn:de:0030-drops-171052 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.1 eng https://creativecommons.org/licenses/by/4.0/legalcode