As Yandex.Taxi looking for cars when they are not

As Yandex.Taxi looking for cars when they are not


image

A good service for ordering a taxi should be safe, reliable and fast. The user will not go into details: it is important for him that he press the “Order” button and get a car as quickly as possible which takes him from point A to point B. If there are no cars nearby, the service should immediately inform about this so that the client does not evolved false expectations. But if the “No cars” plate is highlighted too often, then it’s logical that the person will simply stop using this service and go to a competitor.

In this article I want to talk about how with the help of machine learning we solved the problem of finding machines in a low-density area (in other words, where, at first glance, there are no cars). And what came of it.

Background


To call a taxi, the user performs several simple actions, and what happens in the guts of the service?
User Stage Backend Yandex.Taxi
Selects the point of departure Pin Run a simplified search for candidates - search on pin. Based on the drivers found, the arrival time is predicted - ETA at the pin. The increase factor is calculated at this point.
Select a destination, fare, requirements Offer Build a route and calculate prices for all tariffs, taking into account the increasing factor.
Press the "Call a Taxi" button Order Run a full search for the machine. We choose the most suitable driver and offer him an order.

About ETA pin , pricing and choosing the most suitable driver we already wrote. And this is a story about finding drivers. When an order is created, the search happens twice: on the pin and on the order. Search on the order takes place in two stages: a set of candidates and ranking. First, there are free drivers, candidates, coming on the road graph. Then bonuses and filtering are applied. The remaining candidates are ranked, and the winner receives an order proposal. If he agrees, he is appointed to order and travels to the point of filing. If he refuses, then the offer comes next. If there are no more candidates, the search is restarted. This lasts no more than three minutes, after which the order is canceled - burns.

A search on a pin is similar to a search on an order, only an order is not created and the search itself is performed only once. Simplified settings for the number of candidates and search radius are also used. Such simplifications are needed because there are an order of magnitude more pins than orders, and the search is a rather difficult operation. Key point for our story: if there were no suitable candidates during the preliminary search on the pin, we don’t allow making an order. At least, it was like this before.

Here is what the user saw in the application:



Search for cars without cars


Once we had a hypothesis: perhaps, in some cases, the order can still be completed, even if there were no cars on the pin. After all, some time passes between the pin and the order, and the search on the order is more complete and sometimes repeated several times: during this time, free drivers may appear. We also knew the opposite: if the drivers were found on the pin, it’s not a fact that they will be found when ordering. Sometimes they disappear or everyone refuses an order.

To test this hypothesis, we launched an experiment: we stopped checking the availability of machines during a pin search for a test group of users, i.e.they had the opportunity to make an “order without cars”. The result was rather unexpected: if the car was not on the pin, then in 29% of cases it was later - when searching on the order! Moreover, orders without cars were not much different from the usual frequency of cancellations, estimates and other quality indicators. The number of orders without cars amounted to 5% of all orders, but a little more than 1% of all successful trips.

To understand where the executors of these orders come from, let's look at their statuses during the search on the pin:



  • Free: was available, but for some reason did not get into the candidates, for example, was too far;
  • On order: was busy, but managed to free up or become available for order by chain ;
  • Busy: the ability to take orders was turned off, but then the driver returned to the line;
  • Unavailable: the driver was not online, but he appeared.

Add reliability


Additional orders are great, but 29% of successful searches mean that in 71% of cases the user waited a long time and eventually did not go anywhere. Although from the point of view of system efficiency, there is nothing terrible in this, but in fact, the user receives false hope and spends time, after which he becomes upset and (possibly) stops using the service. To solve this problem, we learned how to predict the probability that an order machine would be found.

The scheme is:

  • User puts a pin.
  • A pin search is in progress.
  • If there are no cars, we predict: maybe they will appear.
  • And depending on the probability of giving or not giving an order, but we warn that the density of cars in this area is small at this time.

In the application, it looked like this:



