DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2017.14

Flight Planning in Free Route Airspaces

Authors: Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract

We consider the problem of finding cheapest flight routes through free route airspaces in a 2D setting. We subdivide the airspace into regions determined by a Voronoi subdivision around the points from a weather forecast. This gives rise to a regular grid of rectangular regions (quads) with every quad having an associated vector-weight that represents the wind magnitude and direction. Finding a cheapest path in this setting corresponds to finding a piece-wise linear path determined by points on the boundaries of the quads. In our solution approach, we discretize such boundaries by introducing border points and only consider segments connecting border points belonging to the same quad. While classic shortest path graph algorithms are available and applicable to the graphs originating from these border points, we design an algorithm that exploits the geometric structure of our scenario and show that this algorithm is more efficient in practice than classic graph-based algorithms. In particular, it scales better with the number of quads in the subdivision of the airspace, making it possible to find more accurate routes or to solve larger problems.

Cite as

Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen. Flight Planning in Free Route Airspaces. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jensen_et_al:OASIcs.ATMOS.2017.14,
  author =	{Jensen, Casper Kehlet and Chiarandini, Marco and Larsen, Kim S.},
  title =	{{Flight Planning in Free Route Airspaces}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{14:1--14:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.14},
  URN =		{urn:nbn:de:0030-drops-79047},
  doi =		{10.4230/OASIcs.ATMOS.2017.14},
  annote =	{Keywords: Flight planning, Geometric shortest path, Free route airspace, Vector weighted paths, Vector weighted planar subdivisions}
}

Search Results

Documents authored by Chiarandini, Marco

Flight Planning in Free Route Airspaces

Abstract

Cite as

Thanks for your feedback!

Could not send message