Constraint Handling in Flight Planning

Anders Nicolai Knudsen, Marco Chiarandini, Kim Skak Larsen

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
Titel23rd International Conference on Principles and Practice of Constraint Programming
RedaktørerJ Christopher Beck
ForlagSpringer
Publikationsdato2017
Sider354-369
ISBN (Trykt)978-3-319-66157-5
ISBN (Elektronisk)978-3-319-66158-2
DOI
StatusUdgivet - 2017
Begivenhed23rd International Conference on Principles and Practice of Constraint Programming - Melbourne, Australien
Varighed: 28. aug. 20171. sep. 2017
Konferencens nummer: 23

Konference

Konference23rd International Conference on Principles and Practice of Constraint Programming
Nummer23
LandAustralien
ByMelbourne
Periode28/08/201701/09/2017
NavnLecture Notes in Computer Science
Vol/bind10416
ISSN0302-9743

Fingeraftryk Dyk ned i forskningsemnerne om 'Constraint Handling in Flight Planning'. Sammen danner de et unikt fingeraftryk.

  • Citationsformater

    Knudsen, A. N., Chiarandini, M., & Larsen, K. S. (2017). Constraint Handling in Flight Planning. I J. Christopher Beck (red.), 23rd International Conference on Principles and Practice of Constraint Programming (s. 354-369). Springer. Lecture Notes in Computer Science, Bind. 10416 https://doi.org/10.1007/978-3-319-66158-2_23