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.