Résolution du problème de construction des horaires mensuels d'une compagnie aérienne avec la méthode d'exploration de voisinage d'un ensemble initial de clusters

Les compagnies aériennes ont eu recours à la recherche opérationnelle pour résoudre efficacement une partie de leurs problèmes de gestion et de planification. Parmi ces derniers, on trouve le PCHMME (problème de construction d'horaires mensuels des membres d'équipage). Ce problème consiste à construire un horaire mensuel pour chaque membre d'équipage en lui affectant un ensemble de rotations ainsi que d'autres tâches telles que les vacances et les formations afin de construire un horaire mensuel pour ce membre. Une rotation représente une succession de vols séparés par des périodes de repos. Une rotation débute et se termine dans la même base (aéroport). L'horaire construit doit respecter l'ensemble des règles gouvernementales, les règles de la convention collective, etc. L'ensemble de rotations est construit durant une étape antérieure. Le problème de construction des horaires est un problème combinatoire et dont la complexité croît exponentiellement avec la taille du problème et le nombre de règles à respecter. La compagnie AD OPT offre des produits d'optimisation dans le domaine du transport aérien. Un de ces produits est dédié à la résolution du PCHMME. Ce dernier est basé sur un solveur qui utilise la programmation linéaire, en particulier l'approche de la génération de colonnes. L'objectif principal de ce travail est d'améliorer le temps de résolution du PCHMME pour une compagnie aérienne donnée. Cette dernière est classée parmi les plus grandes compagnies aériennes au monde suivant un classement basé sur la taille de la flotte et le nombre d'employés. La taille du PCHMME correspondant est alors très grande. Le personnel de cabine de cette compagnie est classifié dans des catégories telles que la catégorie CM qui regroupe les chefs de cabine et la catégorie FA qui regroupe la grande majorité du reste des membres de cabine. La caractéristique la plus importante pour le présent travail qui distingue ces deux catégories est la taille. En effet, la taille de la catégorie FA est beaucoup plus grande que celle de la catégorie CM. Le PCHMME est résolu d'une manière séquentielle, catégorie par catégorie. Dans ce travail, on propose l'utilisation de la solution de la catégorie CM afin d'accélérer la résolution de la catégorie FA, car la durée de résolution de cette dernière est beaucoup plus longue que celle de la catégorie CM. À partir de la solution de la catégorie CM, on construit un ensemble de clusters qui regroupe les rotations du problème de FA. Chaque cluster représente une succession de rotations. L'ensemble de clusters servira de cible durant la résolution des sous-problèmes de la catégorie FA. Seulement les chemins qui sont au voisinage de cet ensemble seront générés, ce qui permet de réduire le temps de résolution des sous-problèmes. Plusieurs méthodes ont été proposées afin de construire cet ensemble de clusters. Une de ces méthodes est basée sur l'utilisation d'un algorithme de flot à coût minimum pour obtenir un ensemble de clusters avec une cardinalité minimale. Au niveau de la résolution de la catégorie FA, on propose une approche améliorée de la génération de colonnes avec la MEV (méthode d'exploration de voisinage). Cette méthode est implémentée au niveau du sous-problème et permet de ne générer que les colonnes qui sont au voisinage de l'ensemble initial de clusters. On a également proposé plusieurs versions de la MEV pour déterminer la taille du voisinage à explorer durant la résolution des sous-problèmes. Parmi ces versions, on trouve la version dynamique de la MEV qui permet de déterminer une distance maximale permise par rapport à l'ensemble initial de clusters avant chaque résolution de sous problème. Cette valeur est déterminée suivant le nombre et la qualité des colonnes générées. La MEV permet également aux membres de la catégorie FA d'avoir un nombre minimum de chefs durant le mois. Cela a un impact positif sur la productivité de l'employé. La MEV n'a pas donné de bons résultats pour la compagnie étudiée, car cette dernière a plusieurs particularités qui nuisent à la MEV. Pour cette raison, on a proposé un raffinement de données afin de produire des données qui ressemblent plus aux celles des autres compagnies qui ont moins de caractéristiques qui vont à l'encontre de la MEV. Après avoir testé avec les nouvelles données, on n'a pas obtenu l'amélioration attendue. Ceci est dû à une mauvaise interaction entre la MEV et des algorithmes utilisés au niveau de l'approche de résolution existante dans le produit d'AD OPT.