文章基本信息

标题：A Priori Search Space Pruning in the Flight Planning Problem
本地全文：下载
作者：Adam Schienle ; Pedro Maristany ; Marco Blanco 等
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2019
卷号：75
页码：1-14
DOI：10.4230/OASIcs.ATMOS.2019.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：time-dependent shortest path problem; crossing costs; flight trajectory optimization; preprocessing; search space