No d'ordre

David Gianazza

Description

Niveau: Supérieur, Doctorat, Bac+8

• redaction

No d'ordre : 2151 THÈSE présentée pour obtenir le titre de DOCTEUR DE L'INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE Discipline : Informatique École doctorale : Informatique et Télécommunications Spécialité : Programmation et Systèmes par David GIANAZZA OPTIMISATION DES FLUX DE TRAFIC AÉRIEN Soutenance le 2 novembre 2004 devant le jury composé de : M. Yves DUTHEN IRIT (Président du jury) M. Marc SCHOENAUER INRIA (Rapporteur) M. Patrick SIARRY Université Paris 12 (Rapporteur) M. Jean-Marc ALLIOT CENA/LOG (Directeur de thèse) M. Arnaud DEDRYVERE DNA (Membre du jury) M. Alain PRINTEMPS CENA (Membre du jury)

• méthode de classification par nuées dynamiques


• justification du choix des méthodes


• description de l'algorithme


• système saturé


• contexte de la gestion du trafic aérien


• cadre professionnel

Sujets

• Redaction
• Optimisation
• Rivière
• Printemps
• Granger

Informations

• Publié par: profil-feym-2012
• Publié le: 01 novembre 2004
• Nombre de lectures: 35
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

oN d’ordre : 2151
THÈSE
présentée pour obtenir le titre de
DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE
Discipline : Informatique
École doctorale : Informatique et Télécommunications
Spécialité : Programmation et Systèmes
par
David GIANAZZA
OPTIMISATION DES FLUX DE TRAFIC AÉRIEN
Soutenance le 2 novembre 2004 devant le jury composé de :
M. Yves DUTHEN IRIT (Président du jury)
M. Marc SCHOENAUER INRIA (Rapporteur)
M. Patrick SIARRY Université Paris 12 (Rapporteur)
M. Jean-Marc ALLIOT CENA/LOG (Directeur de thèse)
M. Arnaud DEDRYVERE DNA (Membre du jury)
M. Alain PRINTEMPS CENA (Membre du jury)Remerciements
Merci tout d’abord à Jean-Marc Alliot et Nicolas Durand, qui ont encadré ma thèse et avant cela
mon DEA. C’est grâce à eux que j’ai pris goût à la recherche et à l’informatique. Je les remercie de
m’avoir fait une place au sein du laboratoire dans des circonstances particulièrement difficiles de ma
vie. Sans leur soutien et leur amitié, rien n’aurait été possible.
Merci aussi à Pascal Brisset, pas seulement pour ses conseils éclairés en Ocaml, mais également
pour sa gentillesse, sa disponibilité, sa curiosité d’esprit, et pour les tiramizu, carrot cakes, et autres
pâtisseries étranges faites maison (merci à Sylvie également...). Merci à tous les autres membres du
LOG ainsi qu’à ceux du LEEA pour l’ambiance conviviale qu’ils savent si bien entretenir au quotidien.
Je pense en particulier à Géraud Granger, Nicolas Barnier, Thomas Rivière, Jean-Baptiste Gotteland,
Nathalie Lenoir, Christian Bontemps, et Kevin Guittet.
Je remercie Joseph Noailles pour sa gentillesse et son humanité. C’est aussi grâce à ses cours
d’optimisation, suivis durant mon DEA, que j’ai repris pied dans la voie scientifique.
Ma gratitude va également à Alain Printemps, chef du CENA, et à Dominique Colin de Verdière,
chef-ajoint du CENA, pour l’intérêt qu’ils ont porté à mes travaux et pour m’avoir permis de réaliser
cette thèse dans le cadre de ma vie professionnelle. Mon affectation au CENA/LOG a été grandement
facilitée par le soutien actif de Frantz Dissler et de Nicolas Dubois. Je ne les en remercierais jamais
assez.
Je tiens à remercier vivement MM. Marc Schoenauer et Patrick Siarry d’avoir bien voulu être
rapporteurs de cette thèse, et également M. Yves Duthen, président du jury, ainsi que M. Arnaud
Dedryvere qui a bien voulu participer au jury, aux côtés de Jean-Marc Alliot et d’Alain Printemps.
J’ai voulu limiter mes remerciements aux personnes rencontrées dans le cadre professionnel. Mais,
toute règle ayant ses exceptions, j’adresse un grand merci à Marie-Pierre et à mes filles, Typhaine et
Auriane, ainsi qu’à ma famille et à mes amis, notamment pour avoir supporté avec philosophie la
période de rédaction de ma thèse.
Je n’ose remercier le hasard, qui fait parfois si mal ou si bien les choses.
Tout ce qui existe dans l’univers est le
fruit du hasard etde lanécessité.
(Démocrite / vers 460-370 avant JC)
La vie de l’homme dépend de sa vo-
lonté; sans volonté, elle serait aban-
donnée au hasard.
(Confucius / 551 à 479 avant JC)Table des matières
1 Introduction 7
1.1 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Démarche de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Organisation du document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Le contexte de la gestion du trafic aérien 11
2.1 Présentation du système existant . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 La conception actuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.3 Un système saturé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Les évolutions possibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Les changements conceptuels . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 L’automatisation dans l’avion . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 L’automatisation des systèmes de contrôle aérien . . . . . . . . . . . . . . . 14
2.2.4 Conclusion sur les évolutions du trafic aérien . . . . . . . . . . . . . . . . . 15
2.3 Choix du contexte et des critères d’optimisation . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Une question de contexte (s)... . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 ... et aussi une question de critères . . . . . . . . . . . . . . . . . . . . . . . 18
3 Description des algorithmes 19
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Justification du choix des méthodes employées . . . . . . . . . . . . . . . . . . . . 20
3.3 Méthode de classification par nuées dynamiques . . . . . . . . . . . . . . . . . . . . 21
3.3.1 Généralités sur les méthodes de classification . . . . . . . . . . . . . . . . . 21
3.3.2 Partitions d’un ensemble àn éléments . . . . . . . . . . . . . . . . . . . . . 21
3.3.3 Les méthodes de partitionnement . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.4 Description de l’algorithme utilisé . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Diagrammes de Voronoï et triangulation de Delaunay . . . . . . . . . . . . . . . . . 25
3.4.1 Définition d’un diagramme de Voronoï . . . . . . . . . . . . . . . . . . . . 25
3.4.2 Dualité entre la triangulation de Delaunay et le diagramme de Voronoï . . . . 25
3.4.3 L’algorithme de Fortune . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.4 Implantation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5 Algorithmes d’exploration d’arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.5.1 Séparation & évaluation (Branch& bound) . . . . . . . . . . . . . . . . . . 32
∗3.5.2 L’algorithmeA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6 Algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
34 TABLE DES MATIÈRES
3.6.1 Principe et généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6.2 L’algorithme génétique classique . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6.3 Améliorations du principe de sélection . . . . . . . . . . . . . . . . . . . . . 39
3.6.4 Amélioration du principe de croisement . . . . . . . . . . . . . . . . . . . . 42
3.6.5 Amélioration du principe de mutation . . . . . . . . . . . . . . . . . . . . . 43
3.6.6 Optimisation sous contraintes avec des algorithmes évolutionnaires . . . . . 43
3.6.7 Une explication intuitive du fonctionnement des AG . . . . . . . . . . . . . 44
3.7 Conclusion sur la description des algorithmes . . . . . . . . . . . . . . . . . . . . . 45
4 Optimisation des regroupements de secteurs 49
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Description du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 Difficulté du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5 Algorithmes déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.6 Algorithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.7 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.7.1 Comparaison des algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.7.2 Comparaison entre schéma optimal et schéma déposé . . . . . . . . . . . . . 58
4.8 Etude statistique sommaire des dégroupements de secteurs . . . . . . . . . . . . . . 60
4.8.1 Démarche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.8.2 Valeurs des variables au moment du dégroupement . . . . . . . . . . . . . . 61
4.8.3 Comparaison des valeurs avant et après dégroupement . . . . . . . . . . . . 64
4.9 Conclusion sur l’optimisation des regroupements de secteurs . . . . . . . . . . . . . 67
5 Construction d’un réseau de routes 69
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2 Agrégation des points de croisement . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3 Construction d’un réseau par triangulation de Delaunay . . . . . . . . . . . . . . . . 74
5.4 Considérations sur la sectorisation associée au réseau de routes . . . . . . . . . . . . 75
5.5 Plus court chemin à travers le réseau de routes . . . . . . . . . . . . . . . . . . . . . 76
5.6 Conclusion sur la constr