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.
Type de document :
Communication dans un congrès
ATM Seminar, 12th USA/Europe Air Traffic Management R&D Seminar, Jun 2017, Seattle, United States
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
Contributeur : Laurence Porte <>
Soumis le : vendredi 22 septembre 2017 - 20:59:00
Dernière modification le : jeudi 23 août 2018 - 11:20:02
Document(s) archivé(s) le : samedi 23 décembre 2017 - 14:24:21


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers