Skip to Main content Skip to Navigation
Conference papers

Large Scale 3D En-Route Conflict Resolution

Abstract : En-route conflict resolution is a good example of a large-scale combinatorial optimization problem. On the one hand, it has been modeled in many different ways, most of the time depending on the tools that were proposed to solve it. On the other hand, many different resolution methods can be tested and compared on such problems but a common model needs to be used to validate the comparison. In this paper we extend the 2D-framework introduced in 2013, which separates the model from the solver. First, we introduce a 3D-model and add new refinements on the uncertainty model taking into account, inter alia, delays due to human factors. Second, we compare the performance of a complete Constraint Programming solver and an approximation algorithm based on a Memetic Algorithm, an efficient metaheuristic combining Genetic Algorithm with Tabu Search. To this aim, we generate a benchmark of conflict resolution problems built with scenarios involving 15 to 100 aircraft, 3 different levels of uncertainty and maneuvers in both horizontal and vertical planes. The two methods are able to efficiently solve moderate size problems in near real time, but the execution time of the complete algorithm exponentially rockets with larger instances whereas the metaheuristic scales much better with the number of aircraft. However, the former is able to prove optimality or infeasibility on reasonable problems, which allows the assessment of the quality of the solutions produced by the latter.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Laurence Porte Connect in order to contact the contributor
Submitted on : Friday, September 22, 2017 - 8:59:00 PM
Last modification on : Tuesday, October 19, 2021 - 11:02:50 AM
Long-term archiving on: : Saturday, December 23, 2017 - 2:24:21 PM


Files produced by the author(s)


  • HAL Id : hal-01592235, version 1



Cyril Allignol, Nicolas Barnier, Nicolas Durand, Alexandre Gondran, Ruixin Wang. Large Scale 3D En-Route Conflict Resolution. ATM Seminar, 12th USA/Europe Air Traffic Management R&D Seminar, Jun 2017, Seattle, United States. ⟨hal-01592235⟩



Record views


Files downloads