A Priori Search Space Pruning in the Flight Planning Problem
- 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.
Author: | Adam Schienle, Pedro Maristany de las CasasORCiD, Marco Blanco |
---|---|
Document Type: | Article |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B99 None of the above, but in this section |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27] | |
Publishing Institution: | Zuse Institute Berlin (ZIB) |
Date of first Publication: | 2019/11/15 |
Series (Serial Number): | ZIB-Report (20-32) |
ISSN: | 1438-0064 |
DOI: | https://doi.org/https://doi.org/10.4230/OASIcs.ATMOS.2019.8 |
Licence (German): | ![]() |