É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

摘要

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. 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- ission 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