Как Яндекс.Такси ищет ближайшего водителя?

Question

[cimajo]

Как Я.Такси ищет ближайшего водителя? Я думаю, надо через foreach взять у каждого водителя координаты, и через API посмотреть расстояние между водителем и точкой отправления. Это хорошое решение, но когда водителей будет 10000? Как поступать тогда? Это же будет превышение квоты на запросы к API да и такой цикл займет дофига времени. Как решаются такие проблемы?

Answer 1

[vasiliev]

Задача поиска ближайшего водителя относится к задачам поиска близжайшего соседа. Простой foreach - линейный поиск, самый простой вариант и работает за O(N), её можно решать быстрее (см. ссылку) - за O(log(N)).

Answer 2

[Макар Герасимов]

Как минимум, логика поиска свободных водителей не расположена у клиента в приложении. Поэтому никаких перегрузок по запросам нет.

Логика такая:
1) Клиент отсылает запрос на поездку, в месте с ним отсылается его геопозиция на сервер
2) По приходу запроса на сервер, становится в очередь на выполнение (или сразу же обрабатывается)
3) Происходит поиск по актуальной базе водителей (где расположены текущие их координаты)
4) Сервер отправляет ответ клиентскому приложению что заказ принят, водитель найден

И да, сделано все это чудо не на php и js :D
Как минимум питончик. А если хотите реализовать открытый канал (когда сервер может отсылать данные клиенту (я про веб)), смотрите в сторону ratchet socketo.me

Comments

[Артемий Лапко]

Что такого есть в питоне - чего нет в php (конкретно для этой задачи) ?!

Answer 3

[Сергей]

Во первых можно отсеять водителей тупо по Евклидовому расстоянию (найти всех водителей в радиусе R).
далее у яндекса есть собственный сервер построения маршрутов (могу ошибаться), ну или я использовал OSRM для таких целей. Данный сервис может подсчитать расстояние от заказа до водителя с учетом городской сети дорог.
ну и дальше выбирается наиближайший, или как-то по другому алгоритму.

P.S. Все действия происходят на сервере.

Answer 4

[timusKul]

если смотреть со стороны приложений, которые используют таксисты:
приложениях (некоторых. у rutaxi есть) у водителей такси есть такая вещь как радиус получения заказа.
так же можно брать заказы "влет" - пока выполняешь один заказ - накинут другой в районе где заканчиваешь выполнение заказа.