OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Cooperation of Combinatorial Solvers for Air Traffic Management and Control

Wang, Ruixin. Cooperation of Combinatorial Solvers for Air Traffic Management and Control. PhD, Informatique et Télécommunication, Institut National Polytechnique de Toulouse, 2020

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


In the context of the SESAR project, Air Traffic Control (ATC) and Management (ATM) in Europe is undergoing a paradigm shift to be able to accommodate the current traffic growth forecast: many expert-based systems will be enhanced by optimization software to improve the decisionmaking process and regulation planning. Current state-of-the-art combinatorial optimization techniques that are applied to ATC and ATM include approximation algorithms like metaheuristics (e.g. Genetic Algorithm, Tabu Search, Simulated Annealing, etc.) and complete algorithms like Constraint Programming (CP) and Mixed Integer Programming. However, the large scale of the considered instances and the handling of their inherent uncertainties result in very hard problems, which can hinder or even defeat either of the previously mentioned optimization methods alone. To overcome these difficulties and improve the resolution efficiency of standard algorithms, we propose to study the generic cooperation of any set of combinatorial solvers by sharing solutions, optimization bounds and possibly other information in order to speed up the overall process. In this thesis, we have specified and implemented a distributed system which is able to integrate any combinatorial solver with the suitable interface, adapt existing solvers to take into account and provide information on the state of the search from and to other solvers, and applied this framework to two ATC and ATM problems: the en-route conflict resolution problem and the Gate Allocation Problem (GAP). For the first one, we have presented a new generic framework for the modeling and resolution of en-route conflicts in three dimensions as well as a large set of realistic instances, which have been solved with the cooperation of a Memetic Algorithm and Integer Linear Programming (ILP) solver. For the GAP, we have presented a new CP model, as well as new optimization constraints to maximize the robustness of the schedule, and search strategies together with their parallel cooperation. The solver, implemented with the FaCiLe CP library, outperforms a state-of-the-art ILP solver on real instances.

Item Type:PhD Thesis
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Laboratory name:
Research Director:
Durand, Nicolas and Barnier, Nicolas
Deposited On:01 Oct 2021 12:42

Repository Staff Only: item control page