Sélection dynamique des services de vols durant l'optimisation des rotations d'équipages aériens

Une problématique importante tant sur le plan financier que mathématiques d'une compagnie aérienne est la fabrication des horaires pour son personnel. Ceux-ci doivent respecter les contraintes légales ainsi que celles des conventions collectives. Alors que d'autres contraintes s'ajoutent à celles-ci, comme la satisfaction des employés qui est considérée dans la fabrication des emplois du temps pour certaines compagnies, nous aboutissons déjà à des problèmes de très grande taille parmi ceux du domaine de la Recherche Opérationnelle. Ils sont séparés en plusieurs problèmes d'optimisation résolus séquentiellement, dont l'un est au centre du travail de ce mémoire : la fabrication de rotations. Ce problème consiste à générer des rotations pour l'équipage de la compagnie à partir de services de vols. Nous appelons une rotation une partie d'un emploi du temps d'une durée variant généralement de 2 à 6 jours, partant et revenant à la base de l'équipage, et l'enchaînement de deux rotations est généralement séparé par une période de repos spéciale. Un service de vol est une séquence de vols séparés par des connections, effectué par un même équipage sur une durée d'une journée de travail. L'objectif à cette étape est de générer des rotations de faible coût, respectant toutes les contraintes, et dont nous pouvons sélectionner un sous-ensemble de coût minimal qui nous permette d'effectuer toutes les taches prévues, comme les vols à assurer. Elle se résout souvent, et c'est le cas dans ce mémoire, à l'aide d'une méthode de génération de colonnes. Cette génération est difficile car il y a une grande "dimension" combinatoire : le nombre de possibilités de concevoir une rotation à partir d'une séquence de services de vols est trop important pour que l'on imagine toutes les générer. Plusieurs techniques d'accélération de la résolution par génération de colonnes existent pour le problème maître (agrégation de contraintes, perturbation, stabilisation) comme pour les sous-problèmes (comme avec des algorithmes de programmation dynamique qui utilisent seulement des sous ensembles des arcs et des étiquettes). Dans le cas d'une résolution avec étiquettes pour la résolution, ce qui est actuellement généralisé, nous proposons d'utiliser les informations duales que nous pouvons récupérer de celles-ci afin de développer un critère de sélection dynamique d'arcs. Ainsi capable de sélection, nous présentons dans ce travail de maîtrise une nouvelle résolution du problème de génération de rotations par génération de colonnes. Nous réduisons le nombre d'arcs des sous-problèmes de plus de 80% pour constituer une banque d'arcs dans laquelle nous sélectionnons dynamiquement ceux que nous avons intérêt à ajouter dans les réseaux des sous-problèmes. Un logiciel de planification développé chez AdOpt, division spécialisée dans le transport aérien de la compagnie Kronos, appelé Altitude Pairing, est dédié à cette étape d'optimisation. Nous y avons implémenté le module développé, en s'attachant à le faire de façon modulaire ce qui permettra le développement de nouveaux outils sur cette base prometteuse. Cette implémentation a demandé une adaptation des concepts théoriques aux réalités du code. Les résultats montrent sur les jeux de données auxquels nous avons eu accès une diminution supérieure aux deux-tiers des temps de calculs dans les sous-problèmes, mais une augmentation du temps global de résolution : l'augmentation du temps de ré-optimisation du problème maître n'est pas suffisamment compensé par le temps gagné dans les sous-problèmes. Pour faire face à ce problème nous avons implémenté et testé deux modifications : la première consiste à relâcher le critère de sélection des arcs. La seconde est de limiter le nombre d'itérations en la banque d'arcs mise-à-jour et le réseau courant. Nous décidons de cette façon d'avoir moins d'itérations d'ajouts d'arcs, tout en augmentant le nombre d'arcs ajoutés. Cela démontre l'intérêt de cette méthode qui devra être testé sur des jeux de données plus complets à l'avenir, ainsi qu'être mieux intégrée dans la stratégie de résolution.