Trois variantes du problème de rotations pour une approche semi-intégrée de la planification d'horaires de personnel aérien

Les horaires d'équipages aériens sont généralement créés à l'aide d'une procédure séquentielle impliquant la résolution de deux problèmes : le problème de rotations d'équipage (CPP) et le problème d'horaires personnalisés (CRP). Le CPP crée un ensemble de rotations couvrant tous les vols d'une période donnée à coût minimum. Une rotation est une séquence de vols, repositionnements, connexions et repos s'étalant sur un ou plusieurs jours, et qui doit être assignée à un équipage composé de plusieurs membres (pilote, copilote, agent de bord, etc.). Une rotation doit également débuter et se terminer à la même base (aéroport où sont affectés des membres d'équipage), et satisfaire plusieurs contraintes imposées par les autorités, ainsi que par les conventions collectives en place. Le CRP utilise les rotations créées par le CPP afin de construire un horaire personnalisé pour chaque membre d'équipage. Les horaires personnalisés doivent couvrir toutes les rotations et doivent également satisfaire un ensemble de contraintes. Le principal désavantage de cette procédure séquentielle est que l'ensemble de rotations générées par le CPP est généralement inadéquat pour le CRP. Par exemple, certains vols doivent être opérés par un équipage possédant des qualifications spécifiques (e.g. des qualifications de langues). Il est possible que dans la solution du CPP, ces vols soient dispersés dans un grand nombre de rotations, de sorte qu'il soit impossible de créer un horaire respectant toutes les contraintes de qualification. Idéalement, il serait préférable de résoudre un seul problème d'optimisation intégrant la création de rotations et la composition d'horaires personnalisés. Bien que de telles approches aient été proposées dans la littérature, les temps de calcul nécessaires à l'obtention de solutions de qualité sont prohibitifs pour des instances de grande taille. Les approches semi-intégrées permettent de surmonter certaines limites de l'approche séquentielle, en évitant les conséquences négatives des approches intégrées. Ces méthodes sont des variantes de l'approche séquentielle dans lesquelles la formulation mathématique du CPP est enrichie. L'idée est d'inclure dans le CPP certains éléments qui sont traditionnellement traités au niveau du CRP, afin de créer des rotations qui sont mieux adaptées au CRP. Dans cette thèse, nous étudions trois variantes du CPP qui conviennent aux approches semiintégrées. Chacune de ces variantes est définie comme un problème de partitionnement d'ensemble avec contraintes supplémentaires dans lequel les variables de décision principales sont associées à des rotations réalisables. Ces problèmes sont résolus par un algorithme de génération de colonnes qui utilise un problème maître restreint pour sélectionner les rotations et des sous-problèmes pour générer des rotations à ajouter au problème maître restreint. Dans le premier sujet de cette thèse, nous nous intéressons au CPP avec contraintes de base (CPPBC). Les contraintes de base pénalisent le temps de travail excédentaire à chaque base, afin de distribuer équitablement la charge de travail entre les différentes bases. Bien que la plupart des logiciels commerciaux incorporent des contraintes de base dans le CPP, aucune étude scientifique ne s'est penchée sur leur impact sur le processus de résolution du CPP. Nous montrons qu'en présence de contraintes de base assez restrictives, les algorithmes de branchement heuristiques traditionnellement utilisés peinent à obtenir une solution entière de qualité. Ces algorithmes prennent un plus grand nombre de décisions de branchement risquées, ce qui nuit à la qualité des solutions obtenues. Afin de remédier à ce problème, nous développons un algorithme de branchement heuristique, appelé branchement rétrospectif, qui élimine certaines mauvaises décisions de branchement lorsque l'écart relatif entre la meilleure solution fractionnaire et la solution fractionnaire au noeud courant est trop grand, et ce, sans avoir à effectuer de retour en arrière. L'algorithme de branchement rétrospectif est testé sur sept instances hebdomadaires. Nous montrons que le branchement rétrospectif permet d'obtenir des solutions de meilleure qualité qu'avec les autres méthodes de branchement couramment utilisées, en des temps de calcul raisonnables. L'algorithme de branchement rétrospectif est présentement implémenté dans un logiciel commercial de planification aérienne, et a été utilisé afin d'obtenir des solutions de qualité pour des problèmes contenant plusieurs dizaines de milliers de vols par mois. Dans le deuxième article de cette thèse, nous proposons une variante du CPP, appelée CPP avec caractéristiques complexes (CPPCF), qui prend en compte les préférences de vols et de vacances des membres d'équipage, dans le but d'augmenter la satisfaction de ceux-ci envers leurs horaires. Pour ce faire, nous identifions six caractéristiques des rotations en lien avec les préférences des membres d'équipage et qui pourraient être bénéfiques au CRP. Un bonus est accordé aux rotations contenant une ou plusieurs de ces caractéristiques, de manière à favoriser leur présence dans la solution retournée. La méthode de résolution du CPP est adaptée au CPPCF : nous modifions les règles de dominance de l'algorithme d'étiquetage utilisé pour résoudre les sous-problèmes. Cela permet de résoudre les sous-problèmes du CPPCF en des temps raisonnables. L'efficacité de cette méthode est démontrée sur sept instances mensuelles. Nous montrons que les solutions obtenues à l'aide du CPPCF permettent la création d'horaires personnalisés dans lesquels un plus grand nombre de préférences sont accordées, augmentant ainsi la satisfaction des membres d'équipage. Le troisième sujet de cette thèse porte sur les contraintes de langues. Il s'agit de contraintes sur les qualifications linguistiques pour l'équipage de certains vols. Cette recherche est fectuée dans un contexte de création d'horaires pour les agents de bord. Le respect des contraintes de langues est primordial pour les compagnies aériennes qui désirent offrir un service sécuritaire et de qualité. Or, les méthodes actuelles sont inadéquates pour traiter les problèmes contenant un grand nombre de contraintes de langues et peu de membres d'équipage parlant ces langues. En effet, le CPP ne prend pas en considération les contraintes de langues, de sorte que les vols qui possèdent des contraintes de langues similaires se retrouvent distribuées dans un grand nombre de rotations. Nous formulons le CPP avec contraintes de langues (CPPLC), une variante du CPP qui favorise le regroupement de plusieurs vols ayant les mêmes contraintes de langues à l'intérieur d'une rotation. La difficulté principale que pose cette variante est l'explosion combinatoire du nombre de sous-problèmes. Nous mettons de l'avant une stratégie de sélection de sous-problèmes dans laquelle un petit ensemble de sous-problèmes prometteurs est résolu à chaque itération de génération de colonnes. Nous développons également une stratégie d'accélération permettant de diminuer significativement les temps de calcul au début du processus de résolution. Nous montrons que l'utilisation du CPPLC permet de réduire considérablement le nombre de contraintes de langues violées dans les horaires personnalisés. Bien que seules les contraintes de langues soient traitées, la méthode proposée pourrait également s'appliquer à une grande variété de contraintes de qualification, autant pour les agents de bord que pour les pilotes et copilotes.

