Points Clés
- Avec pour mission "Make eating well effortless, every day, for everyone", l’une des principales priorités chez Uber Eats est de garantir un service fiable afin de satisfaire et fidéliser ses clients. Ainsi il est important que les livreurs arrivent dans les restaurants au moment où la nourriture est prête, en cela, la prédiction de temps joue un rôle déterminant tout au long du cycle de vie de la commande.
- Le système de répartition d’Uber Eats a été lancé avec un algorithme de correspondance « gourmand », et en utilisant un algorithme « global », alimenté par des prévisions de temps, celui-ci a pu devenir beaucoup plus efficace.
- La plateforme de machine learning d’Uber Michelangelo, a énormément aidé à simplifier l’ensemble du processus permettant aux scientifiques et ingénieurs de données de résoudre les problèmes liés au machine learning.
- Notre plus grand défi quant au manque de donnée provenant du terrain, dans le modèle O2O, a été relevé en déduisant des données étiquetées ("label data") depuis un travail d’ingénierie des fonctionnalités et en tirant parti de la boucle de rétroaction pour le ré-entraînement du modèle.
- Le modèle de prévision du temps de livraison est conçu pour être suffisamment flexible pour gérer divers scénarios.
Uber Eats est l’un des services de livraison de nourriture à la croissance la plus rapide depuis son lancement initial à Toronto en décembre 2015. Actuellement, il est disponible dans plus de 600 villes à travers le monde, servant plus de 222 000 restaurants partenaires et a atteint 8 milliards de réservations brutes en 2018.
La capacité de prévoir avec précision les délais de livraison est primordiale pour la satisfaction et la fidélité des clients. De plus, les prévisions de temps sont importantes du côté de l’offre, car nous calculons le temps nécessaire à chaque expédition d’un coursier. Je vais tenter d’expliquer comment Uber Eats a mis à profit le machine learning pour relever ces défis.
Le machine learning chez Uber Eats
Ayant pour mission de faire à manger facilement, chaque jour, pour tout le monde ("Make eating well effortless, every day, for everyone" l’une de nos priorités est d’assurer un service fiable. Tout d'abord, nous devons définir les bonnes attentes en fournissant des estimations précises des délais de livraison afin d'éviter les frustrations en cas de retard. Ensuite, nous devons calculer le moment idéal pour envoyer nos coursiers récupérer la nourriture. Idéalement, ils devraient arriver au restaurant au moment où la nourriture est prête. Une arrivée prématurée fera perdre du temps au livreur, en revanche, une arrivée tardive entraînera un refroidissement des aliments. Par conséquent, la prédiction de temps joue un rôle déterminant tout au long du cycle de vie de la commande, comme l’illustrent les images ci-dessous.
Prédictions de temps à travers le cycle de vie d’une commande
Il n'y a pas aucun autre moyen d'assurer un tel niveau de précision sans utiliser les technologies du machine learning. Toutefois, des défis se posent. Par rapport à d'autres problèmes liés au machine learning, notre plus grand défi est le manque d’information collecté sur le terrain ("ground truth data"), ce qui est assez courant dans un modèle online-to-offline (O2O). Cependant, c’est le composant le plus important du machine learning, comme nous le savons tous : « garbage in, garbage out » (Si des données erronées sont introduites dans un système afin d’être traitées, les résultats de l’analyse seront eux aussi erronés). Un autre défi est le caractère unique d'Uber Eats en tant que marché à trois côtés (reliant un restaurateur, un livreur et un client de la plateforme), il est donc indispensable de tenir compte de chacun de nos partenaires lors de nos prises de décision.
Heureusement, la plateforme de machine learning d’Uber - Michelangelo a fourni une aide considérable pour simplifier l’ensemble du processus, permettant aux data scientists et data enginners de résoudre les problèmes liés au machine learning. Il fournit des solutions génériques pour la collecte de données, la conception des fonctionnalités ("feature engineering"), la modélisation, la diffusion de prédictions hors ligne et en ligne, etc., ce qui permet de gagner beaucoup de temps, plutôt que de réinventer la roue à chaque fois !
Michelangelo – Prédictions en ligne et hors-ligne
La figure ci-dessus donne un aperçu des pipelines de prédiction en ligne et hors-ligne. La partie en ligne est principalement destinée à faire des prédictions avec des données en temps réel et en temps quasi réel. Les données sont collectées via Kafka et pré-traitées par des frameworks de traitement de flux ("stream processing") tels que Samza, Flink, etc. Finalement la persistance se fait dans les magasins de fonctionnalité ("feature stores") de Cassandra. Pour la partie hors-ligne, les données collectées à partir de différentes sources sont pré-traitées par SparkSQL et persistent dans l’entrepôt de données HIVE. Ensuite, nous entraînons des modèles basés sur les algorithmes fournis par la plateforme, laquelle supporte la bibliothèque Spark MLlib, et d’autres modèles basés sur le deep learning, etc.
Rapport sur les fonctionnalités - distribution de chaque fonctionnalité et importance pour le modèle
Voici l’exemple d’un rapport de fonctionnalités pour un modèle entraîné. Il fournit de nombreuses informations détaillées telles que la distribution des données et l'importance des fonctionnalités. Ce sont des données très importantes pour le travail d'ingénierie des fonctionnalités.
Comment les prévisions de temps alimentent-t-elles le système de répartition ?
Voyons maintenant comment notre système de répartition fonctionne et a évolué grâce aux prévisions de temps. Au plus haut niveau, le système de répartition, c’est le cerveau de l'activité d’Uber Eats. Son objectif est de prendre les décisions les plus optimales d'appariement entre l'offre et la demande. Dans notre contexte, la demande est la commande du client et l’offre, le coursier. Comme nous l'avons mentionné précédemment, le timing est essentiel car nous devons nous assurer que ce dernier arrive au restaurant au moment exact où la nourriture est prête.
Nous avons eu besoin de plusieurs itérations avant d'atteindre le stade actuel. Voyons une comparaison entre avant et après l'introduction des prévisions de temps.
Nous avons commencé par estimer certaines valeurs fixes afin de décider le moment où envoyer les livreurs récupérer la nourriture. Par exemple, si un client passe une commande à 17h30, nous supposions que la nourriture devait prendre 25 minutes pour être préparée et que le livreur avait besoin de 5 minutes pour se rendre au restaurant, nous commencions donc à expédier la commande à 17h50. Mais en réalité, ce n’était pas très précis d'utiliser 25 minutes pour toutes les commandes d’un restaurant, que les clients commandent 1 ou 10 plats - il en va de même quant à l’estimation des 5 minutes de trajet vers le restaurant. En conséquence, cela a causé beaucoup de confusion parmi tous les partenaires, entraînant des problèmes tels que l'incapacité des clients à suivre leur commande avec précision, les coursiers pouvaient attendre trop longtemps dans les restaurants ou parfois la commande refroidissait car les restaurateurs ne trouvaient pas le livreur.
Une fois que nous avons introduit les prédictions de temps, nous avons remplacé les deux principaux facteurs ; des hypothèses nous sommes passés aux prédictions basées sur le machine learning. Le premier facteur était la prédiction du temps de préparation des aliments. Au lieu d'utiliser 25 minutes pour toutes les commandes du même restaurant, nous avons entraîné un modèle de machine learning pour faire une prédiction pour chaque commande, le résultat était de 30 minutes en moyenne dans l'exemple suivant.
Système d'expédition – planification des expéditions
Il en va de même pour le déplacement du livreur. Désormais nous commençons à les expédier 10 minutes en avance. La satisfaction de tous les partenaires s'est considérablement améliorée. Les clients ont pu obtenir des livraisons plus rapides et des prédictions claires. Les restaurants et les partenaires de livraison sont devenus plus efficaces afin de pouvoir traiter plus de commandes dans un même laps de temps.
En plus de cela, notre plateforme de répartition est également passée d'un algorithme de correspondance gourmand ("greedy matching algorithm") à un algorithme de correspondance global ("global matching algorithm").
L'algorithme de correspondance gourmand ne commence à rechercher un livreur que lorsqu'une commande arrive. Le résultat est optimal pour une seule commande mais pas pour toutes les commandes de notre système dans son ensemble. Par conséquent, nous sommes passés à l'algorithme de correspondance dit global afin de pouvoir résoudre l'ensemble des commandes et des livreurs en un seul problème d'optimisation globale. Qu'est-ce que ça veut dire ? Faisons une comparaison rapide grâce à l’illustration ci-dessous. La figure de gauche montre l'algorithme gourmand. Lorsque la première commande arrive, notre système d'expédition la fait correspondre avec le livreur le plus éligible, celui-ci mettra 1 minute pour arriver au restaurant. Ensuite, la deuxième commande arrive, le système la fait correspondre avec un autre livreur qui mettra 5 minutes pour arriver au restaurant. Le temps de trajet total est donc de 6 minutes.
L’image de droite montre l'algorithme de correspondance global dans lequel le nouveau système d'expédition considère à la fois les commandes et les livreurs pour les faire se correspondre de manière optimale au niveau mondial. En conséquence, les deux partenaires de livraison auront besoin de 2 minutes chacun, soit un temps de voyage total de 4 minutes !
Système de répartition - comparaison entre l’algorithme gourmand et global
Il est évident que l'algorithme de correspondance global est beaucoup plus efficace, cependant, pour exister, il a besoin de prévisions de temps précises, eu égard de l’importance de celui-ci dans le processus de décision. Examinons maintenant ce qu’elles sont.
Plongée dans les prévisions de temps
Examinons maintenant les détails des prévisions de temps. Comme nous l'avons déjà vu dans la section précédente, la prédiction du temps de préparation des aliments est cruciale pour l'entreprise, car c'est le principal facteur déterminant pour répartir les livreurs. Aussi, l'un des plus grands défis lors de l'application du machine learning dans le modèle métier O2O est la collecte d’information provenant du terrain, la prédiction du temps de préparation des aliments est un excellent exemple. Étant donné que nous ne sommes pas physiquement dans les restaurants et que ceux-ci ne fournissent pas toujours les informations dont nous avons besoin, il est presque impossible de savoir quand la nourriture sera prête. Ce que nous pouvons faire, c'est utiliser d'autres signaux provenant des livreurs et des restaurants pour en déduire ces informations. Cependant, ils ne sont pas toujours valides en raison de circonstances imprévisibles tels que la disponibilité du stationnement, le trajet en marche à pied pour trouver l'entrée du restaurant, etc. Par conséquent, nous nous sommes concentrés sur deux domaines. L'un consiste à mieux utiliser les données disponibles provenant de l'ingénierie des fonctionnalités ("feature engineering"), et l'autre à augmenter la précision du modèle en inférant les données étiquetées ("labeled data") et en tirant parti de la boucle de rétroaction ("feedback loop") pour le ré-entraînement du modèle.
Pour le travail d'ingénierie des fonctionnalités, il est divisé en trois ensembles : les fonctionnalités historiques, comme le temps moyen de préparation des aliments pour la semaine dernière ; les caractéristiques en temps quasi réel, comme le temps moyen de préparation des aliments pour les 10 dernières minutes et les fonctionnalités en temps réel comme l'heure du jour, le jour de la semaine, la taille des commandes, etc. Les fonctionnalités en temps réel et quasi réel nous permettent d’obtenir des informations supplémentaires pour gérer certaines situations qui peuvent changer rapidement. Par exemple, la répartition entre les commandes et les livreurs peuvent être affectée par les intempéries.
Un exemple de notre travail d'ingénierie des fonctionnalités est de tirer parti de l'apprentissage de la représentation ("representation learning") pour les différents types de cuisine. Dans les fonctionnalités en temps réel, nous avons déjà pris en compte les données spécifiques aux commandes telles que le prix, le nombre d'articles, etc. Cependant, nous ne voulons pas seulement savoir combien d’articles contient la commande, mais aussi quels sont ses articles, car le temps de préparation des aliments entre les différents types de cuisine peut varier considérablement, exemple : la préparation d'un ragoût de bœuf et celle d’une salade. Afin d'améliorer la précision du modèle en tenant compte du type de cuisine, nous utilisons nos données relatives aux menus pour générer des incorporations de mots, les classer en différentes catégories et les intégrer aux fonctionnalités en temps réel.
Representation learning - intégration de menu
Pendant ce temps, nous explorons toujours plus de façons de collecter de nouveaux signaux pour améliorer la précision des données étiquetées. Le signal du capteur provenant des téléphones des livreurs en fait partie. C’est principalement pour détecter le statut du livreur dans certaines circonstances compliquées. Par exemple, si la récupération de la commande est retardée alors que le livreur est proche du restaurant, nous devons savoir si c'est la difficulté à localiser le restaurant ou l'incapacité à trouver une place de parking qui en est la cause. Ici, nous nous appuyons sur les données des capteurs pour prédire leur prochain mouvement en fonction de leurs états actuels.
Signaux des capteurs
La méthode que nous avons utilisée consiste, via la modélisation de champ aléatoire conditionnel "conditional random field" et une cible, à classer l'état d'un ensemble de séquences. En tirant parti de ce modèle de possibilité et en étiquetant les données séquentielles de certains voyages, nous sommes en mesure de prédire la prochaine activité d'un livreur, telle que le stationnement ou la récupération de la commande.
Modèle de champ aléatoire conditionnel
D'un autre côté, la boucle de rétroaction que nous avons introduite pour le ré-entraînement du modèle a considérablement amélioré nos données étiquetées. Avant d’approfondir le sujet, je voudrais d'abord parler du modèle de prédiction du temps de préparation des aliments.
Nous utilisons des arbres de décision pour améliorer le gradient (l’inclinaison d’une fonction à plusieurs variables) formé avec XGBoost et exploitons le réglage de l’hyper-paramètre fourni par la plate-forme Michelangelo pour améliorer la précision du modèle et les performances d’entraînement. L'approche du réglage hyper-paramétrique dans notre modèle de temps de préparation des aliments est l'optimisation Bayésienne. Fondamentalement, l'idée est de nous permettre de faire des choix intelligents parmi toutes les combinaisons possibles de paramètres nécessaires à XGBoost.
Réglage des hyper-paramètres
Alors, comment ça marche ? En regardant le graphique à gauche, la courbe « posterior » montre les 3 combinaisons de paramètres que nous avons essayé jusqu'à présent. La plus large zone bleue, au milieu, montre la partie en laquelle nous avons une faible confiance car nous n'avons encore essayé aucune combinaison. Afin de déterminer la prochaine combinaison à essayer, nous avons créé la fonction d'acquisition, qui nous indique ce que nous devrions essayer pour produire de meilleurs résultats. Le graphique de droite montre les résultats après avoir expérimenté avec la combinaison recommandée de fonctions d'acquisition.
Revenons maintenant à la boucle de rétroaction que nous avons mentionnée plusieurs fois. C'est un autre élément clé en termes d'amélioration de la précision des prédictions pour combler le manque d’information. Il nous fallait déduire exactement le temps de préparation des aliments, une erreur d'approximation existe toujours entre les données présumées et réelles. Réduire ces erreurs était notre priorité absolue. Nous avons donc introduit une boucle de rétroaction dans notre modèle pour ajuster cette erreur d'approximation, cela a aidé à corriger le temps de préparation présumé, en particulier lorsque de nouvelles informations étaient disponibles. Par exemple, nous vérifions chaque commande terminée pour voir si nous avons collecté suffisamment d’informations pour permettre de calculer le temps réel de préparation des aliments. Si c’est le cas, nous utilisons ces données pour mettre à jour la valeur estimée et les utiliser pour de futurs entraînements du modèle.
Boucle de rétroaction
Une autre caractéristique importante des prévisions de temps est le délai de livraison estimé (Estimated Time-of-Delivery), qui affecte constamment l'expérience des consommateurs pendant tout le cycle de vie de la commande. Ainsi, chaque fois que les clients se demandent combien de temps ils doivent attendre avant de pourvoir récupérer leur nourriture, ils peuvent d'abord vérifier nos prévisions ETD. Bien que les prévisions de temps ETD et de préparation des aliments partagent de nombreuses techniques similaires en termes de traitement des données, d'ingénierie des fonctionnalités, etc., il existe également de nombreuses différences entre les deux.
Le caractère unique de la prédiction ETD est son évolution entre les différentes étapes de la livraison du fait de l’enrichissement des informations en cours de route. Par exemple, lorsqu'un client parcourt les différents restaurants avant de passer sa commande, nous n'avons que des informations telles que l'emplacement du restaurant, le type de cuisine, etc. pour faire des prédictions. Lorsqu'un client passe la commande, nous aurons alors des informations plus détaillées de la commande elle-même, telles que le nombre d'articles, les prix, l’heure etc. Lorsque nous aurons trouvé un livreur, nous aurons encore plus d'informations, telles que le temps de trajet estimé. Par conséquent, notre modèle de prédiction ETD doit être suffisamment flexible pour gérer toutes les variations.
ETD face aux clients
La dernière caractéristique des prévisions de temps qui mérite d'être mentionnée est l'estimation du temps de trajet. Uber Eats ne pourrait pas croître de façon exponentielle en si peu de temps sans tout le soutien du secteur du transport. Avec Uber nous partageons les conducteurs, et nous construisons également une pile technologique sur une plate-forme partagée. L'estimation du temps de trajet en fait partie. C'est difficile pour les transporteurs car chaque seconde compte à chaque voyage. Les clients qui voyagent avec Uber sont en mesure de suivre leurs déplacements, du moment où ils demandent un voyage, jusqu'à leur arrivée à destination. Pour Uber Eats, la plus grande différence est que nous avons aussi des livreurs non véhiculés, comme les cyclistes ou des livreurs à pieds. Dans les grandes villes comme New York et San Francisco, ils sont beaucoup plus efficaces pour éviter les embouteillages et les problèmes de stationnement. Faire des prévisions de temps de voyage précises pour ces types de coursiers est très important pour l'entreprise Eats. Pour cela, nous avons travaillé avec l'équipe Maps d'Uber pour collecter des données non liées à la voiture et formé un nouveau modèle. L’image suivante montre la course d’un livreur à vélo en train de récupérer de la nourriture, son temps de trajet estimé est de 11 minutes.
Estimation du temps de trajet à vélo
Conclusion
Vous comprenez maintenant le rôle essentiel que joue la prédiction du temps dans Uber Eats et comment nous avons tiré parti des technologies du machine learning pour résoudre certains des problèmes les plus difficiles du modèle métier O2O. Nous continuerons certainement d'investir dans ce domaine à l'avenir et créerons grâce au machine learning une solution de premier ordre pour servir tous les partenaires de notre marché à trois volets. Pour plus d'informations sur l'apprentissage automatique chez Uber, veuillez visiter nos blogs d'ingénierie. Si vous avez des questions plus spécifiques concernant les prévisions de temps, n'hésitez pas à me contacter sur LinkedIn.
A propos de l'auteur
Zi Wang est Engineering Manager chez Uber, il dirige les travaux d'ingénieries en machine learning sur les prévisions de temps, y compris le temps estimé de livraison, le temps de préparation des aliments et l'estimation du temps de voyage dans Uber Eats. En outre, il a travaillé sur le système de répartition Uber Eats, Uber Rush, et un système de paiement interne. Avant Uber, Zi travaillait chez Microsoft et développait la fonction d'édition collaborative en temps réel pour les principales applications Office. Il est passionné par la création de services backend scalable et performants et par l'exploitation du Big Data et du machine learning pour résoudre les problèmes du monde réel afin d'assurer l'efficacité du système et l'expérience utilisateur.