Air FranceOptimisation de l’affectation des vols aux avions

La problématique : l’affectation des vols auxavions
Fondée en 1933, Air France est la première compagnie aériennefrançaise et, avec KLM, elle est l’un des plus grands transporteursaériens au monde, en chiffre d’affaires et nombre de passagers
transportés. Intégré au service Informatique, le service Recherche
Opérationnelle d’Air France optimise le fonctionnement de l’ensemble des activités de la compagnie en produisant des données
décisionnelles.
Aﬁn de déterminer les horaires les plus efﬁcaces pour l’ensemble dela flotte et ainsi réduire les coûts de carburant et d’exploitation tout
en atténuant la propagation des retards, le service Recherche
Opérationnelle s’est tourné vers l’optimisation mathématique. Cette
solution a permis de résoudre la problématique d’affectation desvols aux avions grâce à la modélisation de l’ensemble du processus
de planiﬁcation des appareils, depuis l’affectation de flotte jusqu’aujour des opérations.
.

Avec ce nouvel outil d’aide à la décision optimisé par lesolveur Gurobi, nous estimons réduire les coûts decarburant d’environ 1%, ce qui représente de grosvolumes pour l’ensemble de laflotte. Nous espérons égalementréduire les coûts engendrés parla propagation des retards ainsi
que les coûts d’exploitation. Le
recours à l’optimisation
mathématique pour résoudre la
problématique de l’affectation
des vols aux avions permet deréaliser des économies annuelles considérables.
Solène Richard, Data Science and Operational Research
Team Leader, Air France KLM
Outre les contraintes strictement liées à l’exploitation, la manière
dont la séquence de vols est programmée a un impact direct surles différents éléments suivants :■ Utilisation de la flotte - Nombre d’heures de vol d’unaéronef dans l’horizon de planiﬁcation, divisé par lenombre total d’heures de l’horizon de planiﬁcation.

■ Respect des horaires - Si un avion donné doit effectuer deuxvols très rapprochés l’un de l’autre, le risque de propagationd’un éventuel retard du premier vol est plus élevé.

■ Consommation de carburant - Certaines destinationsOptimisation de l’affectation des vols aux avions
Cette optimisation consiste à affecter des vols aux avions tout en
tenant compte des contraintes d’exploitation. Un planning est ainsiétabli pour chaque appareil, qui se voit attribuer une séquence de volsprécise.

Contraintes
Des contraintes d’exploitation peuvent survenir lors de la planiﬁcation,
notamment :■ Une limitation du nombre d’heures de vol autorisées avant laprochaine opération de maintenance programmée.

■ L’impossibilité d’affecter certains vols à un avion donné. Par

exemple, seul un type d’avion particulier peut rallier Papeete,
sur l’île de Tahiti, qui se trouve au milieu de l’océan Paciﬁque
et impose que l’avion soit autorisé à voler sur de longues
distances, hors de portée des aéroports de secours (ETOPS).

supposent une plus grande consommation de carburant en
raison de la chaleur ou de la pollution. En outre, tous lesaéronefs n’ont pas la même consommation de carburant.
Celle-ci dépend en effet de l’âge ou de la date de la dernière
visite de maintenance de l’avion ; par conséquent,l’affectation d’un vol a un impact direct sur la consommation.

■ Coûts d’exploitation - Si deux vols sont programmés pour lemême avion avec un temps de transit prolongé, l’appareil
devra probablement être remorqué pour libérer une place destationnement, ce qui mobilise des ressources pour leremorquage et augmente donc les coûts.

■ Affectations préférentielles - Dans la mesure du possible, il
est préférable d’affecter des vols spéciﬁques à un aéronef
donné pour des raisons commerciales, en fonction de sonéquipement propre.

Par conséquent, il est nécessaire de réaliser des arbitrages entre lesdifférents critères et l’impact éventuel pour déterminer les horaires
les plus efﬁcaces pour l’ensemble de la flotte. L’optimisation del’affectation des vols aux avions représente ainsi un problème deprogrammation en nombres entiers mixte (MIP) multicritères.