Abstract

Aircrew scheduling is usually performed according to a two-step sequential procedure: crew pairing and crew rostering. While the crew pairing problem (CPP) finds a set of pairings that covers the legs of a given period at minimum cost, the crew rostering problem (CRP) uses those pairings in order to create a personalized schedule for each crew member. A pairing is a sequence of legs, deadheads, connections and rests spanning over one or multiple days, and that can be assigned to a crew member. A pairing must also begin and end at the same crew base (airport where crew members are stationed), and comply with many rules imposed by airline authorities as well as collective agreements. The crew schedules must cover all pairings, and are also subject to many regulations. The main drawback of this sequential approach is that the set of pairings produced by the CPP is often ill-suited for the CRP. For instance, the CPP solution might assign too much work to a given base, resulting in an imbalance in the work distribution among the bases. Ideally, both steps would be integrated into a single optimization problem. Even though many such approaches have been proposed in the literature, computing times required to solve those integrated problems are prohibitive, even for small-sized instances. Semi-integrated approaches are designed to overcome some limitations of the sequential approaches, without unduly increasing computing times. The main idea is to solve a variant of the CPP that includes some elements that traditionally belong in the CRP. This enables the CPP to create pairings that are better-suited for the CRP. In this thesis, we study three such CPP variants. Each variant is formulated as a setpartitionning problem with additional constraints, in which the main decision variables are associated with feasible pairings. These problems are solved by a column generation algorithm that uses a restricted master problem to select the pairings and multiple subproblems to generate the pairings to add to the restricted master problem. In the first subject of this thesis, we study the CPP with base constraints (CPPBC). Base constraints penalize excess work performed at each crew base in order to evenly distribute the workload among them. Although most commercial softwares include base constraints in the CPP, no academic research has studied their impact on the existing solution methods. Preliminary tests show that when base constraints are very restrictive, the heuristic branching algorithms traditionally used struggle to find a good-quality integer solution: they take a larger number of risky branching decisions, which negatively impact the quality of the solutions. We develop a new heuristic branching scheme, called retrospective branching, that identifies risky branching decisions in the branch-and-bound tree, and removes poor branching decisions when the gap between the current and the best fractional solution becomes too large, without backtracking. The proposed method is tested on seven weekly instances. We show that the retrospective branching algorithm produces solutions of better quality than with the other commonly used branching methods, in reasonable computing times. The retrospective branching is currently implemented in a commercial crew scheduling software, and has been used to obtain good-quality solutions to monthly instances containing tens of thousands of legs. In the second subject of this thesis, we propose a variant of the CPP, called the CPP with complex features (CPPCF) which takes into account legs and vacations preferences of crew members, with the aim of increasing the number of preferences awarded in the CRP, and thus, crew member satisfaction towards their schedule. We identify six pairing features related to those preferences, which could be beneficial to the CRP. Pairings containing one or more of those features are granted a bonus in order to promote their presence in the solutions. The solution method for the CPP is adapted to the CPPCF. We modify the dominance rules of the labeling algorithm used to solve the subproblems, based on the values of new state resources. The proposed method is tested on seven monthly instances. We show that using the CPPCF allows for a significantly higher number of awarded preferences in the CRP. The third subject of this thesis deals with language constraints — constraints on the language qualifications of the crew operating some legs. Satisfying these constraints is essential for airlines, which would otherwise have to pay high penalties, or even cancel some legs. Current methods are inadequate to deal with problems containing a large number of language constraints and few crew members with language qualifications. This is because the CPP does not account for language constraints, resulting in a spreading of the legs with language constraints among many pairings. We study this problem in the context of cabin crew scheduling. We formulate a CPP variant, called CPP with language constraints (CPPLC), which favors the grouping of legs with similar language constraints within the same pairing. The main challenge in solving the CPPLC is the combinatorial explosion in the number of subproblems. We put forward a subproblem selection strategy in which only a fraction of these subproblems are solved at each column generation iteration. We show that taking into account the language constraints in the CPP allows for a significant reduction of the number of language constraint violations in the CRP solutions. Although this study was conducted only for language constraints, the proposed method can be applied to many types of qualification constraints for cabin crews as well as pilots and copilots.