Un bon service de taxi doit être sûr, fiable et rapide. L'utilisateur n'entrera pas dans les détails : il est important pour lui qu'il clique sur le bouton « Commander » et reçoive le plus rapidement possible une voiture qui le conduira d'un point A à un point B. S'il n'y a pas de voiture à proximité, le service doit en informer immédiatement afin que le client n'ait pas de fausses attentes. Mais si le panneau « Pas de voitures » apparaît trop souvent, alors il est logique qu'une personne cesse tout simplement d'utiliser ce service et s'adresse à un concurrent.
Dans cet article, je souhaite expliquer comment, grâce à l'apprentissage automatique, nous avons résolu le problème de la recherche de voitures dans des zones à faible densité (en d'autres termes, là où, à première vue, il n'y a pas de voitures). Et qu’en est-il arrivé.
Préhistoire
Pour appeler un taxi, l’utilisateur effectue quelques étapes simples, mais que se passe-t-il à l’intérieur du service ?
| Utilisateur | Stage | Backend Yandex.Taxi |
|---|---|---|
| Sélectionne le point de départ | Broche | Nous lançons une recherche simplifiée de candidats - recherche d'épingles. Sur la base des chauffeurs trouvés, l'heure d'arrivée est prédite - ETA dans le code PIN. Le coefficient croissant en un point donné est calculé. |
| Sélectionne la destination, le tarif, les exigences | Offrir | Nous construisons un itinéraire et calculons les prix pour tous les tarifs, en tenant compte du coefficient croissant. |
| Appuie sur le bouton « Appeler un taxi » | Заказ | Nous lançons une recherche complète de la voiture. Nous sélectionnons le chauffeur le plus adapté et lui proposons une commande. |
Sur , и nous avons déjà écrit. Et c'est une histoire de recherche de pilotes. Lorsqu'une commande est créée, la recherche s'effectue deux fois : sur le Pin et sur la commande. La recherche d'une commande se déroule en deux étapes : le recrutement des candidats et le classement. Tout d'abord, les candidats conducteurs disponibles sont trouvés les plus proches le long du graphique routier. Ensuite, les bonus et le filtrage sont appliqués. Les candidats restants sont classés et le gagnant reçoit une offre de commande. S'il est d'accord, il est affecté à la commande et se rend au point de livraison. S'il refuse, l'offre passe à la suivante. S'il n'y a plus de candidats, la recherche recommence. Cela ne dure pas plus de trois minutes, après quoi la commande est annulée et brûlée.
La recherche sur une épingle est similaire à la recherche sur une commande, sauf que la commande n'est pas créée et la recherche elle-même n'est effectuée qu'une seule fois. Des paramètres simplifiés pour le nombre de candidats et le rayon de recherche sont également utilisés. De telles simplifications sont nécessaires car il y a un ordre de grandeur plus de broches que de commandes, et la recherche est une opération assez difficile. Le point clé de notre histoire : si lors de la recherche préliminaire aucun candidat approprié n'a été trouvé sur le Pin, alors nous ne vous permettons pas de passer une commande. Du moins, c'était comme ça avant.
Voici ce que l'utilisateur a vu dans l'application :
Rechercher des voitures sans voitures
Un jour, nous avons émis une hypothèse : peut-être que dans certains cas, la commande peut encore être exécutée, même s'il n'y avait aucune voiture sur la broche. Après tout, un certain temps s'écoule entre le code PIN et la commande, et la recherche de la commande est plus complète et parfois répétée plusieurs fois : pendant ce temps, des pilotes disponibles peuvent apparaître. Nous savions aussi le contraire : si des drivers étaient trouvés sur la broche, ce n'était pas un fait qu'ils seraient trouvés lors de la commande. Parfois, ils disparaissent ou tout le monde refuse la commande.
Pour tester cette hypothèse, nous avons lancé une expérimentation : nous avons arrêté de vérifier la présence de voitures lors d'une recherche sur un Pin pour un groupe test d'utilisateurs, c'est-à-dire qu'ils ont eu la possibilité de passer une « commande sans voiture ». Le résultat était assez inattendu : si la voiture n'était pas sur l'épingle, alors dans 29 % des cas, elle a été trouvée plus tard - lors de la recherche sur la commande ! De plus, les commandes sans voitures n'étaient pas significativement différentes des commandes régulières en termes de taux d'annulation, de notes et d'autres indicateurs de qualité. Les réservations sans voiture représentaient 5 % de toutes les réservations, mais un peu plus de 1 % de tous les voyages réussis.
Pour comprendre d’où viennent les exécuteurs de ces ordres, regardons leurs statuts lors d’une recherche sur un Pin :
- Disponible: était disponible, mais pour une raison quelconque, il n'a pas été inclus parmi les candidats, par exemple, il était trop loin ;
- Sur commande: était occupé, mais a réussi à se libérer ou à devenir disponible pour ;
- Occupé: la possibilité d'accepter les commandes a été désactivée, mais le chauffeur est ensuite revenu dans la file d'attente ;
- Pas disponible: le chauffeur n'était pas en ligne, mais il est apparu.
Ajoutons la fiabilité
Les commandes supplémentaires sont une bonne chose, mais 29 % des recherches réussies signifient que 71 % du temps, l'utilisateur a attendu longtemps et n'a finalement abouti à rien. Bien que ce ne soit pas une mauvaise chose du point de vue de l'efficacité du système, cela donne en fait de faux espoirs à l'utilisateur et lui fait perdre du temps, après quoi il s'énerve et (éventuellement) arrête d'utiliser le service. Pour résoudre ce problème, nous avons appris à prédire la probabilité qu'une voiture en commande soit trouvée.
Le schéma est le suivant:
- L'utilisateur met une épingle.
- Une recherche est effectuée sur le pin.
- S’il n’y a pas de voitures, nous prédisons : peut-être qu’elles apparaîtront.
- Et selon la probabilité, nous vous autorisons ou non à passer une commande, mais nous vous prévenons que la densité de voitures dans cette zone en ce moment est faible.
Dans l'application, cela ressemblait à ceci :
L'utilisation du modèle permet de créer de nouvelles commandes avec plus de précision et de ne pas rassurer les gens en vain. Autrement dit, réguler le rapport de fiabilité et le nombre de commandes sans machines en utilisant le modèle de rappel de précision. La fiabilité du service influence l’envie de continuer à utiliser le produit, c’est-à-dire qu’en fin de compte tout se résume au nombre de trajets.
Un peu sur le rappel de précisionL'une des tâches de base de l'apprentissage automatique est la tâche de classification : attribuer un objet à l'une des deux classes. Dans ce cas, le résultat de l'algorithme d'apprentissage automatique devient souvent une évaluation numérique de l'appartenance à l'une des classes, par exemple une évaluation de probabilité. Cependant, les actions effectuées sont généralement binaires : si la voiture est disponible, alors nous vous laisserons la commander, et sinon, nous ne le ferons pas. Pour être plus précis, appelons un algorithme qui produit une estimation numérique un modèle, et un classificateur une règle qui l'attribue à l'une des deux classes (1 ou –1). Pour créer un classificateur basé sur l'évaluation du modèle, vous devez sélectionner un seuil d'évaluation. La manière exacte dont cela dépend grandement de la tâche.
Supposons que nous effectuions un test (classificateur) pour une maladie rare et dangereuse. Sur la base des résultats des tests, soit nous envoyons le patient pour un examen plus détaillé, soit nous disons : « Bien, rentrez chez vous ». Pour nous, renvoyer une personne malade chez elle est bien pire que d’examiner inutilement une personne en bonne santé. Autrement dit, nous voulons que le test fonctionne pour autant de personnes vraiment malades que possible. Cette valeur est appelée rappel =. Un classificateur idéal a un rappel de 100 %. Une situation dégénérée est d'envoyer tout le monde pour un examen, alors le rappel sera également à 100 %.
Cela se produit également dans l'autre sens. Par exemple, nous créons un système de test pour les étudiants, doté d'un détecteur de tricherie. Si du coup le contrôle ne fonctionne pas dans certains cas de tricherie, alors c'est désagréable, mais pas critique. D’un autre côté, il est extrêmement mauvais d’accuser injustement les étudiants de quelque chose qu’ils n’ont pas fait. Autrement dit, il est important pour nous que parmi les réponses positives du classificateur, il y ait autant de réponses correctes que possible, peut-être au détriment de leur nombre. Cela signifie que vous devez maximiser la précision = . Si le déclenchement se produit sur tous les objets, alors la précision sera égale à la fréquence de la classe définie dans l'échantillon.
Si l'algorithme produit une valeur de probabilité numérique, alors en sélectionnant différents seuils, vous pouvez obtenir différentes valeurs de précision-rappel.
Dans notre problème, la situation est la suivante. Le rappel est le nombre de commandes que nous pouvons proposer, la précision est la fiabilité de ces commandes. Voici à quoi ressemble la courbe précision-rappel de notre modèle :
Il existe deux cas extrêmes : ne permettre à personne de commander et permettre à tout le monde de commander. Si vous n'autorisez personne, alors le rappel sera 0 : nous ne créons pas de commandes, mais aucune d'entre elles n'échouera. Si nous autorisons tout le monde, alors le rappel sera de 100 % (nous recevrons toutes les commandes possibles) et la précision sera de 29 %, soit 71 % des commandes seront mauvaises.
Nous avons utilisé différents paramètres du point de départ comme signes :
- Heure/lieu.
- État du système (nombre de machines occupées de tous tarifs et broches à proximité).
- Paramètres de recherche (rayon, nombre de candidats, restrictions).
En savoir plus sur les signes
Conceptuellement, nous souhaitons distinguer deux situations :
- « Forêt profonde » - il n'y a pas de voitures ici en ce moment.
- "Pas de chance" - il y a des voitures, mais lors de la recherche, il n'y en avait pas de convenable.
Un exemple de « malchanceux » est s’il y a beaucoup de demande dans le centre le vendredi soir. Il y a beaucoup de commandes, beaucoup de gens volontaires et pas assez de chauffeurs pour tout le monde. Cela peut se produire comme ceci : il n'y a pas de pilotes appropriés dans la broche. Mais littéralement en quelques secondes, ils apparaissent, car à l'heure actuelle, il y a beaucoup de conducteurs à cet endroit et leur statut change constamment.
Par conséquent, divers indicateurs du système à proximité du point A se sont révélés être de bonnes caractéristiques :
- Nombre total de voitures.
- Nombre de voitures en commande.
- Le nombre de voitures indisponibles à la commande en statut « Occupé ».
- Nombre d'utilisateurs.
Après tout, plus il y a de voitures, plus il est probable que l’une d’elles soit disponible.
En fait, il est important pour nous que non seulement les voitures soient localisées, mais que des voyages réussis soient également réalisés. Il était donc possible de prédire la probabilité d’un voyage réussi. Mais nous avons décidé de ne pas le faire, car cette valeur dépend fortement de l'utilisateur et du conducteur.
L'algorithme de formation du modèle a été . Les données obtenues lors de l'expérience ont été utilisées pour la formation. Après la mise en œuvre, des données de formation ont dû être collectées, permettant parfois à un petit nombre d'utilisateurs de commander contre la décision du modèle.
Les résultats de
Les résultats de l'expérience ont été ceux attendus : l'utilisation du modèle permet d'augmenter considérablement le nombre de voyages réussis grâce aux commandes sans voiture, mais sans compromettre la fiabilité.
À l'heure actuelle, le mécanisme a été lancé dans toutes les villes et tous les pays et, grâce à son aide, environ 1 % des voyages réussis ont lieu. De plus, dans certaines villes à faible densité de voitures, la part de ces déplacements atteint 15 %.
Autres articles sur la technologie des taxis
Source: habr.com