Skip to content

Blog


Utiliser la ML et l'optimisation pour résoudre le problème d'expédition de DoorDash

17 août 2021

|

Alex Weinstein

DoorDash livre des millions de commandes chaque jour avec l'aide de DeepRed, le système au centre de notre plateforme logistique du dernier kilomètre. Mais comment DeepRed fonctionne-t-il réellement et comment l'utilisons-nous pour assurer le bon fonctionnement de la place de marché ? Pour alimenter notre plateforme, nous devions résoudre le "problème de l'expédition" : comment acheminer chaque commande du magasin au client, via Dashers, de la manière la plus efficace possible. Dans cet article de blog, nous discuterons des détails du problème de l'expédition, de la façon dont nous avons utilisé le ML et l'optimisation pour résoudre le problème, et de la façon dont nous améliorons continuellement notre solution avec des simulations et des expérimentations.

Comprendre le problème de la répartition

Pour mieux comprendre le problème de la répartition, nous allons examiner les objectifs que DeepRed tente d'atteindre pour chaque partie de notre marché à trois côtés, puis nous examinerons les obstacles auxquels nous sommes confrontés. 

Les objectifs du dispatching

Définissons d'abord les objectifs que nous essayons d'atteindre lorsque nous envoyons des Dashers. Nos objectifs sont doubles : 

  • Proposer des offres aux Dashers de la manière la plus efficace possible afin qu'ils puissent maximiser leurs opportunités de gains.
  • Livrer les commandes rapidement et à temps pour que les consommateurs et les commerçants soient satisfaits de leur expérience. 

Pour atteindre ces objectifs, il faut relever un certain nombre de défis. Nous abordons chaque défi à l'aide de solutions d'apprentissage automatique et d'optimisation, et nous utilisons des méthodes de simulation et d'expérimentation pour tirer parti de ces performances.  

Trouver le meilleur Dasher 

Pour trouver le meilleur Dasher pour livrer une commande, nous devons prendre en compte un certain nombre de facteurs différents. Le facteur le plus important est la situation géographique des Dashers. Nous souhaitons généralement trouver un casseur qui soit le plus proche possible du magasin afin de minimiser la durée totale du trajet. Le deuxième facteur que nous prenons en compte est de s'assurer que le Dasher arrivera au bon moment. Si nous envoyons un Dasher trop tôt, il devra attendre que la commande soit prête. Si nous l'envoyons trop tard, les aliments resteront trop longtemps sur place et risqueront de refroidir, tandis que les commerçants et les consommateurs seront mécontents que les aliments n'aient pas été livrés aussi rapidement que possible. Un autre facteur est la mise en lots, qui consiste à utiliser les Dashers aussi efficacement que possible en recherchant des opportunités où un seul Dasher peut récupérer plusieurs commandes dans le même magasin (ou dans un ensemble de magasins proches).

Figure 1 L'objectif du dispatching est de trouver le meilleur Dasher pour récupérer chaque commande une fois qu'elle est prête chez le commerçant et de la livrer au client. (Cette figure a été publiée dans un article précédent du blog).

Prise en compte des conditions du marché

Il existe d'autres conditions de marché sur lesquelles nous n'avons aucun contrôle et qui jouent un rôle dans notre décision de choisir un Dasher. La plus importante est l'équilibre entre l'offre et la demande sur un marché donné. Bien que nous essayions de faire en sorte qu'il y ait suffisamment de Dashers disponibles pour honorer les commandes, il peut arriver que nous n'ayons pas assez de Dashers pour honorer toutes les commandes. Dans ces scénarios de sous-approvisionnement, nous devons faire des compromis sur les commandes à honorer maintenant ou plus tard. Il s'agit également de situations dans lesquelles il est utile de rechercher des possibilités de regroupement, car un consommateur peut obtenir sa commande plus rapidement si un seul Dasher est en mesure de récupérer plusieurs commandes en même temps. Nous devons également tenir compte des conditions météorologiques et de circulation qui peuvent avoir un impact sur les délais de livraison ou amener les caissiers à refuser des commandes dans des proportions plus élevées que ce à quoi nous nous attendrions normalement. Par exemple, s'il pleut et que de nombreux Dashers utilisent des motos, nous pouvons nous attendre à moins de livraisons acceptées, ce qui peut entraîner des retards et nuire à notre capacité à atteindre nos objectifs. 

