Uber: Présentation des algorithmes de gestion de plate-forme clés

1. Introduction

Les plates-formes de transport de passagers en ligne, telles que Uber, DiDi et Yandex, sont apparues assez récemment, alors qu'elles ont rapidement atteint une taille impressionnante et, malgré leur petit âge, ont considérablement modifié et complété le système de transport urbain. Les technologies et les modèles théoriques utilisés par ces plateformes (ou développés pour elles) sont actuellement un domaine de recherche active pour un large éventail de spécialistes de la communauté scientifique: économistes, mathématiciens, programmeurs et ingénieurs.

Dans cet article, nous (en tant que représentants de l'équipe d'optimisation de la place de marché Uber) présenterons brièvement un aperçu des principaux leviers de la gestion de l'efficacité des plateformes en ligne: algorithmes responsables de la répartition des décisions (appariement), de la tarification dynamique, et introduisons également l'un des nouveaux concepts - heure dynamique de rendez-vous de la voiture (attente dynamique). Sur la base d'une expérience pratique réelle, nous montrerons que les trois algorithmes jouent un rôle important dans la création d'un système à hautes performances et à temps d'attente bas pour les commandes des passagers et des conducteurs.

La description présentée des algorithmes sera de nature exploratoire et délibérément dénuée de profondeur et de rigueur techniques. Un lecteur intéressé est invité à étudier l'article original ( Dynamic Pricing and Matching in Ride-Hailing Platforms - N.Korolko , D.Woodard, C.Yan, H.Zhu - 2019), publié par des chercheurs de la place de marché Uber, sur la base duquel ce bref examen introductif et créé.

2. Description des principaux algorithmes

Au cours de la dernière décennie, l'industrie des solutions de transport a connu une croissance rapide grâce à de nouvelles idées et technologies conceptuelles, telles que les plates-formes de transport de passagers en ligne, le développement de voitures autonomes et de voitures électriques. La synergie de ces technologies, que de nombreuses entreprises et laboratoires travaillent en même temps, promet une énorme percée dans la réduction du coût unitaire du transport de passagers, pas moins de 10 fois sur une vingtaine d'années.

La croissance la plus explosive de cette liste de technologies est actuellement démontrée par les plateformes de transport de passagers en ligne. Par exemple, Uber a généré plus de 10 milliards de voyages dans plus de 80 pays et 700 villes à travers le monde au cours de ses 10 années d'existence [Figure 1]. Le marché mondial de ces transports en ligne promet d'atteindre une taille incroyable de 285 milliards de dollars d'ici 2030. Par conséquent, il n'est pas surprenant que l'efficacité de telles plateformes qui contrôlent dynamiquement le marché bilatéral des passagers et des conducteurs soit d'une grande importance pratique.



Des études empiriques montrent que des algorithmes automatisés de traitement des données, d'acheminement, de tarification et de commande permettent aux plateformes en ligne d'obtenir une utilisation plus élevée des heures de travail des conducteurs et des temps d'attente plus courts pour les passagers qu'un service de taxi classique. En outre, ces deux caractéristiques clés du système (utilisation du temps du conducteur et du temps d'attente des passagers) sont étroitement liées à la fiabilité et à la stabilité du service: des flambées soudaines de demande locale (par exemple, à la fin d'un grand concert ou le soir du Nouvel An) peuvent considérablement aggraver les deux mesures, ce qui permet d'utiliser service peu attrayant pour les deux côtés du marché. Cela est dû au fait que les conducteurs en ligne dans la zone de forte demande reçoivent rapidement une petite partie du nombre total de commandes, et les conducteurs des régions éloignées sont affectés à la partie restante des commandes. Cela augmente le délai de livraison de la voiture, qui n'est le plus souvent pas payé au conducteur (et donc réduit ses gains par unité de temps), et en même temps crée une impression négative sur le passager. Ainsi, les deux parties utilisant la plate-forme commencent à l'utiliser moins. Pour cette raison, les deux mesures commencent à se détériorer encore plus, entraînant ainsi la spirale descendante des performances de la plate-forme dans le sens d'une efficacité nulle. Dans la littérature anglaise, ce phénomène négatif est appelé la chasse à l'oie sauvage (WGC), dont la traduction littérale est «la poursuite de l'oie sauvage».

