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.

Abstract

One of airline industry's major financial and mathematical issue is scheduling. An airline schedule has to comply to a lot of legal constraints and labor agreements. Without considering other additional constraints, we already are facing a huge optimization problem. This one is traditionally separated in several sequential optimization problems, among which is the one considered in this Maîtrise: pairing generation. This problem's objective is to generate pairings for airline personnel from duties. A pairing is part of a schedule, usually lasting from 2 to 6 days, starting and ending at the crew's designated base, and two pairings usually have a special rest inbetween. a duty is a flight sequence inbetween connections, that are flown by the same crew and lasts one day. Here we have to generate pairings with low costs, that comply with all constraints, and enabling us to covering each and every flight that is scheduled, using a sub-set of them. It is often solved using column generation techniques, as it is in this present work. It is a hard generation because of the huge number of possibilities to generate a sequence of duties from a set of duties. In fact, we won't be able to generate all of the possible pairings because there are way too many. Several acceleration techniques are used for column generation, from master problem (constraints aggregation, perturbation or stabilization) to sub-problem (labelling algortihm for example). In this latter case, which is nowadays used a lot, we suggest to use dual informations from these labels, aiming to create a criteria for a dynamique selection of arcs. Now capable of selecting arcs according to this criteria, we present a new resolution of pairing generation using column generation. We use reduced subproblems networks with at most 20% initial arcs, the other put into a "bank". From this bank will be dynamically selected interesting arcs to subproblems networks. A dedicated software developped at AdOpt, specialized division in airline transportation industry of company Kronos, is called Altitude Pairing. We implemented in it our module, making sure all the processus would be modular. This is necessary so that our tools can be used in the future. Results show that on our three data sets, time spent in subproblems was reduced but that the Master Problem resolution took longer which led to an overall resolution time also longer. The subproblem time improvement did not compensate for the deterioration of the Master Problem time resolution. To overcome these difficulties, we decided to implement two main modifications: relax our criteria that determines if an arc can lead to an interesting column or not, and limit the number of dynamic arc adding. We thus enable our algorithm to add more arcs but less frequently. These modifications led tovery positive results: we reached a better end value in a shorter time. This demonstrates this method's quality: it still has to be tested on bigger data sets, and the overall resolution strategy has to be adapted to this new module in a better way.