S'attaquer au problème de la répartition

La prise en charge d'un problème aussi complexe s'est faite en deux étapes. Tout d'abord, nous avons mis en place un service de répartition sophistiqué qui utilise un certain nombre de modèles ML et d'optimisation pour comprendre l'état du marché et faire les meilleures offres possibles aux Dashers afin de répondre aux besoins de notre marché. La deuxième étape a consisté à créer des plateformes de simulation et d'expérimentation qui nous permettraient d'améliorer continuellement notre service de répartition. Ces deux méthodes nous ont permis d'atteindre nos objectifs et de continuer à nous améliorer de 1 % chaque jour. Dans les sections suivantes, nous présenterons l'architecture de notre système de répartition et la manière dont il traite un échantillon de livraison. Nous décrirons ensuite comment nous utilisons nos plateformes de simulation et d'expérimentation pour améliorer nos décisions. 

Construire DeepRed : notre service de répartition 

À un niveau élevé, le moteur de répartition repose sur deux ensembles de modèles mathématiques. Le premier ensemble de modèles est constitué de modèles ML formés pour estimer comment une commande se déroulera si nous la proposons à un Dasher particulier. Ces modèles s'attachent à faire des prédictions sur chaque commande, chaque magasin et chaque Dasher.

Restez informé grâce aux mises à jour hebdomadaires

Abonnez-vous à notre blog d'ingénierie pour recevoir régulièrement des informations sur les projets les plus intéressants sur lesquels notre équipe travaille.

Une fois les estimations réalisées, elles sont introduites dans notre deuxième couche de modélisation, notre modèle d'optimisation à nombres entiers mélangés. Le modèle d'optimisation émet les recommandations finales concernant les commandes à proposer aux différents Dashers. Alors que les couches de modélisation sont axées sur l'établissement d'estimations individuelles pour chaque commande, la couche d'optimisation est axée sur la prise de décisions à l'échelle du système pour l'ensemble du marché.

Ensemble, les modèles ML et la couche d'optimisation distillent des millions de points de données de notre place de marché en un ensemble de décisions d'expédition qui garantissent que chaque commande est proposée au Dasher qui peut la livrer du magasin au consommateur de la manière la plus efficace possible.

Le parcours d'une commande à l'expédition

La meilleure façon de comprendre comment nous résolvons le problème de la répartition est de considérer comment une commande individuelle se fraye un chemin à travers le système complexe de DeepRed. Nous verrons comment une commande passe par les différentes couches de DeepRed, en commençant par notre générateur d'offres candidates, en passant par notre couche de ML qui estime comment ces offres pourraient fonctionner dans le monde réel, puis en passant par notre couche d'optimisation qui émet les recommandations finales.

Figure 2 Les commandes passent par les trois couches de DeepRed : la génération d'offres, la couche ML et notre modèle d'optimisation.

Construire des offres potentielles

Lorsqu'une nouvelle commande arrive sur notre moteur d'expédition, nous commençons par mettre à jour notre compréhension de l'état actuel du marché et de la manière dont cette commande interagit avec les Dashers et les autres commandes. Nous cherchons à savoir quels Dashers se trouvent à proximité et sont disponibles pour prendre la nouvelle commande. Ces Dashers peuvent être en train d'attendre leur prochaine commande, auquel cas nous pouvons leur proposer une nouvelle commande dès maintenant, ou ils peuvent être en train de terminer une autre commande, auquel cas nous pouvons prévoir de leur proposer une nouvelle commande dès qu'ils auront terminé leur livraison en cours.

À ce stade, notre attention ne se limite pas aux Dashers disponibles : nous examinons également les autres commandes qui attendent d'être enlevées. Si une autre commande est en cours de retrait dans le même magasin ou dans le même quartier que la nôtre, il peut être judicieux de proposer les deux commandes au même Dasher. Il en va de même si une autre livraison doit être déposée à proximité de l'endroit où notre commande doit être livrée.

