Document Open Access Logo

A Priori Search Space Pruning in the Flight Planning Problem

Authors Adam Schienle, Pedro Maristany, Marco Blanco

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2019.8.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Adam Schienle
  • Zuse Institute Berlin, Berlin, Germany
Pedro Maristany
  • Zuse Institute Berlin, Berlin, Germany
Marco Blanco
  • Lufthansa Systems, Raunheim, Germany

Cite As Get BibTex

Adam Schienle, Pedro Maristany, and Marco Blanco. A Priori Search Space Pruning in the Flight Planning Problem. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.ATMOS.2019.8

Abstract

We study the Flight Planning Problem for a single aircraft, where we look for a minimum cost path in the airway network, a directed graph. Arc evaluation, such as weather computation, is computationally expensive due to non-linear functions, but required for exactness. We propose several pruning methods to thin out the search space for Dijkstra’s algorithm before the query commences. We do so by using innate problem characteristics such as an aircraft’s tank capacity, lower and upper bounds on the total costs, and in particular, we present a method to reduce the search space even in the presence of regional crossing costs.
We test all pruning methods on real-world instances, and show that incorporating crossing costs into the pruning process can reduce the number of nodes by 90% in our setting.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
Keywords
  • time-dependent shortest path problem
  • crossing costs
  • flight trajectory optimization
  • preprocessing
  • search space

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. Technical report, Microsoft Research, 2015. Google Scholar
  2. G. Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. Minimum Time-dependent Travel Times with Contraction Hierarchies. J. Exp. Algorithmics, 18:1.4:1.1-1.4:1.43, April 2013. Google Scholar
  3. Gernot Veit Batz, Robert Geisberger, Sabine Neubauer, and Peter Sanders. Time-Dependent Contraction Hierarchies and Approximation. In Paola Festa, editor, Experimental Algorithms, pages 166-177, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  4. Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-Consumption Tradeoff for Electric Vehicle Route Planning. In Stefan Funke and Matúš Mihalák, editors, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, volume 42 of OpenAccess Series in Informatics (OASIcs), pages 138-151, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2014.138.
  5. 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 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), 2017. Google Scholar
  6. Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), 2016. Google Scholar
  7. Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Thomas Schlechte, and Swen Schlobach. The Shortest Path Problem with Crossing Costs. Technical report, ZIB, 2016. Google Scholar
  8. Edsger W. Dijkstra. Numerische Mathematik, chapter A Note on Two Problems in Connexion with Graphs, pages 269-271. Springer, 1959. Google Scholar
  9. Axel Dreves and Matthias Gerdts. Free Flight Trajectory Optimization and Generalized Nash Equilibria in Conflicting Situations. Technical report, Universität der Bundeswehr München, 2017. Google Scholar
  10. Stuart E. Dreyfus. An Appraisal of Some Shortest Path Algorithm. Operational Research, 17(3):395-412, June 1969. Google Scholar
  11. Eurocontrol. Free route airspace (FRA). Online, 2019. Accessed April 2019. URL: https://www.eurocontrol.int/articles/free-route-airspace.
  12. Eurocontrol. Route Availability Document. Online, April 2019. URL: https://www.nm.eurocontrol.int/RAD/.
  13. Luca Foschini, John Hershberger, and Subhash Suri. On the Complexity of Time-Dependent Shortest Paths. Algorithmica, 68(4):1075-1097, April 2014. URL: https://doi.org/10.1007/s00453-012-9714-7.
  14. Michael L. Fredman and Robert Endre Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Journal of the ACM, 34(3):596-615, July 1987. Google Scholar
  15. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact Routing in Large Road Networks Using Contraction Hierarchies. Transportation Science, 46(3):388-404, August 2012. Google Scholar
  16. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions of Systems Science and Cybernetics, 4(2):100-107, July 1968. Google Scholar
  17. Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen. Flight Planning in Free Route Airspaces. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), 2017. Google Scholar
  18. Stefan E. Karisch, Stephen S. Altus, Goran Stojković, and Mirela Stojković. Quantitative Problem Solving Methods in the Airline Industry, chapter Operations, pages 283-383. Springer, 2012. Google Scholar
  19. Adam Schienle. Shortest Paths on Airway Networks. Master’s thesis, Freie Universität Berlin, 2016. Google Scholar
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 About DROPS Imprint Privacy Contact