- Constraint Handling in Flight Planning.
- Anders N. Knudsen, Marco Chiarandini, and Kim S. Larsen.
In 23rd International Conference on Principles and Practice of Constraint Programming (CP), volume 10416 of Lecture Notes in Computer Science, pages 354-369. Springer, 2017.
Flight routes are paths in a network, the nodes of which
represent waypoints in a 3D space. A common approach to route planning
is first to calculate a cheapest path in a 2D space, and then to
optimize the flight cost in the third dimension.
We focus on the problem of finding a cheapest path through a network
describing the 2D projection of the 3D waypoints. In European airspaces,
traffic flow is handled by heavily constraining the flight
network. The constraints can have very diverse structures, among them
a generalization of the forbidden pairs type. They invalidate the FIFO
property, commonly assumed in shortest path problems. We formalize the
problem and provide a framework for the description, representation
and propagation of the constraints in path finding algorithms,
best-first, and A* search. In addition, we study a lazy approach to
deal with the constraints. We conduct an experimental evaluation based
on real-life data and conclude that our techniques for constraint
propagation work best together with an iterative search approach, in
which only constraints that are violated in previously found routes
are introduced in the constraint set before the search is restarted.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
open access (1.1 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.