Tarification dynamique ou comment Yandex.Taxi prédit une forte demande

Auparavant, pour appeler un taxi, ils devaient appeler différents numéros des services de répartition et attendre que la voiture soit livrée pendant une demi-heure ou plus. Désormais, les services de taxi sont bien automatisés et le délai moyen de livraison d'une voiture Yandex.Taxi à Moscou est d'environ 3-4 minutes. Mais cela vaut la peine de pleuvoir ou de mettre fin à un événement de masse, et encore une fois, nous risquons de manquer de voitures gratuites.

Je m'appelle Anton Skogorev, je dirige le groupe de développement des performances de la plateforme Yandex.Taxi. Aujourd'hui, je dirai aux lecteurs de Habr comment nous avons appris à prédire la forte demande et à attirer en outre des conducteurs afin que les utilisateurs puissent trouver une voiture gratuite à tout moment. Vous apprendrez comment se forme un coefficient qui affecte la valeur de la commande. Tout y est loin d'être aussi simple que cela puisse paraître à première vue.

Défi de tarification dynamique

La tâche la plus importante de la tarification dynamique est de toujours offrir la possibilité de commander un taxi. Il est obtenu en utilisant le coefficient de surtension, par lequel le prix calculé est multiplié. Nous appelons cela simplement une montée subite. Il est important de dire que la surtension non seulement régule la demande de taxis, mais contribue également à attirer de nouveaux conducteurs pour augmenter l'offre.

Si la poussée est trop importante, nous réduirons trop la demande, il y aura un excès de voitures gratuites. S'il est trop bas, les utilisateurs verront "pas de voitures gratuites". Vous devez être en mesure de choisir un coefficient auquel nous marcherons sur une glace mince entre le manque de voitures gratuites et la faible demande.

De quoi devrait dépendre ce coefficient? Il vient immédiatement à l'esprit la dépendance à l'égard du nombre de voitures et de commandes autour de l'utilisateur. Maintenant, vous pouvez simplement diviser le nombre de commandes par le nombre de pilotes, obtenir le coefficient et le transformer en augmentation avec une formule (éventuellement linéaire).

Mais il y a un petit problème dans cette tâche - il peut être trop tard pour compter les commandes autour de l'utilisateur. Après tout, une commande est presque toujours une machine déjà occupée, ce qui signifie qu'une augmentation de notre coefficient sera toujours en retard. Par conséquent, nous ne considérons pas les commandes créées, mais les intentions de commander des épingles de voiture. Une épingle est une étiquette «A» sur une carte qu'un utilisateur met lors du lancement de notre application.



Formulons le problème: nous devons lire les valeurs instantanées des machines et des broches à un moment donné de l'utilisateur.

Nous comptons le nombre de broches et de voitures autour

Lorsque la position de la broche change (l'utilisateur sélectionne le point «A»), l'application utilisateur envoie de nouvelles coordonnées et une petite feuille d'informations supplémentaires au backend, ce qui permet d'évaluer la broche plus précisément (par exemple, le tarif sélectionné).

Nous essayons d'adhérer à l'architecture de microservice, où chaque microservice est engagé dans des tâches distinctes. Le microservice Surger est engagé dans le calcul des surtensions. Il enregistre les broches, les enregistre dans la base de données et met également à jour le nugget des broches dans la RAM, dans lequel elles s'intègrent assez bien. Le décalage du cache pendant un tel travail n'est que de quelques secondes, ce qui est acceptable dans notre cas.


Un cache chaud est construit avec un index de hachage géographique . Nous regroupons toutes les broches par geohash, puis collectons les broches pour le rayon souhaité autour du point de commande.

Nous faisons de même avec les voitures, mais dans un autre service appelé Tracker, auquel le Surger répond simplement par la question "combien de conducteurs se trouvent dans ce rayon".

Nous considérons donc les valeurs instantanées du coefficient.

Mise en cache

Cas : vous vous trouvez dans le Garden Ring à Moscou et vous souhaitez réserver une voiture. Dans le même temps, le prix grimpe assez souvent et c'est gênant.

Connaissant déjà la mécanique, on peut comprendre que cela peut être dû au fait que les conducteurs s'accumulent à un feu de circulation conditionnel au moment de la demande de surtension et partent également rapidement. Pour cette raison, la flambée et le prix peuvent sensiblement «sauter».

Pour éviter cela, nous mettons en cache la valeur de surtension par utilisateur. Lorsqu'un utilisateur vient pour une surtension, nous cherchons à voir s'il existe une valeur de surtension enregistrée pour cet utilisateur dans un rayon acceptable (un tour linéaire de toutes les surtensions enregistrées de l'utilisateur). S'il y en a, nous le restituons, sinon nous comptons sur un nouveau et le sauvegardons également.

Cela a bien fonctionné, mais il existe d'autres situations.

Cas : 2 utilisateurs demandent une surtension. L'un commande 30 secondes plus tard que l'autre lorsque des voitures d'un feu de circulation d'un cas passé sont déjà parties. Nous obtenons une image où 2 utilisateurs commandant presque simultanément peuvent avoir des surtensions sensiblement différentes.

Et ici, nous passons du cache par utilisateur au cache par position. Maintenant, au lieu de mettre en cache la valeur de surtension uniquement par utilisateur, nous commençons à la mettre en cache par le hachage géographique que nous connaissons déjà. Nous avons donc presque résolu le problème. Pourquoi presque? Parce qu'il peut y avoir des différences aux frontières des geoheshes. Mais le problème n'est pas si important, car nous avons un lissage.

Lissage

Peut-être, à la lecture d'un cas concernant un feu de circulation, vous avez pensé qu'il était en quelque sorte injuste d'envisager une surtension instantanée, en fonction du feu de circulation. Nous le pensons également, nous avons donc trouvé un moyen de régler la situation.

Nous avons décidé d'emprunter la méthode des voisins les plus proches à l' apprentissage automatique pour le problème de régression afin de déterminer à quel point la valeur de la surtension instantanée est différente de ce qui se passe autour.

L'étape de formation, comme dans la description formelle de la méthode, consiste à stocker tous les objets - dans notre cas, les valeurs calculées de la surtension dans la broche, nous faisons déjà tout cela au moment de charger toutes les broches dans le cache. La petite chose est de calculer la valeur instantanée, de la comparer avec la valeur de la zone et de convenir que l'on ne peut pas trop s'écarter de la valeur de la zone.

Nous obtenons donc un système avec une réponse rapide aux événements et vous permettant de lire rapidement la valeur du coefficient croissant.

Carte de conduite Surge

Pour communiquer avec le conducteur, nous devons être en mesure d'afficher la carte de surtension dans l'application du conducteur - un taximètre. Cela permet au conducteur de savoir s'il existe une demande dans la région où il se trouve actuellement et où il doit se déplacer pour obtenir les commandes les plus chères. Pour nous, cela signifie que davantage de conducteurs arriveront dans la zone à forte demande et la régleront.



Nous vivons avec le paradigme que l'appareil du pilote est un appareil plutôt faible. Par conséquent, le rendu de la grille hexagonale de surtension se trouve sur le côté backend. Le client vient au backend pour les tuiles. Ce sont des images tramées découpées pour un affichage direct sur la carte.

Nous avons un service séparé qui récupère périodiquement les moulages de broches du microservice Surger et calcule toutes les méta-informations nécessaires pour rendre la grille hexagonale: où est quel hex et quelle surtension se trouve dans chacun.

Conclusion

La tarification dynamique est une recherche constante d'un équilibre entre l'offre et la demande, afin que les utilisateurs disposent toujours de voitures gratuites, y compris par le biais du mécanisme visant à attirer des conducteurs supplémentaires dans les zones à forte demande. Par exemple, nous travaillons actuellement sur une utilisation plus approfondie de l'apprentissage automatique pour calculer la surtension. Dans le cadre de l'une des tâches dans ce domaine, nous apprenons à déterminer la probabilité de conversion d'une broche en commande et à prendre en compte ces informations. Il y a assez de travail ici, nous sommes donc toujours ravis des nouveaux spécialistes de l'équipe.

Si vous souhaitez en savoir plus sur une partie de ce grand sujet, écrivez dans les commentaires. Vos commentaires et idées sont également les bienvenus!

PS Dans la prochaine publication, mon collègue parlera de l'utilisation du machine learning pour prédire l'heure d'arrivée prévue d'un taxi.