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