Air France - KLM en route pour l'IA (2) : un algorithme prescriptif pour aider l'activité Cargo

De l’IA dans le « Tétris du Cargo »

Sur leurs vols passagers, les compagnies aériennes ont la capacité de transporter du cargo lorsqu'il reste de la place en soute (ce qui est presque toujours le cas). Problème : la capacité disponible est connue au dernier moment, environ 90 minutes avant l'embarquement.

« Cette capacité dépend du nombre de passagers et de la quantité de bagages qu'ils apportent avec eux », explique, Waïl Benfatma. « Or les analystes cargo acceptent des demandes deux semaines avant le vol ». Pour corser le casse-tête, des évènements imprévus (retards, annulations, grèves, etc.) ajoutent une dose supplémentaire d'aléatoire aux allocations.

Le problème à résoudre : déterminer une cargaison complexe et mouvante de fret en une heure trente

Il arrive donc régulièrement que le jour du départ, Air France-KLM ait plus d'expéditions que de place dans ses avions.

« C'est même assez fréquent. Nous pourrions réviser nos prévisions de remplissage à la baisse - et donc de ventes cargo - mais l’expérience montre que cela ne règle pas toujours le problème ».

Pour le fret en réserve qui reste sur la terre ferme, se pose alors une deuxième question : comment le réallouer rapidement sur d’autres vols pour assurer toutes les expéditions en temps et en heure ? « C'est un peu comme jouer au Tetris », plaisante Waïl Benfatma. Mais aux niveaux les plus durs.

Aujourd’hui, ces réallocations sont faites par des analystes qui prennent en compte de nombreux critères : disponibilité, priorité, incompatibilité de produits, etc. Une tâche très chronophage.

L'idée est alors venue à l'équipe du Program Manager d'appliquer des algorithmes « au jeu de Tetris ». Une assistance de ce type ferait gagner du temps à l’analyste, lui fournirait un plan de remplissage quasi instantané, et lui permettrait de se focaliser sur des tâches à plus forte valeur ajoutée (comme de décider d’accepter telle ou telle nouvelle expédition de marchandise pour augmenter le chiffre d'affaire de l'activité).

Apprentissage par renforcement et simulations

Au départ, le principe choisi par Waïl Benfatma est de s'appuyer sur les données passées pour tenter de déterminer un algorithme d'optimisation. Mais très vite, le responsable se rend compte qu'il s'agit d'une impasse.

« Quand on a regardé les données historiques, nous nous sommes rendus compte qu'il n'y avait pas de comportement ou de schéma récurrent qui expliquaient les décisions des analystes », se souvient-il.

Une première version de l'algorithme en avril, une mise en production espérée cette année

L'explication tient au fait que les analystes décident sous pression. « Un vol part dans une heure trente, ils doivent choisir dans ce laps de temps les expéditions qu’il va transporter. Du coup, ils le font comme ils peuvent. D’un analyste à l’autre, cela est fait différemment ».

Le projet se pare alors d'un nouvel objectif : unifier la procédure en la rationnalisant.

Face au constat que l'historique n'apportera rien, l’équipe bascule vers une démarche de simulations et d'apprentissage par renforcement. Le principe de base est qu'elle génère des vols fictifs et à chaque vol, elle fait prendre des décisions à l'algorithme qu'elle développe pour qu'il puisse, seul, trouver la meilleure solution à prendre à un instant donné.

Les étapes de l'apprentissage par renforcement