Using the model allows you to more accurately create new orders, not encouraging people in vain. That is, to adjust the ratio of reliability and the number of orders without cars using precision-recall model. Reliability of service affects the desire to continue to use the product, i.e. in the end, it all comes down to the number of trips.

A bit about precision-recall
One of the basic tasks in machine learning is the task of classification: to attribute an object to one of two classes. In this case, the result of the work of the machine learning algorithm often becomes a numerical estimate of belonging to one of the classes, for example, a probability estimate. However, the actions that are performed are usually binary: if the car is, then we give it to order, and if not, then not. For definiteness, let us call a model an algorithm that produces a numerical estimate, and a classifier is a rule that refers to one of two classes (1 or –1). In order to make a classifier on the basis of an assessment of a model, it is necessary to select an assessment threshold. How exactly - strongly depends on the task.

Suppose we do a test (classifier) ​​for some rare and dangerous disease. According to the test results, we either send the patient to a more detailed examination, or say: "Healthy, go home." For us, sending a sick person home is much worse than doing nothing to examine a healthy person. That is, we want the test to work for as many real sick people as possible. This value is called recall = $ \ frac {number \ defined \ classifier \ patients} {number \ all \ patients} $ . The ideal classifier recall is 100%. The degenerate situation is to send everyone to the survey, then the recall will also be 100%.

It happens and vice versa.For example, we make a testing system for students, and it has a cheating detector. If suddenly a check does not work for any cases of cheating, then it is unpleasant, but not critical. On the other hand, it is extremely bad to undeservingly blame students for what they did not do. That is, it is important for us that among the positive answers of the classifier there should be as many correct answers as possible, to the detriment of their number. So, you need to maximize precision = $ \ frac {number \ valid \ positives} {number \ all \ operations} $ . If the operations will occur on all objects, then precision will be equal to the frequency of the class being defined in the sample.

If the algorithm produces a numerical value of probability, then by selecting different thresholds, you can achieve different precision-recall values.

In our problem, the situation is as follows. Recall is the number of orders we can offer, precision is the reliability of these orders. Here is the precision-recall curve of our model:

There are two extreme cases: do not allow anyone to order and allow everyone to order. If you do not allow anyone, then recall will be 0: we do not create orders, but then none of them will fail. If you allow everything, then the recall will be 100% (we will receive all possible orders), and precision - 29%, i.e. 71% of orders will be bad.


As signs, we used various parameters of the departure point:

  • Time/place.
  • The state of the system (the number of used cars of all tariffs and pins in the neighborhood).
  • Search options (radius, number of candidates, restrictions).

More about features


Conceptually, we want to distinguish between two situations:

  • “Deaf Forest” - there are no cars here at this time.
  • "Not lucky" - there are cars, but when searching for suitable ones it wasn’t.

One example of "No luck" - if on Friday evening in the center of great demand. There are a lot of orders, there are many who want to, there are not enough drivers at all. It may happen this way: there are no suitable drivers in the pin. But literally in seconds they appear, because at this time there are a lot of drivers in this place and their status is constantly changing.

Therefore, various features of the system in the vicinity of point A proved to be good features:

  • Total number of cars.
  • The number of cars on order.
  • The number of machines that are unavailable for ordering is in busy status.
  • Number of users.

After all, the more around the cars, the more likely that one of them will be available.
In fact, it is important for us not only to find cars, but also to make successful trips. Therefore, it was possible to predict the likelihood of a successful trip. But they decided not to do so, because this value is highly dependent on the user and the driver.

The models used CatBoost as the learning algorithm. For training used the data obtained from the experiment. After implementation, it was necessary to collect training data, sometimes allowing a small number of users to place an order contrary to the decision of the model.

Results


The results of the experiment turned out to be expected: the use of the model allows to significantly increase the number of successful trips at the expense of orders without cars, but without sacrificing reliability.

At the moment, the mechanism is launched in all cities and countries and with its help about 1% of successful trips take place. And in some cities with a small density of cars, the share of such trips comes to 15%.

Other posts about Taxi technologies


Source text: As Yandex.Taxi looking for cars when they are not