Résumé

L'augmentation du trafic aérien génère des problèmes d'optimisation très complexes pour le Contrôle Aérien. Le problème d'optimisation de trajectoires pour la résolution de conflits en route reste aujourd'hui ouvert. Dans cette thèse, l'approche initiale est d'étudier le problème de conflit à deux avions comme un problème de commande optimale avec contrainte sur l'état. Cette approche permet de dégager certaines propriétés des trajectoires optimales. L'étude théorique de la structure de l'ensemble des trajectoires admissibles fait apparaître le caractère fortement combinatoire du problème. Des applications numériques effectuées avec un algorithme de type gradient permettent alors d'illustrer les résultats théoriques et de constater l'inefficacité des méthodes locales. Dans un deuxième temps, les résultats théoriques sont exploités afin de définir les premiers éléments de modélisation du problème réel permettant de tenir compte des contraintes opérationnelles liées au contexte du contrôle du trafic aérien. Le caractère global et fortement combinatoire du problème d'optimisation conduit à utiliser les algorithmes génétiques. Ceux-ci permettent d'approcher plusieurs solutions différentes proches de l'optimum. Un opérateur de croisement adapté aux fonctions partiellement séparables est introduit dans les algorithmes génétiques de manière à pouvoir résoudre des conflits pouvant impliquer jusqu'à une vingtaine d'avions en temps réel avec de faibles populations. Les résultats sont illustrés par plusieurs exemples.

Mots clés :

Contrôle du trafic aérien, résolution de conflits, algorithmes génétiques, séparabilité partielle, optimisation combinatoire, optimisation global.

Abstract

As air traffic keeps increasing, the resolution of En Route conflicts is becoming a serious concern, especially in Europe. In this thesis, the two aicraft conflict problem is first studied as an optimal command problem with state constraints : this study enlights some interesting properties of the optimal trajectories. The structure of the admissible trajectories set makes the problem combinatorial. Numerical tests run with local optimization tools confirm that local optimization algorithms are not suited to solve such problems. The theoretical results are then used to build a model that can handle many aircraft and Air Traffic Control real constraints. As the optimization problem is global and combinatorial, Genetic Algorithms are suited to it. Furthermore, Genetic Algorithms find several local optima near the global optimum. Genetic operators adapted to partially separable functions are introduced in order to improve the algorithms efficiency on conflicts problems involving up to 20 aircraft.

Keywords :

Air trafic control, conflict solving, genetic algorithms, partial separability, combinatorial optimization, global optimization.

Remerciements

J'adresse de sincères remerciements aux membres du jury qui ont accepté de juger ce travail.

Monsieur Paul Bourgine du CREA à l'Ecole Polytechnique, qui m'a fait l'honneur d'être rapporteur de ces travaux.
Monsieur Philippe Toint, professeur à l'Université de Namur, qui m'a fait l'honneur d'être rapporteur de ces travaux.
Monsieur Gérard Padiou, professeur à l'ENSEEIHT, pour l'honneur qu'il me fait d'être examinateur.
Monsieur Dominique Colin de Verdière, chef adjoint du CENA, qui m'a fait confiance dans l'orientation de mes travaux auxquels il a toujours porté un grand intérêt.
Monsieur Joseph Noailles, mon directeur de thèse, pour m'avoir fait confiance en me proposant cette thèse, pour ses précieux conseils, sa disponibilité et que j'espère n'avoir pas deçu.
Jean-Marc Alliot, qui a toujours été présent, et m'a continuellement soutenu et guidé durant trois ans.
Monsieur Xavier Fron, du Centre Expérimental Eurocontrol de Brétigny, membre invité du jury.

Mes remerciements vont également aux personnes du laboratoire Informatique et Mathématiques Appliquées de l'ENSEEIHT, et notamment l'équipe Algorithmique Parallèle et Optimsation du deuxième étage pour leur aide durant ma première année de thèse et pour la bonne ambiance qui règne au deuxième étage. Je remercie particulièrement Jean-Yves L'Excellent et Samuel Gruska avec qui j'ai partagé le bureau, et qui m'ont beaucoup aidé à commencer mes travaux.

Je tiens à exprimer mes remerciements aux personnes avec qui j'ai pu travailler à l'ENAC, Nicolas Alech, Frédéric Médioni, Olivier Chansou, Jean-Baptiste Gottland, Yann Lefablec, Daniel Delahaye et Jean-François Bosc, sans oublier Christophe Bontemps et Isabelle Alliot.

J'exprime ma reconnaissance à Stéphane Chatty, Ruby et Laurence Garcia pour leur aide dans mes démarches administratives.

Enfin, je remercie Monsieur Jean-Marc Garot, Directeur du centre expérimental EUROCONTROL de Brétigny, de m'avoir permis de faire cette thèse au CENA, et de m'avoir fait confiance dans les orientations prises.

This document was translated from L^AT_EX by H^EV^EA.

This document was cut into pieces by H^AC^HA.