En examinant les Dashers disponibles et les autres ordres, nous sommes en mesure de construire des offres potentielles pour notre nouvel ordre : un ensemble de Dashers à qui cet ordre pourrait être offert et éventuellement d'autres ordres qui pourraient être récupérés par le même Dasher. Ces offres potentielles sont ensuite envoyées à la couche ML où nous prédisons ce qui pourrait arriver à ces offres dans le monde réel.

Prévoir le déroulement d'une commande dans la couche ML

Avec un ensemble d'offres potentielles en main, nous sommes prêts à faire quelques estimations à l'aide de nos modèles ML, y compris, mais sans s'y limiter : les temps de préparation des commandes, les temps de déplacement et la probabilité d'acceptation de l'offre.

  1. La première question à laquelle nous voulons répondre à l'aide du ML est de savoir quand une commande sera prête à être enlevée(temps de préparation de la commande). Nous estimons les délais de préparation des commandes sur la base d'un modèle de temps de préparation. Un article précédent, intitulé Résolution des données non observées dans un modèle de régression à l'aide d'un simple ajustement des données, décrivait comment nous estimons le temps de préparation d'une commande et comment nous avons surmonté les difficultés liées à la réalisation d'une prédiction avec des données censurées.
  1. La deuxième série de questions auxquelles notre couche ML permet de répondre concerne l'estimation des temps de déplacement, c'est-à-dire le temps qu'il faudra à un Dasher pour se rendre au magasin, puis pour livrer la commande à l'endroit souhaité par le client. En plus de ces temps de trajet, il y a plusieurs aspects du voyage du Dasher que nous modélisons séparément : le temps qu'il faudra au Dasher pour trouver un parking chez le commerçant et chez le consommateur, le temps qu'il lui faudra pour gérer la logistique du retrait de la commande, et le temps qu'il lui faudra pour retourner à son véhicule. Chacune de ces étapes du parcours de livraison de la commande nécessite un modèle distinct. Certains sont basés sur des modèles arborescents construits sur notre plateforme Sibyl ML. D'autres estimations sont basées sur des modèles naïfs plus simples. Par exemple, nous pouvons estimer le temps de stationnement dans un magasin particulier en utilisant le temps moyen qu'il a fallu aux Dashers pour trouver un parking dans ce magasin au cours du mois dernier.
  1. La troisième et dernière question à laquelle notre couche ML doit répondre est la probabilité que chaque Dasher accepte la commande si nous la lui proposons. Les Dashers étant libres d'accepter ou de refuser chaque offre, nous nous efforçons d'anticiper les types d'offres les plus susceptibles d'être acceptées et de les présenter au Dasher le plus concerné. Il est important de s'assurer que chaque commande est livrée à temps même si un ou plusieurs Dashers refusent l'offre avant que nous n'en trouvions un qui l'accepte.

