2026-07-25T00:03:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11420 2024-03-06T10:30:48Z ddc:004 open_access

A Priori Search Space Pruning in the Flight Planning Problem Schienle, Adam Maristany, Pedro Blanco, Marco time-dependent shortest path problem crossing costs flight trajectory optimization preprocessing search space 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Schienle and Pedro Maristany and Marco Blanco 2019 Is Part Of OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2019.8 urn:nbn:de:0030-drops-114205 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.8 eng https://creativecommons.org/licenses/by/3.0/legalcode