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
Liste complète des métadonnées

Cited literature [15 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-01592235
Contributor : Laurence Porte <>
Submitted on : Friday, September 22, 2017 - 8:59:00 PM
Last modification on : Thursday, August 23, 2018 - 11:20:02 AM
Document(s) archivé(s) le : Saturday, December 23, 2017 - 2:24:21 PM

File

12th_ATM_RD_Seminar_paper_31.p...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01592235, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

382

Files downloads

77