How does Yandex.Taxi search for the nearest driver?

Question

Yandex

How does Ya.Taxi search for the nearest driver? I think we need to take the coordinates from each driver through foreach, and use the API to see the distance between the driver and the point of departure. This is a good decision, but when will there be 10,000 drivers? How to proceed then? This will also be an excess of the quota for requests to the API, and such a cycle will take a lot of time. How are such problems solved?

Answer 1

The problem of finding the nearest driver belongs to the problems of finding the nearest neighbor . A simple foreach is a linear search, the simplest option and works in O(N), it can be solved faster (see link) - in O(log(N)).

Answer 2

At a minimum, the logic for searching for free drivers is not located on the client in the application. Therefore, there are no request overloads.
The logic is as follows:
1) The client sends a request for a trip, along with it, its geolocation is sent to the server
2) When the request arrives at the server, it queues for execution (or is immediately processed)
3) The current database of drivers is searched (where the their current coordinates)
4) The server sends a response to the client application that the order is accepted, the driver is found
And yes, all this miracle was done not in php and js: D
At least a python. And if you want to implement an open channel (when the server can send data to the client (I'm talking about the web)), look towards ratchet socketo.me

Answer 3

Firstly, you can weed out the drivers stupidly by the Euclidean distance (find all the drivers within the radius R).
further, Yandex has its own route building server (I could be wrong), or I used OSRM for such purposes. This service can calculate the distance from the order to the driver, taking into account the city's road network.
Well, then the closest one is selected, or somehow according to a different algorithm.
PS All actions take place on the server.

Answer 4

if you look from the side of applications that taxi drivers use:
applications (some. rutaxi has) taxi drivers have such a thing as a radius for receiving an order.
you can also take orders "in flight" - while you are fulfilling one order, another one will be thrown in the area where you complete the order.