Large Scale 3D En-Route Conflict Resolution - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Communication Dans Un Congrès Année :

Large Scale 3D En-Route Conflict Resolution


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.
Fichier principal
Vignette du fichier
12th_ATM_RD_Seminar_paper_31.pdf (450.76 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01592235 , version 1 (22-09-2017)


  • 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⟩
399 Consultations
250 Téléchargements


Gmail Facebook Twitter LinkedIn More