- Flight Planning in Free Route Airspaces.
- Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen.
In 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS), volume 59 of OASIcs, pages 14:1-14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2017.
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
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
open access (1.5 MB)
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
Other publications by the author.