Génération de colonnes pour la résolution du problème de resectorisation dynamique

Session : GC / Génération de colonnes
Vendredi 12 février 10:30 - 11:50 Salle : CI2-07
Tambet Treimuth, Daniel Delahaye et Sandra Ulrich Ngueveu

Au cours de ces dernières décennies, au fur et à mesure de l’augmentation du trafic, l’espace aérien a été divisé en secteurs de plus en plus petits afin d’éviter la saturation de ces derniers.Ce principe de sectorisation présente une limite dans la mesure où l’on doit ménager un temps suffisant au contrôleur pour gérer son trafic et donc générer des secteurs dont la taille permet de satisfaire cette contrainte. Il est donc nécessaire d’optimiser la planification sur une journée du schéma de regroupement et de dégroupement des secteurs : resectorisation dynamique de l’espace aérien. Un des objectifs est de fournir des groupes de secteurs présentant un minimum de coordinations et équilibrés en terme de charge de contrôle afin que chaque équipe de contrôleurs travaille de la même façon. La méthode de résolution proposée est un algorithme de type branch-and-price où chaque problème maître ne comprenant qu’un sous-ensemble de variables est résolu par un solveur linéaire et chaque sous-problème est résolu par un algorithme spécialement conçu de génération de configurations valides de coût réduit négatif. Les résultats préliminaires en démontrent la performance.

Mots clés : gestion du trafic aérien, sectorisation de l’espace aérien, décomposition de Dantzig-Wolfe, génération de colonnes partitionnement de graphe