Constraint Handling in Flight Planning

Anders Nicolai Knudsen, Marco Chiarandini, Kim Skak Larsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publication23rd International Conference on Principles and Practice of Constraint Programming
EditorsJ Christopher Beck
Publication date2017
ISBN (Print)978-3-319-66157-5
ISBN (Electronic)978-3-319-66158-2
Publication statusPublished - 2017
Event23rd International Conference on Principles and Practice of Constraint Programming - Melbourne, Australia
Duration: 28. Aug 20171. Sept 2017
Conference number: 23


Conference23rd International Conference on Principles and Practice of Constraint Programming
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Constraint Handling in Flight Planning'. Together they form a unique fingerprint.

Cite this