No d'ordre

Charles - Edmond Bichot

Description

Niveau: Supérieur, Doctorat, Bac+8
No d'ordre : 2534 THÈSE présentée pour obtenir le titre de DOCTEUR DE L'INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE Par : Charles-Edmond BICHOT École doctorale : Informatique et Télécommunications Spécialité : Sûreté du Logiciel et Calcul à Haute Performance Laboratoire d'accueil : Laboratoire d'Optimisation Globale (DSNA/ENAC) ÉLABORATION D'UNE NOUVELLE MÉTAHEURISTIQUE POUR LE PARTITIONNEMENT DE GRAPHE : LA MÉTHODE DE FUSION-FISSION. APPLICATION AU DÉCOUPAGE DE L'ESPACE AÉRIEN Soutenu le 9 novembre 2007 devant le jury composé de : MM. Patrick SIARRY Université Paris XII Rapporteur, Président du jury El-Ghazali TALBI Université de Lille I Rapporteur MM. François PELLEGRINI ENSEIRB Membre du jury Jean-Marc ALLIOT DSNA Membre du jury MM. Joseph NOAILLES ENSEEIHT Directeur de thèse Nicolas DURAND DSNA Codirecteur de thèse

• partitionnement


• description formelle du problème du partitionnement de graphe


• approches infructueuses pour le découpage de l'espace aérien


• direction des services de la navigation aérienne


• méthodes classiques de partitionnement de graphe


• blocs entre pays européens


• dsna


• découpage

Sujets

• Brisset
• Rivière
• Institut national polytechnique de Toulouse
• Laboratoire d'optimisation globale
• Noailles
• Descartes
• Barnier

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 novembre 2007
• Nombre de lectures: 63
• Langue: Français
• Poids de l'ouvrage: 5 Mo

Extrait

