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.

Abstract

Airlines have used operational research to effectively resolve some of the management and planning issues they face. Among these, we find the crew rostering problem CRP which consists in assigning for each given crew member, a set of pairings as well as other tasks such as vacations and training in order to build a monthly schedule for this crew member. The schedule built must comply with all government rules and the rules of the collective agreement. The set of pairings is built during an earlier stage (a pairing represents a succession of flights and starts and ends at the same airport). The CRS is a combinatorial problem and its complexity increases proportionally with the size of the problem and the number of rules to be respected. The company AD OPT offers optimization products in the aviation sector. One of these products is dedicated to the resolution of CRP. The latter is based on a solver that uses linear programming, in particular the column generation approach. The main objective of this work is to improve the time consumption of CRP for a given airline. This airline is ranked among the largest airlines in the world according to a ranking based on the size of the fleet and the number of employees. Therefore the size of the corresponding CRP is very large. The cabin crew members of this company are classified into categories and their CRP is solved sequentially category by category. In this work, we focus on the category of the cabin managers and the FA category which represents the rest of the members. These two categories have a lot in common, for that reason, we propose to use the solution of the cabin managers category in order to speed up the resolution of the FA category because the size of the latter is larger and takes much longer to solve. From the solution of the cabin managers category, we build a set of clusters which groups together the pairing of the FA problem. Each cluster represents a succession of pairings. The set of clusters is used as a target during the resolution of sub-problems of FA category. Only paths in the neighborhood of this set will be generated. This will reduce solving time of the subproblems. Several methods have been proposed in order to build this set of clusters. One of these methods is based on the use of a minimum cost flow algorithm to obtain a set of clusters with minimum cardinality. To resolve the FA category, we propose an improved approach of the column generation method. This approach is based on a neighborhood search method (NSM). This method is implemented at the subproblem level and only generates the columns which are in the neighborhood of the initial set of clusters. Several versions of the NSM have been proposed in order to determine the size of the neighborhood to explore during the resolution of the sub-problems. Among these versions, there is the dynamic one which determines before each resolution of the sub-problems, a maximum distance allowed with respect to the initial set of clusters. This value represents the size of the neighborhood to explore and it is determined according to the number and quality of the columns generated. After testing with the new data, we did not get the expected improvements. This is due to the harmful e˙ects of the dominance heuristic. This heuristic eliminates paths in a quasi-random way during the resolution of the sub-problems. The NSM also allows FA members to have a minimum of change of managers, during the month. This has a positive impact on the productivity of the employee. The NSM did not give very improving results for the company studied because the latter has several characteristics which harm the process of the NSM. For this reason, a refinement of data has been proposed to produce data that have less characteristics which go against NSM which and it is more like other companies data. After testing with the new data, we did not get the expected improvements. This is principally due to the harmful effect of the existing heuristics.