Dans cette démarche d'apprentissage par renforcement « l'état (NDR : l'environnement dans le schéma ci-dessus), ce sont nos vols avec les réservations. Les différentes actions sont l'ajout et le retrait du fret sur un vol. La récompense c'est est-ce que ça a été bien fait ou mal fait par rapport à la situation finale du vol et à la qualité de service demandé », explique Waïl Benfatma.

Le projet d'algorithme débute en octobre 2017. En mars 2018, la phase de simulation aboutit et l'équipe IA propose une première version opérationnelle en avril.

Google est ton ami

« C'est un temps très court, surtout sur une technologie qui est relativement nouvelle pour nous. Il nous a fallu monter en compétence sur les technologies », souligne le responsable.

D'ailleurs Air France - KLM n'a pas mené ce projet seul. Le groupe a créé un écosystème autour de l'IA qui va de la start-up aux gros vendeurs en passant par les collaborations universitaires et France IA - dont la compagnie est membre.

« Je me pose, à titre personnel, de vraies questions sur la qualité des solutions de Watson »

Google, tout particulièrement, a été d'une aide précieuse. Air France - KLM a également collaboré avec IBM Watson, mais le résultat n'enchante visiblement pas Waïl Benfatma. « Je me pose, à titre personnel, de vraies questions sur la qualité des solutions de Watson. Aujourd’hui Watson est vendu comme quelque chose qui est capable de tout faire. Je n’ai pas l’impression que ce soit le cas », lâche-t-il sur la scène du salon AI Paris.

La collaboration avec Big Blue se cantonne au final à la partie coaching interne sur l'intelligence artificielle et à l'utilisation de briques NLP (traitement automatique du langage naturel) pour les chatbots.

« Avec Google cela va plus loin. Nous avons un partenariat de co-développement. Sur cette problématique cargo, ils nous ont apporté un support technique sur les algorithmes. Nous avons aussi eu des échanges avec leurs équipes de Data Science à Zurich pour avancer dans la mise en place de notre modèle d'apprentissage par renforcement ».

Air France - KLM fait également appel, ponctuellement, à des experts extérieurs (NDR : comme les hollandais de Big Data Republic). « Et nous avons des partenariats avec des académies pour avancer sur des sujets de R&D pour lesquels, concrètement, le groupe ne va pas investir en propre beaucoup d’argent mais où nous voulons collaborer avec des partenariats (NDR: avec l’Ecole des Ponts, Telecom Paris, et l'Université de technologie de Delft) sur des sujets comme les algorithmes pour la maintenance prédictive ».

Résultats modestes, en apparence

L'apprentissage par renforcement nécessite un certain nombre d'itérations. L'expérience de l'équipe de Waïl Benfatma a montré qu'il fallait entre 1,5 million et deux millions d'itérations pour commencer à avoir un modèle qu'il qualifie de « correct », c'est à dire « qui se rapproche de ce que l'analyste fait » - c'est à dire un résultat où les expéditions sont prises par ordre de priorité et casées dès qu'il y a une disponibilité et modélisée par un algorithme glouton (ligne noire sur le graphique ci-après).

4 millions d’itérations pour un gain de 0,5% « très important dans un contexte industriel »

Lorsque il passe à 3 ou 4 millions d’itérations, Waïl Benfatma constate que l'algorithme gagne en qualité.

« En revanche, même en multipliant les itérations, il est impossible d’atteindre la qualité absolue. On ne peut déterminer le remplissage optimal qu'a posteriori, en regardant deux ou trois semaines après ce qu'il aurait été possible de faire ».

De son propre aveu, le responsable du projet constate que les résultats de l'algorithme (en rouge et en vert sur le graphique) ne sont pas spectaculaires. Pas à première vue en tout cas. « Nous sommes tout de même capable d'atteindre des gains de 0,5 %. Dans un contexte industriel, avec des milliers de vols et des millions d’expéditions tous les ans, cela représente un gain très important ».

Performance de l'algorithme dans l'allocation du fret comparée à une méthode basique d'analyste représentée par un algorithme glouton

Mise en production cette année

Il ne s'en satisfait pas pour autant. Aujourd'hui, l'équipe travaille sur le paramétrage de l'algorithme pour améliorer encore les résultats. Cet été, elle lance un premier pilote pour tester la solution sur des jeux réels (ceux de la production).

L'implémentation finale, et la mise en production, devraient intervenir dans les 6 mois (« on veut mettre la pression pour y arriver »).

Le deuxième défi qu'il faudra relever concerne une plateforme interne qui gère le booking Cargo, baptisée AFLS, lancée il y a deux ans et demi avec Accenture.

« C’est une plateforme d’inventaire et de gestion des vols. Nous utilisons les données d'AFLS pour alimenter nos algorithmes d’IA. Mais toute la difficulté, une fois que notre algorithme sera capable de proposer une solution, ce sera de les réinjecter dans ce système ».