Pour en savoir plus, consultez Gurobi.com ou contactez-nous à l’adresse info@gurobi.com ou par téléphone au +1 713-871-9341.

1

Air France
Optimisation de l’affectation des vols aux avions

La solution : Modélisation multicritères etoptimisation mathématique
Pour commencer, l’équipe Recherche Opérationnelle a dû modéliser trois critères. Pour ce faire, elle s’est appuyée sur l’expertisemétier et l’analyse statistique du passé. L’équipe a créé desmodèles statistiques pour estimer la consommation de carburantde chaque appareil, sur la base de ce qui a déjà été observé par lepassé et en tenant compte du calendrier de maintenance dechaque avion (réparation, amélioration des performances despièces, etc.). En ce qui concerne le retard, elle a estimé un coûtreprésentatif d’une propagation du retard potentielle selon letemps de transit.
Les horaires étant ré-établis chaque jour en fonction des perturbations de la veille, l’outil se devait d’être réactif. En raison de lacomplexité et de l’aspect répétitif des décisions, l’optimisationétait donc tout indiquée pour résoudre le problème ; en effet, bienque le pourcentage de gains attendus soit inﬁme il s’applique àdes volumes conséquents.
Le problème peut être facilement résolu pour la flotte long-courrier
dont les vols durent de six à douze heures. La modélisation
multicritères et les arbitrages entre les différents aspects pourobtenir une solution optimale non biaisée représentent quant à eux
la partie la plus complexe du problème.
La difﬁculté a donc été d’adapter le modèle à la flotte moyen-courrier,avec des vols d’une durée de trois à six heures. Le nombre depossibilités étant bien plus élevé que pour la flotte long-courrier, lacomplexité du problème s’en trouve accrue. En effet, des vols plus
courts signiﬁent plus de vols à programmer. Il convient doncd’adapter les techniques standard pour trouver une solution optimale
au problème, ou s’en rapprocher le plus possible à tout le moins.
L’équipe Recherche Opérationnelle d’Air France a réussi à créer unmodèle efﬁcace et a tiré parti des excellentes performances dusolveur de programmation mathématique Gurobi, pour trouver unesolution optimale ou quasi optimale au problème de planiﬁcation
des avions moyen-courrier dans un délai raisonnable.

Figure 1 : Outil d’aide à la décision - Chaque ligne représente un
appareil et chaque rectangle représente un vol ou une activité demaintenance. Nous pouvons constater que certains vols nepeuvent être affectés qu’à certains appareils. Par exemple, les volsen jaune ne peuvent être affectés qu’aux appareils en jaune.

À propos de l’équipe Recherche Opérationnelled’Air France
Intégrée au service Informatique d’Air France, l’équipe Recherche
Opérationnelle a pour mission d’optimiser le fonctionnement del’ensemble des activités de la compagnie en produisant des données
décisionnelles. Elle contribue ainsi à la stratégie de la compagnie en
améliorant ses performances commerciales et opérationnelles.
L’équipe Recherche Opérationnelle d’Air France est l’une des plus
importantes en France et dans le secteur du transport aérien. Les
employés sont à la fois consultants, innovateurs et développeurs. Ils
travaillent sur divers domaines de la compagnie, allant de lamaintenance à la relation client en passant par le personnelnavigant.

Outil d’aide à la décision
L’équipe Recherche opérationnelle a créé un outil d’aide à ladécision, optimisé par le solveur Gurobi, pour recommander une
solution que les utilisateurs internes peuvent exploiter aﬁn derépondre à leurs besoins spéciﬁques. L’outil apporte unesolution optimale en tenant compte des contraintes et descritères donnés, mais l’utilisateur a toujours la possibilitéd’adapter la solution selon sa propre expérience. Ainsi, l’équipeRecherche Opérationnelle est en mesure d’informer l’utilisateurdes conséquences engendrées par ses décisions, en mettant enévidence la contrainte qui pourrait être violée ou l’impact sur lesdifférents coûtsPour en savoir plus, consultez Gurobi.com ou contactez-nous à l’adresse info@gurobi.com ou par téléphone au +1 713-871-9341.

2