License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2019.8
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11420/
Go to the corresponding OASIcs Volume Portal

Schienle, Adam ; Maristany, Pedro ; Blanco, Marco

A Priori Search Space Pruning in the Flight Planning Problem

pdf-format:
OASIcs-ATMOS-2019-8.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{schienle_et_al:OASIcs:2019:11420,
  author =	{Adam Schienle and Pedro Maristany and Marco Blanco},
  title =	{{A Priori Search Space Pruning in the Flight Planning Problem}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{8:1--8:14},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Valentina Cacchiani and Alberto Marchetti-Spaccamela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11420},
  doi =		{10.4230/OASIcs.ATMOS.2019.8},
  annote =	{Keywords: time-dependent shortest path problem, crossing costs, flight trajectory optimization, preprocessing, search space}
}

Keywords: time-dependent shortest path problem, crossing costs, flight trajectory optimization, preprocessing, search space
Collection: 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Issue Date: 2019
Date of publication: 15.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI