An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles

File

Author Details

Marco Blanco

Lufthansa Systems GmbH & Co. KG, Raunheim, Germany
Zuse Institute, Berlin, Germany

Ralf Borndörfer

Zuse Institute, Berlin, Germany

Pedro Maristany de las Casas

Zuse Institute, Berlin, Germany

Cite AsGet BibTex

Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas. An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/OASIcs.ATMOS.2022.1

Abstract

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.

Subject Classification

ACM Subject Classification

Mathematics of computing → Graph algorithms
Mathematics of computing → Paths and connectivity problems
Mathematics of computing → Combinatorial optimization
Mathematics of computing → Discrete optimization

Keywords

shortest path problem
a-star algorithm
flight trajectory optimization
flight planning
heuristics

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks, 2015. URL: https://doi.org/10.48550/ARXIV.1504.05140.
Moritz Baum, Julian Dibbelt, Dorothea Wagner, and Tobias Zündorf. Modeling and engineering constrained shortest path algorithms for battery electric vehicles. Transportation Science, 54:1571-1600, November 2020. URL: https://doi.org/10.1287/trsc.2020.0981.
Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Pedro Maristany de las Casas, Thomas Schlechte, and Swen Schlobach. Cost projection methods for the shortest path problem with crossing costs. In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 17superscriptth Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59, 2017.
Marco Blanco, Ralf Borndörfer, Nam Dũng Hoàng, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. Solving time dependent shortest path problems on airway networks using super-optimal wind. In 16superscriptth Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54, 2016. in press. URL: https://doi.org/10.4230/OASIcs.ATMOS.2016.12.
Marco Blanco, Ralf Borndörfer, Nam Dũng Hoàng, Anton Kaier, Thomas Schlechte, and Swen Schlobach. The shortest path problem with crossing costs. techreport 16-70, ZIB, 2016.
H.M. de Jong. Optimal track selection and 3-dimensional flight planning. techreport, Royal Netherlands Meteorological Institute, 1974.
Daniel Delling and Giacomo Nannicini. Core routing on dynamic time-dependent road networks. INFORMS Journal on Computing, 24(2):187-201, May 2012. URL: https://doi.org/10.1287/ijoc.1110.0448.
Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal route planning for electric vehicles in large networks. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI'11, pages 1108-1113. AAAI Press, 2011.
Patrick Hagelauer and Felix Antonio Claudio Mora-Camino. A soft dynamic programming approach for on-line aircraft 4D-trajectory optimization. European Journal of Operational Research, 107(1):87-95, May 1998. URL: https://doi.org/10.1016/S0377-2217(97)00221-X.
Edward He, Natashia Boland, George Nemhauser, and Martin Savelsbergh. Time-dependent shortest path problems with penalties and limits on waiting. INFORMS Journal on Computing, 2020.
Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen. Flight Planning in Free Route Airspaces. In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 1-14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.14.
Stefan E. Karisch, Stephen S. Altus, Goran Stojković, and Mirela Stojković. Operations. In Cynthia Barnhart and Barry Smith, editors, Quantitative Problem Solving Methods in the Airline Industry, volume 169 of International Series in Operations Research & Management Science, pages 283-383. Springer US, 2012.
Anders Nicolai Knudsen, Marco Chiarandini, and Kim S. Larsen. Vertical optimization of resource dependent flight paths. In ECAI 2016 - 22superscriptnd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016), pages 639-645, 2016. URL: https://doi.org/10.3233/978-1-61499-672-9-639.
Anders Nicolai Knudsen, Marco Chiarandini, and Kim S. Larsen. Constraint Handling in Flight Planning. In Principles and Practice of Constraint Programming - 23superscriptrd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings, pages 354-369, 2017. URL: https://doi.org/10.1007/978-3-319-66158-2_23.
Anders Nicolai Knudsen, Marco Chiarandini, and Kim S. Larsen. Heuristic Variants of A* Search for 3D Flight Planning. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15superscriptth International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings, pages 361-376, 2018. URL: https://doi.org/10.1007/978-3-319-93031-2_26.
P. Maristany de las Casas, A. Sedeño-Noda, and R. Borndörfer. An improved multiobjective shortest path algorithm. Computers & Operations Research, page 105424, June 2021. URL: https://doi.org/10.1016/j.cor.2021.105424.
Pedro Maristany de las Casas, Luitgard Kraus, Antonio Sedeño-Noda, and Ralf Borndörfer. Targeted multiobjective dijkstra algorithm, 2021. URL: https://doi.org/10.48550/ARXIV.2110.10978.
Hok K. Ng, Banavar Sridhar, and Shon Grabbe. Optimizing aircraft trajectories with multiple cruise altitudes in the presence of winds. Journal of Aerospace Information Systems, 11(1):35-47, 2014.
Matti Nykänen and Esko Ukkonen. The exact path length problem. Journal of Algorithms, 42(1):41-53, 2002. URL: https://doi.org/10.1006/jagm.2001.1201.
Ariel Orda and Raphael Rom. Traveling without waiting in time-dependent networks is np-hard. Technical report, Department Electrical Engineering, Technion-Israel Institute of Technology, 1989.
Adam Schienle, Pedro Maristany, and Marco Blanco. A Priori Search Space Pruning in the Flight Planning Problem. In Valentina Cacchiani and Alberto Marchetti-Spaccamela, editors, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), volume 75 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2019.8.
Ben Strasser and Tim Zeitz. A fast and tight heuristic for a* in road networks, 2019. URL: https://doi.org/10.48550/ARXIV.1910.12526.
Tim Zeitz. Np-hardness of shortest path problems in networks with non-fifo time-dependent travel times. Information Processing Letters, 179:106287, 2023. URL: https://doi.org/10.1016/j.ipl.2022.106287.