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.