Optimisation dynamique de la sélection de vols partagés d'un transporteur aérien

Codesharing is now a widespread practice that allows an airline to put one of its flight numbers on a flight operated by a partner airline and consider it in its own network. Even though it has been repeatedly demonstrated that this type of partnership can generate important additional revenues, it is very complex for an airline to choose which flights to share with which partners. The objective of this project is to provide a decision support tool that maximizes the revenues of an airline considering two aspects that were not explicitly considered in the literature: the impact of adding a shared flight in the network and the interactions that exist between flights that are chosen to become codeshared. Therefore, a heuristic is developed. At each iteration, the demand is distributed on the network considering the codeshare flight selection and this selection is modified in order to increase the profitability of the carrier. To speed up the resolution, the demand is distributed on reduced graphs instead of the full network. A mathematical model of demand distribution is built and validated using existing software before being used in the heuristic. In addition, a blocking flow method is used to ensure greater realism. Two algorithms based on the developed heuristic are used to optimize the codeshare flight selection of Air Canada with one partner and with two partners. In comparison with two methods currently used, these algorithms propose codeshare flight selections that generate much greater revenues. The results also show that there is a clear interaction between selected flights and that it is important to consider this effect when optimizing the selection of codeshared flights. However, the proposed algorithms require very long resolution times and their convergence is not guaranteed. Further research should be conducted to acccelerate the resolution of the proposed heuristic, to improve the accuracy of the demand distribution model used and to investigate different factors related to codeshare management that were not considered in this project.

Résumé

Le partage de vols est une pratique désormais très répandue qui permet à un transporteur aérien d'apposer un de ses numéros de vol sur un vol exploité par une compagnie partenaire pour ainsi considérer ce dernier dans son propre réseau. Malgré qu'il ait été prouvé à maintes reprises que ce type de partenariat peut générer d'énormes revenus additionnels, il reste très complexe pour une compagnie aérienne de choisir quels vols partager avec quels partenaires. L'objectif du présent projet est de proposer un outil d'aide à la décision qui optimise les revenus d'un transporteur aérien en considérant deux aspects qui n'étaient pas expressément considérés dans la littérature : l'impact de rendre un vol partagé dans le réseau et les interactions qui existent entre les vols que l'on souhaite rendre partagés. Pour ce faire, une méthode heuristique est développée. À chaque itération, la demande est répartie sur le réseau en fonction de la sélection de vols partagés et cette sélection est modifiée dans le but d'augmenter la profitabilité du transporteur. Pour accélérer la résolution, la demande est répartie sur des graphes réduits au lieu de considérer le réseau entier d'un transporteur. Un modèle mathématique de répartition de la demande est construit et validé à l'aide d'un logiciel existant afin d'être utilisé à l'intérieur de l'heuristique. De plus, une méthode de blocage du flot est employée pour assurer un plus grand réalisme. Deux algorithmes basés sur l'heuristique développée sont appliqués pour optimiser la sélection de vols partagés d'Air Canada avec un partenaire et, en deuxième temps, avec deux partenaires. En comparaison avec deux méthodes actuellement utilisées, ces algorithmes proposent des sélections de vol qui génèrent beaucoup plus de revenus. Les résultats obtenus démontrent également qu'il existe une interaction claire entre les vols partagés choisis et qu'il est important de considérer cet effet dans l'optimisation de la sélection de vols partagés. Toutefois, les algorithmes proposés nécessitent de très longs temps de résolution et rien n'assure leur convergence. Des recherches plus approfondies devront être menées pour accélérer la résolution de l'heuristique proposée, pour améliorer la précision du modèle de répartition de la demande utilisé et pour étudier plusieurs facteurs reliés à la gestion de vols partagés qui n'ont pas été considérés dans le présent projet.