Document Open Access Logo

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

Authors Marco Blanco, Ralf Borndörfer, Pedro Maristany de las Casas

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2022.1.pdf
  • Filesize: 0.63 MB
  • 15 pages

Document Identifiers

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

  1. 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.
  2. 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.
  3. 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. Google Scholar
  4. 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.
  5. 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. Google Scholar
  6. H.M. de Jong. Optimal track selection and 3-dimensional flight planning. techreport, Royal Netherlands Meteorological Institute, 1974. Google Scholar
  7. 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.
  8. 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. Google Scholar
  9. 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.
  10. 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. Google Scholar
  11. 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.
  12. 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. Google Scholar
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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. Google Scholar
  19. 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.
  20. 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. Google Scholar
  21. 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.
  22. 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.
  23. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact