Repenser l'algorithme de tarification des transporteurs d'Uber Freight pour de meilleurs résultats

Par : Kenneth Chong (Scientifique appliqué Sr.), Joon Ro (Scientifique appliqué Sr.), Emir Poyraz (Ingénieur Sr.) et May Wu (Responsable de la science appliquée)

Une approche innovante d'un algorithme classique

Uber Freight opère sur un marché biface, qui interagit séparément avec les expéditeurs (qui cherchent à déplacer des chargements du point A au point B) et avec les transporteurs (les chauffeurs de camion qui déplacent ces chargements). Les deux côtés de ce marché sont alimentés par des algorithmes de tarification dynamique. Chacun est structuré différemment en fonction des besoins du marché respectif.

Récemment, notre équipe a identifié le besoin de modifier l'algorithme dictant la tarification des transporteurs. L'algorithme génère un tarif basé sur divers facteurs comme les conditions du marché, la taille du chargement, la distance à parcourir, etc. Jusqu'à présent, nous utilisions un algorithme basé sur les Processus de Décision Markoviens (MDP) pour établir les prix des transporteurs (voir cet article de blog précédent pour une description complète du fonctionnement du modèle MDP) car il est naturellement adapté à notre problème : nous devons prendre des décisions de tarification séquentiellement dans le temps. Au fil du temps, nous avons réalisé que, bien que l'algorithme soit performant, il présentait des lacunes difficiles à résoudre avec une implémentation MDP standard.

Nous avons surmonté ces difficultés en :

1. Tronquant l'induction rétrograde

2. S'appuyant davantage sur l'apprentissage automatique (ML) pour approximer la fonction de valeur

3. Développant un nouvel algorithme de clustering pour identifier des chargements "similaires" qui peuvent être utiles pour estimer les coûts—combinant de manière créative l'optimisation et le ML pour développer ce que nous considérons comme une version plus robuste du MDP.

Le MDP est un choix naturel d'algorithme, mais sa mise en œuvre est difficile

Pour illustrer brièvement le problème de la tarification des transporteurs, supposons que nous nous soyons engagés auprès de l'expéditeur à transporter un chargement de Chicago, IL à Dallas, TX. Le rendez-vous d'enlèvement commence exactement dans 5 jours : en d'autres termes, le délai d'anticipationT est de 120 heures. Comme il devient plus difficile de trouver des transporteurs avec un préavis plus court, les prix ont tendance à augmenter à mesure que le délai diminue. Ainsi, nous avons une séquence de décisions à prendre au fil du temps, que nous appelons une trajectoire de prix :

Figure 1 : Exemple d'une trajectoire de prix sur un délai d'anticipation de 5 jours

Comme nous mettons à jour les prix toutes les heures, cette trajectoire peut être représentée comme une séquence {pt}t∈{T, T-1, …, 0}, où pt est le prix offert t heures avant l'enlèvement. L'objectif de notre algorithme est de choisir une trajectoire qui minimise, en espérance, le coût total pour couvrir le chargement. Nous appelons cette quantité eCost :

eCostT=∑t=T0ptPr(Bt=1 | pt,St),

où Bt = 1 si le chargement i est réservé au délai d'anticipation t (0 sinon), et St désigne les variables d'état (éventuellement variables dans le temps) autres que le prix qui peuvent affecter la probabilité de réservation. Cette quantité augmente généralement avec le temps si le chargement reste non réservé.

Avec MDP, le calcul de eCost implique de résoudre l'équation de Bellman

Vt =minpt[Pr(Bt | pt, St)pt +(1-Pr(Bt | pt, St))Vt-1] t∈{0, 1, …, T}

Les quantités {Vt} sont directement interprétables comme eCost, conditionnellement à notre politique de tarification. Cependant, une entrée cruciale dans le MDP est l'estimation précise des probabilités de réservation Pr(Bt=1 | pt , St). Bien que le modèle ML que nous utilisons à cet effet fonctionne bien, les erreurs peuvent s'accumuler au fil du temps. Cela signifie que nous devenons vulnérables à la malédiction de l'optimiseur, qui stipule qu'en présence de bruit, les estimations de coût total associées à la décision optimale sont susceptibles d'être sous-estimées. Cela conduit à des prix plus bas, trop optimistes, qui ont tendance à diminuer davantage à des délais d'anticipation plus élevés.

De plus, la malédiction de la dimensionnalité présente des défis importants dans la modélisation de transitions d'état plus complexes. Par exemple, l'incorporation de caractéristiques en temps quasi réel (NRT), comme l'activité de l'application, dans nos prix implique de les ajouter aux variables d'état – ce qui rend rapidement notre problème impossible à calculer.

Notre approche : un mélange soigné de prédiction et d'optimisation

Pour améliorer la précision des prix, nous avons exploré l'utilisation d'un modèle prédictif, plutôt qu'une induction rétrograde standard, pour estimer eCost. En particulier, nous effectuons K ≤ T étapes d'induction rétrograde, et si le chargement reste non réservé après K heures, nous substituons à la valeur de continuation VT-K une prédiction de ce modèle. Dans ce cas, les équations de Bellman deviennent :

Vt =minpt[Pr(Bt | pt, St)pt +(1-Pr(Bt | pt, St))Vt-1] t∈{T-K+1, …, T-1, T}

avec la condition limite VT-K =eCostT-K.

Figure 2 : Illustration de la prise de décision séquentielle dans le MDP

Choisir une valeur appropriée pour K a nécessité quelques itérations, mais cette induction rétrograde tronquée aide à atténuer chacun des problèmes que nous avons soulignés ci-dessus.

Un premier candidat pour un tel modèle prédictif était un ensemble XGBoost que nous avions précédemment utilisé ailleurs dans la tarification des transporteurs. Les données d'entraînement consistaient en des chargements historiques, leurs caractéristiques (que nous décrivons plus en détail ci-dessous), les délais d'anticipation auxquels ils ont été réservés, ainsi que leurs coûts réalisés.

Cependant, les prédictions générées par ce modèle n'étaient pas adaptées pour estimer eCost pour deux raisons.

1. Il existe une distinction importante entre le délai d'anticipation restant d'un chargement et son délai d'anticipation disponible. Bien que nous inclurions le premier dans le vecteur de caractéristiques au moment de la diffusion, il existe des modèles systématiques dans le second. C'est-à-dire que des chargements similaires ont tendance à devenir disponibles à des délais d'anticipation spécifiques. Par exemple, les transports plus longs ont tendance à devenir disponibles avec des délais d'anticipation plus élevés que les transports plus courts. Ainsi, nous aurions des concentrations de points de données autour de certains délais d'anticipation disponibles, rendant les prédictions à d'autres délais moins fiables.

2. Les données d'entraînement consistaient uniquement en des résultats—les réalisations de variables aléatoires, plutôt que leurs espérances—donc les prédictions de ce modèle ne pouvaient pas non plus être interprétées comme un eCost. Il n'était pas clair comment modifier l'ensemble d'entraînement pour que les prédictions du modèle XGBoost puissent être traitées comme des espérances.

Au lieu d'essayer de prédire directement eCost, nous empruntons des principes du clustering pour trouver un ensemble de chargements similaires à celui à tarifer, et prenons une moyenne pondérée de leurs coûts totaux. Avec cette approche, les délais d'anticipation restants peuvent être explicitement incorporés dans eCost — nous pouvons exclure, de l'ensemble des chargements similaires, ceux qui ont été réservés plus tôt que le délai d'anticipation restant du chargement actuel. De plus, chacun des chargements similaires identifiés peut être considéré comme un résultat potentiel pour le chargement actuel, auxquels sont attribuées des probabilités égales aux poids utilisés dans la moyenne.

Le principal défi ici est de développer une façon de mesurer la similarité entre les chargements, que nous décrivons avec un certain nombre d'attributs :

• Emplacements des installations d'enlèvement et de livraison

