Распределение заказов между водителями в Яндекс.Такси

Среди важных задач в Яндекс.Такси это постараться сделать так чтобы к пользователям максимально быстро приезжал автомобиля, при этом у водителей уменьшалось время «холостого пробега». Кажется что все очень просто, пользователь должен выбрать подходящий тариф и указывает пожелания. В итоге нужно будет отфильтровать водителей, которые находятся на линии, найти ближайшего и предложить выполнить заказ. Только это все обеспечить не легко. Кстати, если вы ищите в Яндекс Такси вакансии всегда есть.

Архитектура поиска

Сразу же, как пользователь нажмет на кнопку «Вызвать такси», в бэкенде появляется объект заказа и он начинается обрабатываться, учитывая конечный автомат. С целью заказ получил состояние «Водитель назначен» придется найти подходящего водителя и предложить ему заказ, после этого необходимо времени, чтобы дождать подтверждения что заказ принят.

Жадный подход

В Яндекс.Такси длительное время работал жадный подход. Точнее во время поиска исполнителя запрос поступал в микросервис Tracker, который отвечал за водителя. Tracker зал совершенно все об автомобилях, начиная от цвета и завершая его местоположением. В Tracker’e присутствует локальный геоиндекс как по водителям, так и по коннекторам к сервисам маршрутизации, чтобы выстраивать маршруты. Соответственно когда приходил запрос на поиск водителя данная система изначально устанавливала в локальном геоиндексе самые ближайшие автомобили, по прямому радиусу учитывая ограничения заказа. После этого необходимо было уточнять время и длину маршрута, чтобы поддать автомобиля, отталкиваясь от данной информации, вы сможете выбрать самый подходящий вариант.
Но спустя время данная логика эволюционировала, точнее для каждого водителя начали успешно рассчитывать «скоринг» на заказ, точнее эта функция времени подачи автомобиля. Дальше водителей ранжировали по значению скоринга. Предусматривалось не только время подачи, но и ряд других факторов, начиная от спроса и завершая опытом водителей. Столь жадное назначение принято называть бонусным.
При таком подходе ближайшего водителя мог получить тот человек, который успел первым заказать такси.