ZIB-Report
Refine
Year of publication
- 2019 (57) (remove)
Document Type
- ZIB-Report (55)
- Article (2)
Has Fulltext
- yes (57)
Keywords
- Periodic Event Scheduling Problem (3)
- Periodic Timetabling (3)
- mixed integer programming (3)
- Classification (2)
- Lie groups (2)
- MINLP (2)
- Manifold valued statistics (2)
- Monte Carlo (2)
- Statistical shape analysis (2)
- blood oxygen saturation (2)
Institute
- Mathematical Optimization (31)
- Visual Data Analysis (14)
- Visual and Data-centric Computing (14)
- Mathematical Optimization Methods (11)
- Numerical Mathematics (9)
- Therapy Planning (5)
- Energy Network Optimization (4)
- Computational Medicine (3)
- Computational Systems Biology (3)
- Distributed Algorithms and Supercomputing (2)
20-32
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.