Deux technologies clés visant à augmenter la stabilité et la productivité de la plateforme sont les algorithmes de distribution des commandes et de tarification dynamique. La première technologie contrôle les décisions de répartition et la tarification dynamique en temps réel équilibre le rapport offre-demande extrêmement volatile pour le transport de passagers. La tarification dynamique est essentielle pour maintenir les performances du système, réduire le temps d'attente pour une voiture et augmenter le nombre de conducteurs pendant les périodes de forte demande. De plus, des études empiriques et théoriques montrent que la tarification dynamique peut réduire l'ampleur de l'effet pathologiquement dangereux du WGC.

2.1 Algorithmes de distribution des commandes (appariement)

L'algorithme de répartition le plus simple pour affecter un pilote à la commande est le protocole dit de première répartition. Malgré sa simplicité et ses bons indicateurs de performance pratiques, il est facile de montrer que cet algorithme est inefficace dans un grand nombre de situations fréquentes. Premièrement, il sélectionne un conducteur uniquement dans ce sous-ensemble de conducteurs qui étaient libres au moment de la commande, ignorant ceux qui pourraient être sur le point de terminer un trajet à proximité immédiate d'une nouvelle commande [Figure 4]. Deuxièmement, cet algorithme simple ne prend en compte que les informations sur le système dans un laps de temps donné, alors que le plus souvent la plate-forme peut recevoir des informations suffisamment précises sur ce qui se passera avec le flux des commandes et la répartition spatiale des conducteurs dans un avenir proche. Dans la littérature, une classe de tâches similaires donnant des recettes pratiques sur la façon dont ces informations peuvent être utilisées pour améliorer la qualité de l'algorithme est appelée le «problème du serveur K».



Une autre famille populaire d'algorithmes de répartition est basée sur l'idée de combiner un groupe d'ordres de voyage dans un court intervalle de temps et de résoudre le problème d'optimisation agrégé de l'affectation par paire. En d'autres termes, au lieu d'attribuer instantanément et séquentiellement une voiture à chaque commande individuelle, le système collecte des informations sur les commandes entrantes et répartit les commandes accumulées entre les conducteurs sur la ligne avec une certaine fréquence. Si certaines commandes sont laissées sans pilote désigné, elles restent dans le système et participent à la tâche de distribution du pas de temps suivant. La fonction objective de la tâche d'optimisation à résoudre à chaque étape peut inclure un large éventail de métriques caractérisant la qualité des rendez-vous de répartition générés: temps d'attente du passager pour la voiture, distance entre la commande et le conducteur désigné, probabilité d'annulation de la commande par le passager ou le conducteur, etc.

En pratique, les algorithmes de répartition semblent beaucoup plus compliqués, car ils doivent prendre en compte un grand nombre de fonctionnalités de différents produits qui sont présentées simultanément dans l'interface de l'application. Par exemple, les voitures immatriculées sur la plateforme peuvent être de différentes classes de confort et de capacités différentes. Certains produits de plateformes en ligne impliquent l'utilisation simultanée d'une voiture par différents passagers (UberPool, Lyft Line), si leurs itinéraires sont assez proches. De plus, les décisions de répartition doivent souvent prendre en compte les préférences des chauffeurs pour les zones de service et le sens des commandes reçues par eux. Ainsi, l'éventail des problèmes d'optimisation qui se posent pour augmenter l'efficacité des décisions de répartition, qui doivent également être résolus en temps réel, est continuellement mis à jour avec de nouvelles formulations de plus en plus complexes.

2.2 Algorithmes de tarification dynamique