Une fois que notre nouvelle commande est passée par chacun des trois ensembles de modèles de notre couche ML (temps de préparation de la commande, temps de trajet et taux d'acceptation), nous comprenons beaucoup mieux ce que nous devons faire pour livrer la commande aussi efficacement que possible. C'est à notre couche d'optimisation qu'il revient de prendre la décision finale d'expédition.

Faire des offres finales dans la couche d'optimisation

La couche d'optimisation est la dernière étape du voyage de notre nouvelle commande avant qu'elle ne soit expédiée à un Dasher. Le modèle d'optimisation se charge d'évaluer et de classer les offres potentielles, de prendre des décisions concernant la mise en lot des commandes et de retarder stratégiquement les expéditions si nécessaire. 

Lorsqu'elles arrivent dans la couche d'optimisation, les offres potentielles de notre nouvelle commande sont notées et classées pour permettre au programme en nombres entiers mélangés (MIP) de prendre ses décisions, un processus que nous décrivons dans un article précédent, intitulé Next-Generation Optimization for Dasher Dispatch at DoorDash (Optimisation de nouvelle génération pour l'expédition par Dasher chez DoorDash). Notre fonction de notation est conçue pour reconnaître les compromis entre l'efficacité (utiliser le temps du Dasher aussi efficacement que possible) et la qualité (livrer les consommateurs aussi rapidement que possible), tout en essayant de tenir compte de la variance expliquée et inexpliquée dans nos estimations ML des temps de préparation des commandes, des temps de déplacement et du taux d'acceptation du Dasher. Une fois chaque offre notée, nous résolvons le MIP à l'aide de Gurobi, un logiciel commercial de résolution de MIP capable de résoudre ce type de problème à grande échelle de manière très efficace.

Outre l'évaluation et le classement des commandes individuelles, le modèle d'optimisation prend également en compte les commandes qui devraient être regroupées, c'est-à-dire servies par un seul et même Dasher, afin de gagner en efficacité. La mise en lots fonctionne particulièrement bien lorsque les commandes sont retirées chez le même commerçant, ce qui réduit le nombre de transactions de retrait, ou chez plusieurs commerçants proches, ce qui réduit le nombre d'instances de stationnement. Le temps nécessaire à la préparation d'une commande est en fait utile et peut nous permettre d'avoir plus de temps pour récupérer une autre commande en cours de route, plutôt que de simplement retarder une offre à un Dasher. Dans certains cas, la mise en lots permet d'améliorer à la fois l'utilisation efficace du temps du Dasher et la livraison plus rapide de la commande - en particulier lorsque nous n'avons pas beaucoup de Dashers disponibles dans cette zone. Dans d'autres cas, nous pouvons retarder légèrement le délai de livraison pour permettre à nos Dashers de gagner plus d'argent en servant plusieurs commandes simultanées sans violer la promesse de ponctualité que nous avons faite à nos clients. En ajustant la fonction de notation pour prendre en compte les commandes groupées et les comparer aux commandes uniques, nous permettons au solveur d'effectuer ces compromis efficacement pour nous.

Une dernière étape importante avant d'émettre des recommandations d'offres finales consiste à décider si nous choisissons le meilleur Dasher disponible maintenant ou si nous retardons l'envoi pour choisir un Dasher plus optimal qui pourrait être disponible dans un avenir proche. Une autre raison de retarder l'envoi est d'attendre que la commande soit prête pour que le Dasher n'ait pas à attendre trop longtemps au magasin. Grâce à notre moteur d'expédition dynamique, le modèle d'optimisation est capable de faire le meilleur compromis entre l'expédition immédiate et l'attente.

Après avoir noté et classé les offres, examiné les meilleurs lots et décidé de retarder ou non l'envoi, notre commande termine son parcours par l'envoi. La commande est proposée au Dasher que nous avons choisi, et nous attendons de voir s'il accepte ou refuse l'offre. Si nécessaire, nous trouverons un autre Dasher à qui proposer la commande, jusqu'à ce que la commande soit récupérée au magasin et livrée à l'heureux client. Notre commande a été expédiée !

Gestion des interactions entre les couches de ML et d'optimisation

Dans notre exemple de parcours d'expédition, notre nouvelle commande passe successivement par la couche ML, puis par la couche d'optimisation, avant qu'un Dasher ne soit envoyé pour récupérer la commande. Mais en réalité, il y a beaucoup d'interactions complexes entre nos modèles de ML et d'optimisation. Ces interactions posent trois défis importants que nous avons relevés lors de la construction de DeepRed.

  • Traiter les déchets à l'entrée et à la sortie 
  • Éviter le surajustement 
  • Gestion de la variabilité en cascade 

Examinons ces défis un par un. 

  • Le premier problème peut être qualifié de " garbage in, garbage out ". Dans un article précédent, Maintaining Machine Learning Model Accuracy Through Monitoring, nous avons décrit comment nous surveillons la dérive de nos modèles ML. Du point de vue de DeepRed, si nos prédictions de temps de préparation ou de temps de trajet commencent à dériver au fil du temps, la qualité de notre optimisation diminuera également. C'est pourquoi nous réentraînons continuellement nos modèles ML et utilisons des fonctions historiques et en temps réel qui garantissent que les entrées de nos modèles restent fraîches.
  • Le deuxième défi est le risque de surajustement des paramètres dans notre modèle d'optimisation. Il y a surajustement lorsque les paramètres sont réglés précisément en fonction des conditions observées dans le passé, mais qu'ils se traduisent par des performances sous-optimales lorsqu'ils sont soumis à de nouvelles entrées qui peuvent ne pas correspondre aux conditions historiques. Même si nos modèles ML sont entraînés à l'aide d'une régularisation afin d'éviter un surajustement des données d'entraînement, nous risquons toujours un surajustement des paramètres dans notre modèle d'optimisation si nous réglons nos paramètres de manière naïve sur la base d'un retour d'information empirique afin d'optimiser les performances à court terme. Nous pouvons tomber dans le piège d'un optimum local où toute amélioration de la précision de nos modèles ML ne parvient pas à améliorer le résultat de l'optimisation globale. Pour lutter contre l'overfitting, nous avons mis en œuvre des techniques d'optimisation bayésienne pour ajuster les paramètres de manière robuste et adaptative.
  • Le troisième défi est la variabilité en cascade. Chacun de nos modèles ML contribue à la variance de notre modèle de ce qui se passera lorsque nous proposerons un ensemble particulier de commandes à un Dasher particulier. Cette variabilité s'accumule à mesure qu'un itinéraire devient plus complexe ou plus long, par exemple en raison de la mise en lots. Nous avons conçu notre fonction de notation pour prendre en compte la variance ajoutée par des itinéraires plus complexes en ajoutant un terme de pénalité qui s'adapte à chacune de ces formes de complexité et décourage DeepRed de faire des offres avec une grande variabilité. 

En comprenant et en relevant les défis posés par les interactions entre les couches de ML et d'optimisation, nous avons conçu DeepRed pour qu'il soit aussi robuste que possible.

Comment nous améliorons le service d'envoi

Apporter des améliorations aux modèles qui alimentent la répartition est un défi, à la fois parce que nos décisions de répartition sont critiques pour l'activité de DoorDash et parce que tout changement de produit peut avoir des interactions complexes et des impacts en aval dans l'ensemble de DeepRed. Nous utilisons deux approches de modélisation pour atténuer ce défi : l'expérimentation et la simulation. La simulation hors ligne nous aide à explorer les idées de produits à un stade précoce afin d'évaluer et d'anticiper leurs impacts sur l'ensemble du système avant d'entreprendre un effort de mise en œuvre important. Une expérimentation rigoureuse nous aide à mesurer l'impact global de tous les changements - mineurs ou substantiels - apportés aux modèles de ML ou d'optimisation sous-jacents dans le cadre du dispatching. Dans cette section, nous allons décrire comment nous tirons parti de nos plateformes d'expérimentation et de simulation pour conduire des améliorations continues au sein de DeepRed.

Figure 3 Le cycle de vie d'un changement de produit DeepRed vers l'un de nos modèles de ML ou d'optimisation commence par la simulation en tant que bac à sable pour les idées et se termine par l'expérimentation sur notre marché.

Simulation des conditions réelles du marché

La simulation est un outil que nous pouvons utiliser pour accélérer le rythme et l'échelle de l'innovation et de la compréhension en prototypant de nouveaux concepts et en comprenant les impacts potentiels des changements de produits. Il est difficile de répondre à certaines questions par l'expérimentation, comme l'impact des changements de produits qui nécessitent un travail d'ingénierie substantiel sur l'ensemble de la plateforme, ou la manière dont DeepRed se comportera dans différentes conditions d'offre et de demande du marché que nous n'avons peut-être pas observées historiquement dans le monde réel.

L'exécution de simulations nous permet de créer des mondes contrefactuels où nous pouvons estimer comment de nouvelles idées ou des conditions environnementales différentes auraient un impact sur les mesures de performance de base, sans le risque de dégradation de l'expérience du client ou des mesures commerciales. Le simulateur que nous construisons peut imiter les comportements des consommateurs, des Dasher et des commerçants qui interagissent avec le système de répartition actuel ou testé. Les simulations nous donnent un aperçu de la manière dont les modèles de répartition fonctionnent dans différentes conditions d'exploitation, y compris l'efficacité avec laquelle nous pourrions gérer une forte demande, une faible disponibilité des Dasher et d'autres scénarios futurs probables que nous n'observons pas aujourd'hui.

Tester les modifications apportées aux produits en cours de production

Notre plateforme d'expérimentation nous aide à mesurer la performance réelle des changements apportés à nos modèles de ML et d'optimisation sur la base d'indicateurs commerciaux clés. Nous utilisons des méthodes d'expérimentation pour mesurer scientifiquement si nos améliorations font réellement bouger l'aiguille. Avec l'expérimentation, il y a deux façons de s'assurer que nous obtenons des mesures précises de l'impact des changements de produits : une conception réfléchie et une analyse rigoureuse.

  • La première approche consiste à réfléchir à la manière dont nous concevons nos expériences. Dans un article précédent, intitulé Tests à rebours et expérimentation aléatoire en présence d'effets de réseau chez DoorDash, nous décrivons le défi que représente l'expérimentation sur la place de marché de DoorDash et la manière dont nous surmontons les effets de réseau en utilisant des modèles d'expérimentation à rebours. Outre les effets de réseau, nous devons également nous préoccuper des effets d'interaction entre les expériences. Parce que l'expédition est au cœur de tout ce que nous faisons chez DoorDash et que le système est complexe, nous disposons d'une équipe importante de scientifiques et d'ingénieurs des données qui mènent de nombreuses expériences en même temps. Avec un cycle d'itération hebdomadaire et de nombreuses expériences en interaction, nous avons cherché des moyens de réduire les intervalles de confiance sur nos métriques de haut niveau. Pour ce faire, nous divisons chaque semaine nos zones géographiques et nos périodes de temps de manière aléatoire en deux groupes distincts. Nous utilisons le premier groupe pour mener un grand nombre d'expériences exploratoires. Dans ce groupe, nous obtenons une mesure initiale bruyante pour ces expériences. Les expériences qui donnent des résultats prometteurs dans le premier groupe peuvent être transférées la semaine suivante dans le deuxième groupe où nous effectuons un nombre restreint d'expériences (pas plus de trois) afin d'obtenir une mesure finale moins bruitée.
  • La deuxième approche pour obtenir des mesures précises consiste à faire attention à la manière dont nous analysons nos expériences. Plus précisément, il est important de trouver des moyens de réduire la variance dans nos estimateurs pour les mesures d'efficacité et de qualité. Certaines de nos méthodes de réduction de la variance, telles que l'erreur standard robuste en grappes, ont été examinées dans un article précédent. Nous utilisons également des méthodes de régression post hoc et l'analyse des effets d'interaction.

Constituer la bonne équipe

Il est essentiel de constituer la bonne équipe pour relever l'ensemble complexe de défis que présente le problème de la répartition. Le développement de modèles en ML, l'optimisation, l'expérimentation et la simulation requièrent un ensemble diversifié de compétences en science des données. Nous avons constitué et développé une équipe de science des données sur la répartition qui est diversifiée à travers les disciplines (OR, ML, inférence causale, statistiques) et l'expérience de l'industrie (ridesharing, gig economy, Google).

Conclusion

L'objectif de la répartition chez DoorDash est de trouver le bon Dasher pour livrer chaque commande du marchand au client. Les décisions que nous prenons en matière de distribution définissent l'expérience de nos Dashers, de nos clients et de nos commerçants, ainsi que l'efficacité avec laquelle notre place de marché fonctionne. Pour résoudre le problème de la répartition, nous avons utilisé le ML et l'optimisation pour construire notre moteur de répartition DeepRed. Nous nous sommes appuyés sur l'expérimentation et la simulation pour apporter des améliorations continues à DeepRed afin que les choses fonctionnent le mieux possible. Ces efforts ne seraient pas possibles sans l'équipe diversifiée et talentueuse de Data Science que nous avons constituée pour résoudre cet ensemble de problèmes passionnants.

About the Author

Emplois connexes

Job ID: 2915998
Localisation
Sao Paulo, Brazil
Département
Ingénierie
Localisation
Sunnyvale, CA
Département
Ingénierie
Localisation
Pune, Inde
Département
Ingénierie
Localisation
São Paulo, Brésil
Département
Ingénierie
Localisation
San Francisco, CA; Tempe, AZ
Département
Ingénierie