oN d’ordre : 2534
THÈSE
présentée pour obtenir le titre de
DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE
Par : Charles-Edmond BICHOT
École doctorale : Informatique et Télécommunications
Spécialité : Sûreté du Logiciel et Calcul à Haute Performance
Laboratoire d’accueil : Laboratoire d’Optimisation Globale (DSNA/ENAC)
ÉLABORATION D’UNE NOUVELLE MÉTAHEURISTIQUE POUR LE
PARTITIONNEMENT DE GRAPHE : LA MÉTHODE DE FUSION-FISSION.
APPLICATION AU DÉCOUPAGE DE L’ESPACE AÉRIEN
Soutenu le 9 novembre 2007 devant le jury composé de :
MM. Patrick SIARRY Université Paris XII Rapporteur, Président du jury
El-Ghazali TALBI Université de Lille I
MM. François PELLEGRINI ENSEIRB Membre du jury
Jean-Marc ALLIOT DSNA du jury
MM. Joseph NOAILLES ENSEEIHT Directeur de thèse
Nicolas DURAND DSNA Codirecteur de thèseRésumé : Dans cette thèse, nous étudions des méthodes de partitionnement de graphe et les
appliquons au découpage de l’espace aérien, ainsi qu’à d’autres problèmes. L’espace aérien est composé
de volumes limités, appelés secteurs de contrôle, chacun étant sous la responsabilité d’un contrôleur.
Chaque contrôleur est habilité sur un ensemble de secteurs, appelé zone de qualification. Les secteurs
sont également regroupés en centres de contrôle, qui englobent au moins une zone de qualification.
Dans le cadre du ciel unique européen, la Commission européenne a prévu la création de blocs
fonctionnels d’espace aérien. La création de ces blocs entre pays européens entraînera probablement un
redécoupage des centres actuels. Cette thèse propose des outils d’aide à la conception d’un nouveau
découpage de l’espace européen en centres et en zones de qualification. À cet effet, plusieurs méthodes
sont étudiées : des méthodes de partitionnement classiques, comme l’expansion de région, le
multiniveaux ou les algorithmes de type Kernighan-Lin ; des métaheuristiques, comme le recuit simulé, les
algorithmes de colonies de fourmis et les algorithmes évolutionnaires ; et une nouvelle méthode que
nous avons mise au point, la fusion-fission. C’est cette dernière qui permet de trouver les découpages
les plus performants, au sens de la fonction de coût utilisée, pour le découpage de l’espace aérien.
Afin de diversifier ses applications, nous l’avons aussi adaptée à la segmentation d’images et à la
classification de documents. Enfin, la qualité de cette méthode a été éprouvée sur les bancs de tests
classiques du partitionnement de graphe et confrontée aux méthodes concurrentes. Elle a permis de
trouver pour plusieurs problèmes de test des partitions dont le coût est le plus bas obtenu jusqu’à
présent.
Mots clés : Graphe, partition, fusion-fission, contrôle aérien, métaheuristique, multi-niveaux, affinage,
spectrale
Abstract : This thesis studies graph partitioning methods and applies them to airspace partitioning
and other partitioning problems. Each air traffic controller supervises a limited space, called an air
traffic sector. Controllers have qualifications to work only on a set of sectors, called qualification air
zone. Sectors are grouped together into control centers wich include almost one qualification air zone.
The European single sky project intended by the European Commission could involve a new airspace
partitioning into control centers and qualification air zones. In this framework, this thesis proposes
some tools to design the airspace. Classical graph partitioning methods are studied (load-balancing,
region growing and multilevel algorithms), a well as some metaheuristics (simulated annealing, ant
colonies and evolutionary algorithms). A new method is introduced in this thesis : the fusion-fission
method. Compared with the others, this method allows to find the best airspace partitioning for our
objective function. To diversify its applications, the fusion-fission method has also been applied to
image segmentation and documents clustering. Finally, it has been tested on classical benchmarks
and compared with contestant methods. On benchmarks, it finds some new partitions which have the
lowest cut ever found.
Key words : Graph, partition, fusion-fission, airspace control, metaheuristic, multilevel, load
balancing, spectral
LABORATOIRE D’OPTIMISATION GLOBALE
DIRECTION DES SERVICES DE LA NAVIGATION AÉRIENNE
ÉCOLE NATIONALE DE L’AVIATION CIVILE
7 avenue Édouard Belin - BP 54005
31055 Toulouse cedex 4Remerciements
« Je trouve ici que la pensee´ est un attribut qui m’appartient : elle seule
ne peut etreˆ detach´ ee´ de moi. [. . .] Je ne suis donc, precis´ ement´ parlant,
qu’une chose qui pense»
« De cela memeˆ que je suis une substance, je n’aurais pas neanmoins´
l’idee´ d’une substance infinie, moi qui suis un etreˆ fini, si elle n’avait et´ e´
mise en moi par quelque substance qui futˆ veritablement´ infinie.»
Ren´ e´ Descartes. Les meditations´ sur la philosophie premier` e, 1641.
Merci a` tous ceux qui m’ont aide´ et supporte´ pendant ces trois annees´ de these.` Cette experience´
formidable et tellement enrichissante n’aurait pas et´ e´ possible sans eux, sans vous. Mes premiers
remerciements vont donc a` tous ceux, tres` proches ou lointains, qui ont participe´ a` ma vie pendant
cette periode.´ Cependant, des remerciements specifiques´ meritent´ d’etreˆ adresses´ aux personnes qui
ont particulierement` contribue´ au bon deroulement´ de cette these.`
C’est a` Jean-Marc Alliot et a` Nicolas Durand, par l’intermediaire´ de Pascal Brisset, que je dois
l’opportunite´ d’avoir fait cette these.` En effet, ils m’ont tout d’abord propose´ de realiser´ mon stage
de DEA, appele´ maintenant master recherche, au sein du Laboratoire d’optimisation globale, puis ils
ont eu la gentillesse de m’accepter en these,` de me laisser beaucoup d’autonomie, ce qui m’a permis
d’explorer mes propres chemins de recherche, de relire mes papiers et de me permettre d’aller a` de
nombreuses conferences.´ Je leur suis vraiment reconnaissant pour tout cela.
J’ai eu la chance d’avoir pour rapporteurs Patrick Siarry qui ma si souvent utilement conseille´
pendant celle-ci et El-Ghazali Talbi qui a toujours soutenu mes travaux ; je voudrais les remercier tout
particulierement.` Ma gratitude va aussi a` Joseph Noailles, mon directeur officiel de these` et a` Franc ¸ois
Pellegrini pour ses remarques sur ma these` et mon annee´ de post-doctorat dans son equipe.´
Merci aussi a` tous les membres du LOG, de la DSNA/DTI, du LEEA et de l’ENAC avec qui j’ai
et´ e´ en contact et qui m’ont si bien accueilli parmi eux. J’ai une pensee´ toute particuliere` pour Nicolas
Archambault qui doit faire face au terrible accident qu’il a eu. Je voudrais aussi remercier chaudement
Jean-Baptiste Gotteland qui a toujours tres` gentiment supporte´ mes fantaisies en tant que collegue` de
bureau, Pascal Brisset pour ses conseils varies´ allant du Caml au nutritionel, Nicolas Barnier pour
ses debats´ passionnes,´ Thomas Riviere` pour bomberman, David Gianazza pour ses relectures, Estelle
Malavolti pour sa bonne humeur et Kevin´ Guittet pour nos petites soirees´ au London Town. Je souhaite
maintenant beaucoup de bons moments et de persev´ erance´ a` Pierre-Selim´ Huard et Cyril Allignol qui
sont les nouveaux doctorants du laboratoire.Si mes remerciements sont profonds et sinceres` a` tous ceux qui etaient´ pres` de moi sur le plan
professionnel, ils sont tout aussi et sinceres` a` ceux qui m’ont entoures´ sur le plan familial
et amical. Je remercie toute ma famille et specialement´ mes parents pour leur soutient et je souhaite
beaucoup d’endurance a` ma mere` qui est en train de passer sa these.` Je remercie vivement tous mes
´ ´amis, ceux qui ont compris ma mauvaise disponibilite, ceux qui ont eu la patience d’ecouter mes
idees,´ et je remercie en particulier mes amis toulousains qui ont si bien su me supporter pendant cette
periode.´ Enfin, je remercie ma future femme, Caroline, qui a su etreˆ si patiente pendant la duree´ de
ma these` et a` qui je dedie´ celle-ci.Table des matières
Introduction générale 1
1 Introduction au problème du partitionnement de graphe 7
1.1 Notions mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Graphes . . . . . . . .