L'une des principales difficultés opérationnelles de la gestion de la plate-forme de transport de passagers en ligne est le volume de la demande et de l'offre de services de taxi qui évoluent constamment dans l'espace et dans le temps. La figure ci-dessous [Figure 5] montre le rapport entre le nombre de demandes de voyage en ligne des passagers et le nombre d'heures que les conducteurs ont passé sur la ligne pour deux quartiers de San Francisco: le centre financier et le coin nuit résidentiel à la périphérie de la ville. Ce graphique illustre bien la forte volatilité et le manque d'équilibre entre l'offre et la demande (dont le rapport peut parfois prendre des valeurs extrêmement élevées), ainsi que la diversité du comportement de cet équilibre en fonction de la situation géographique.



Afin de contrôler l'équilibre de l'offre et de la demande dans l'espace et dans le temps, les plateformes en ligne utilisent des algorithmes de tarification dynamique qui augmentent le tarif de base en temps réel si le nombre de commandes reçues de passagers dépasse de manière significative le nombre de conducteurs libres. Les avantages de la tarification dynamique pour maintenir des performances de plate-forme stables sont soutenus par un grand nombre de modèles théoriques, d'expériences et d'observations empiriques associées à des charges système record. De telles charges peuvent survenir pour un grand nombre de raisons prévisibles et peu nombreuses: conditions météorologiques défavorables, événements publics, dysfonctionnement des transports en commun, etc. En cas de mauvais fonctionnement de l'algorithme de tarification, avec une forte augmentation du nombre de demandes des passagers (ou avec une forte diminution du nombre de voitures disponibles), vous pouvez observer une très faible proportion de passagers auxquels la voiture est attribuée en conséquence et le délai insatisfaisant de sa soumission. Le rôle clé de la tarification dynamique pour une plateforme en ligne est de permettre à n'importe quel utilisateur, n'importe où et à tout moment, d'appeler un taxi. Même si le tarif proposé est plus élevé que d'habitude, ce sera une option plus favorable que d'informer l'utilisateur de la plate-forme (qui peut avoir un besoin urgent d'une voiture) qu'il n'y a actuellement aucune machine disponible.

Les méthodes populaires de modélisation de la tarification dynamique comprennent les modèles économiques qui décrivent un modèle en régime permanent, les modèles de programmation dynamique, l'analyse de régression et les modèles d'optimisation qui décrivent l'optimisation du réseau. Des études récentes d'économistes (Castillo, 2017) ont montré qu'une augmentation tarifaire dynamique permet également à la plateforme d'éviter de tomber dans la zone d'effet négatif de la WGC, dont nous avons parlé plus haut.

La tarification dynamique présente des défauts objectifs. Premièrement, le prix final d'un voyage, que les passagers voient lors de la commande d'un taxi, peut varier considérablement en raison de la volatilité de l'offre et de la demande, augmentant ainsi l'imprévisibilité du prix sur le même trajet. D'un autre côté, les conducteurs de plateformes en ligne ont souvent accès à des informations dans l'application sur les quartiers de la ville où le facteur d'augmentation est actif. Cependant, en raison de la forte volatilité de ce coefficient, au moment où le conducteur se déplace vers la zone de prix plus élevés, le tarif peut revenir aux valeurs de référence. De plus, une augmentation automatique des tarifs par l'algorithme peut encourager les conducteurs à coopérer et créer artificiellement sur le marché local une situation de pénurie de voitures disponibles à la commande, activant ainsi des coefficients croissants pour les trajets. Bien sûr, un tel comportement coordonné des conducteurs n'est pas difficile à détecter pour les plates-formes qui traitent une grande quantité de données de commande et prennent les mesures de protection nécessaires, mais pour les passagers, une telle expérience de prix artificiellement élevés peut ne pas être satisfaisante.

2.3 Temps d'attente dynamique de la voiture (attente dynamique)

Pour éviter les problèmes liés à la tarification dynamique, en pratique, d'autres algorithmes sont utilisés pour équilibrer l'offre et la demande, ainsi que pour éviter de placer le système dans la zone de l'effet WGC. Il s'agit notamment de l'idée de limiter la distance maximale entre la commande et le chauffeur désigné (Rayon de répartition maximum), ainsi que la formation d'une file d'attente des ordres de voyage (file d'attente) reçus dans le système, remplaçant la nomination instantanée du chauffeur pour chaque commande.

