Problème d'affectation des types d'avion aux vols : optimisation robuste et intégration de la demande des passagers

Le problème d'affectation des types d'avion aux vols (fleet assignment problem, FAP) consiste à déterminer le type d'avion à utiliser pour chaque segment de vol d'un horaire donné de façon à maximiser les profits anticipés, c'est-à-dire les revenus estimés moins les coûts. Les frais d'exploitation dépendent de l'affectation des types d'avion et se calculent relativement bien, tandis que les revenus varient selon la demande des passagers et sont sensiblement plus difficiles à estimer. La plupart des modèles dans la littérature utilisent une estimation par segment de vol, ce qui néglige l'interdépendance des revenus entre les vols ainsi que le débordement et la récupération des passagers. Des modèles de flot de passagers (passenger flow models, PFMs) ont été développés pour améliorer la fonction objectif du FAP, mais ils ont tous divers défauts. La majorité implique un contrôle total de la compagnie aérienne sur ses passagers, sinon ils nécessitent des temps de calcul beaucoup plus importants. De plus, la demande des passagers est sujette à des variations d'une semaine à l'autre au courant d'une saison et d'une journée à l'autre dans une même semaine, ce qui rend sous-optimale toute solution au FAP qui serait répétée période après période sans changement. Cette thèse cherche à accroître la prise en compte de la demande des passagers dans le FAP afin d'améliorer la qualité et la robustesse de la solution. Le premier volet propose un algorithme faisant appel à un modèle de flot de passagers durant la résolution du FAP afin d'améliorer l'estimation des revenus. Dumas (2008) introduit dans sa thèse un modèle de flot de passagers réaliste qui utilise la solution du FAP pour déterminer la répartition des passagers sur les segments de vol et ainsi fournir une meilleure estimation des revenus. Il développe une méthode de résolution itérative qui alterne entre le FAP et le PFM en utilisant cette nouvelle estimation pour mettre à jour les revenus dans la fonction objectif du FAP. Cette méthode donne de meilleurs résultats que la résolution d'un modèle standard, au prix de multiplier les temps de calcul par un facteur de 10 ou plus. L'algorithme que nous proposons utilise le PFM pour réévaluer périodiquement les revenus des segments de vol durant la résolution du FAP par un algorithme heuristique d'énumération implicite. Cette méthode permet d'accélérer les temps de calcul par un facteur de 2 à 3 tout en préservant la qualité de la solution. Le deuxième volet de ce travail de recherche consiste à intégrer la variabilité de la demande dans la modélisation et la résolution du FAP. Lorsque la journée des opérations approche et que la demande se précise, les compagnies aériennes tentent de faire des changements d'affectation pour rentabiliser au maximum leur flotte. Puisque l'affectation initiale n'a pas été faite en tenant compte de ces échanges futurs, il y a généralement peu d'opportunités de réaffectation. Pour remédier à ce problème, nous développons différents modèles d'affectation des types d'avion aux vols avec réaffectation et scénarios de demande. Ces modèles diffèrent selon la complexité du problème de départ et des hypothèses établies. Ils permettent de planifier des opportunités d'échanges de types d'avion en fonction de plusieurs scénarios représentant la variation de la demande au cours d'une saison. Nous développons deux méthodes de résolution que nous testons sur une des variantes du problème. La première méthode utilise la décomposition de Benders pour tenter d'accélérer la résolution, les sous-problèmes étant définis pour les scénarios de demande. Les résultats ne sont pas aussi bons qu'espérés; la convergence de l'algorithme est assez lente et des erreurs numériques se glissent en cours de résolution lorsque les coupes d'optimalité, qui ont des coefficients beaucoup plus élevés que ceux de la matrice de contraintes, sont ajoutées au problème maître. Nous proposons quelques réflexions pour remédier à ces problèmes. La deuxième méthode est une approche directe par CPLEX. Plusieurs expérimentations sont faites sur des instances de tailles diverses avec différents ensembles de scénarios. Les résultats obtenus montrent que l'utilisation de multiples scénarios de demande permet d'améliorer la qualité de la solution de 1 à 3 % comparée au FAP standard et jusqu'à doubler le nombre de réaffectations de types d'avion effectuées en moyenne par rapport à l'utilisation d'un seul scénario représentant la demande moyenne par itinéraire.

Abstract

The fleet assignment problem (FAP) consists of determining the aircraft type to use on each flight leg of a given schedule in order to maximize the expected profits, which are the expected revenues minus the costs. The operating costs depend on the aircraft type assignment and can be computed relatively easily, while revenues vary with passenger demand and are significantly harder to estimate. Most models in the literature use an estimation per flight leg, that neglects the interdependency of revenues between flights as well as the spill and recapture of passengers. Passenger flow models (PFMs) have been developed to improve the FAP objective function, but they all have various flaws. The majority of them implies total control by the airline company over its passengers, otherwise they require much larger computational times. Furthermore, passenger demand is subject to variations from one week to the other during a season and from day to day in the same week, making sub-optimal any solution to the FAP that would be repeated period after period without change. This thesis seeks to augment the consideration of passenger demand in the FAP in order to improve the quality and robustness of the solution. The first part proposes an algorithm that calls a PFM while solving the FAP to improve the estimated revenues. Dumas (2008) introduced in his thesis a realistic passenger flow model that uses the FAP solution to determine the distribution of passengers on flight legs and thus provides a better estimate of revenues. He developed an iterative solution method that alternates between the FAP and the PFM using this new estimate to update revenues in the FAP objective function. This method gives better results than the usual approach on the standard FAP model, at the cost of increasing computational times by a factor 10 or more. Our proposed algorithm uses the PFM to reevaluate periodically the flight leg revenues while solving the FAP within a heuristic branch-and-bound algorithm. This method speeds up computational times by a factor of 2 to 3 while preserving solution quality. The second part of this research consists of integrating the demand variability in the modeling and solution process of the FAP. When the operation day is approaching and demand becomes more accurate, airlines try to make fleet assignment changes to maximize their fleet utilization. Since the initial fleet assignment was not made taking into account these future exchanges, there is generally few reassignment opportunities. To address this problem, we develop different fleet assignment models with reassignment and demand scenarios. These models differ depending on the initial problem complexity and the assumptions made. They allow to plan aircraft type exchange opportunities based on several scenarios representing demand variation during a season. We develop two solution methods that we test on one of the problem variants. The first method uses Benders decomposition to try to accelerate the solution process, sub-problems being defined for the demand scenarios. The results are not as good as hoped for; the convergence of the algorithm is quite slow and numerical errors are introduced during the solution process when optimality cuts, which have much higher coefficients than those of the constraint matrix, are added to the master problem. We offer some thoughts to remedy to these problems. The second method is a direct approach using CPLEX. Several tests are done using instances of various sizes with different sets of scenarios. The results show that using multiple scenarios improves solution quality by 1 to 3% relative to the standard FAP and up to double the number of aircraft type reassignments done on average compared to using a single scenario representing the average demand per itinerary.