• Heure de la journée, jour de la semaine où le chargement est prévu pour être enlevé ou livré

• Conditions du marché autour du moment où le chargement est prévu pour être déplacé

Il y a un mélange de caractéristiques continues et catégorielles, et il n'est pas du tout clair comment celles-ci devraient être pondérées les unes par rapport aux autres lors du calcul de la similarité.

... avec un algorithme de clustering non conventionnel

Nous avons développé un nouvel algorithme où notre modèle XGBoost susmentionné est utilisé pour effectuer le clustering. Considérons le cas simple où notre modèle est un seul arbre de décision (peu profond) avec une seule caractéristique : la distance de conduite. Nous pourrions obtenir un arbre comme le suivant :

Figure 3 : Illustration d'un arbre de décision unique pour le clustering

Deux chargements peuvent être considérés comme "similaires" si leurs prédictions sont faites à partir du même nœud feuille. Dans le cas du nœud feuille n°6, nous savons que leurs distances de route sont toutes deux comprises entre 282 et 458 miles.

Cela peut sembler une façon rudimentaire de mesurer la similarité, mais en développant des arbres de décision plus profonds et en incorporant plus de caractéristiques, nous exigeons que les deux chargements aient des valeurs comparables sur plusieurs dimensions pour être considérés comme "similaires". Nous pouvons différencier davantage en développant des arbres supplémentaires. En résumé, nous associons à chaque chargement un vecteur d'embedding, composé de valeurs non nulles aux emplacements correspondant aux nœuds feuilles dans lesquels le chargement se retrouve. Nous mesurons la similarité entre les chargements par la similarité cosinus de leurs embeddings, qui est directement liée au nombre d'arbres dans lesquels les deux ont des nœuds feuilles communs.

Des prix plus stables ont conduit à de meilleurs résultats de réservation

Étant donné les changements assez substantiels que nous avons apportés à l'algorithme, nous avons effectué un déploiement en deux phases principales. Premièrement, nous avons incorporé eCost dans les algorithmes que nous utilisions dans les canaux de réservation secondaires, et avons mené un test A/B pour garantir qu'il n'y ait pas de baisse de performance. Deuxièmement, nous avons réalisé une expérience de switchback le comparant avec la version précédente du MDP. L'effet net de ces deux expériences a été une réduction statistiquement significative du coût total de couverture des chargements, sans aucun impact négatif sur les métriques secondaires. Nous attribuons cela aux trajectoires de prix plus stables générées par le nouvel algorithme, ce qui entraîne une réservation plus précoce des chargements dans leur cycle de vie. Ceci est particulièrement pertinent, car les coûts ont tendance à augmenter fortement une fois que les délais d'anticipation tombent en dessous de 24 heures.

Le déploiement de ce nouvel algorithme s'accompagne d'un certain nombre d'avantages secondaires. La réservation plus précoce des chargements, due à des trajectoires de prix plus stables, réduit non seulement les coûts mais est cruciale pour éviter les fortes augmentations de coûts associées à des délais d'anticipation plus courts. La réduction du coût total pour couvrir les chargements nous permet d'offrir des prix plus compétitifs aux expéditeurs, ce qui, à son tour, augmente le volume. De plus, des trajectoires de prix plus plates pourraient amener les transporteurs à consulter les chargements sur l'application plus tôt dans leur cycle de vie. Au-delà de ces avantages commerciaux, l'algorithme a également contribué à réduire la dette technique en unifiant la tarification à travers les canaux de réservation, ainsi qu'en supprimant les composants non essentiels utilisés dans l'implémentation précédente du MDP.

Bien que nous pensions qu'il y a des domaines à améliorer davantage, ce nouvel algorithme de tarification fournit un modèle pour l'application du MDP à de nouveaux cas d'utilisation au sein d'Uber Freight.

*Comme nous utilisons également eCost comme une sorte d'approximateur de fonction de valeur, le problème que nous résolvons maintenant partage certaines similitudes avec un programme dynamique approximatif.