Un nouveau concept visant à remplacer ou à compléter une augmentation dynamique des prix est le mécanisme de contrôle dynamique du temps d'attente avant l'attribution d'une voiture (attente dynamique). Une variante de ce mécanisme est utilisée dans le produit Express Pool, récemment lancé par Uber sur certains grands marchés. Ce type de transport de passagers se caractérise par les tarifs les plus bas possibles et implique l'utilisation simultanée d'une seule voiture par plusieurs passagers indépendants pour voyager en cours de route.

L'idée générale du mécanisme de temps de destination dynamique est la suivante. Pour un passager commandant un voyage, l'application ne nomme pas instantanément un conducteur, mais propose d'attendre, mais pas plus qu'un certain temps indiqué à l'avance (les limites supérieures typiques sont de 2 ou 5 minutes). De plus, le rendez-vous du conducteur peut survenir à tout moment convenable pour la plateforme: de l'instant à la limite supérieure spécifiée. Dans ce cas, le temps d'attente total des passagers pour la voiture se compose de deux parties (presque indépendantes): le temps jusqu'à ce que le conducteur soit nommé et le temps de sa nomination à l'arrivée au lieu de commande. L'inconvénient d'attendre un passager est compensé par un tarif inférieur.

Du côté de la plate-forme, un degré de liberté supplémentaire au fil du temps que les pilotes sont attribués aux commandes est utilisé comme suit. Étant donné que le produit implique la combinaison de commandes et la nomination d'une voiture pour le transport simultané de plusieurs passagers, le temps supplémentaire pour collecter des informations vous permet d'augmenter le nombre d'options combinatoires et, par conséquent, de générer des voyages plus efficaces. Dans ce cas, la métrique d'efficacité peut être, par exemple, la proximité des itinéraires de passagers tombant dans une voiture. Evidemment, dès que la plateforme trouve une combinaison de déplacements suffisamment performante, elle prend immédiatement le rendez-vous du chauffeur nécessaire et informe tous ses participants. Si une combinaison réussie et pratique n'est pas trouvée, la plate-forme envoie un chauffeur individuel à chacun des passagers qui ont passé la commande.

Le mécanisme décrit optimise principalement les décisions d'expédition et le moment où ces décisions sont prises, et il peut être utilisé simultanément avec l'optimisation dynamique des prix. Le modèle théorique développé et analysé dans l'original de l'article principal démontre que l'optimisation simultanée des prix et du temps présente un grand nombre d'avantages: elle permet de réduire la volatilité tarifaire, de réduire les risques de l'effet WGC, et également d'augmenter le nombre total de trajets générés par la plateforme par unité de temps. De plus, ces options de transport sont plus économiques à la fois pour les conducteurs (qui reçoivent simultanément plusieurs passagers payant le voyage) et pour les passagers (qui bénéficient d'une remise en échange d'une flexibilité avec le temps d'attente).

3. Conclusion

Dans cet article, nous avons brièvement décrit les principales tâches de gestion de l'optimisation qui résolvent les plateformes de transport de passagers en ligne pour assurer un fonctionnement stable et augmenter leur efficacité. Ces tâches comprennent la construction d'algorithmes de répartition, des algorithmes de tarification dynamique et la détermination dynamique des heures de rendez-vous des conducteurs. La gestion simultanée de ces leviers permet d'atteindre des taux élevés d'utilisation du temps des conducteurs, un temps d'attente bas pour la voiture et le nombre de déplacements générés par la plateforme par unité de temps. La classe de ces tâches est constamment mise à jour avec de nouveaux exemples de plus en plus réalistes, ouvrant de larges horizons pour la recherche théorique et pratique.

Toutes les références aux sources citées se trouvent dans l'article original ( Dynamic Pricing and Matching in Ride-Hailing Platforms - N.Korolko , D.Woodard , C.Yan , H.Zhu - 2019).