Всем привет, меня зовут Алексей Чубуков. Я аналитик из команды поиска и назначений водителей в Яндекс Такси. В нашей команде мы оптимизируем алгоритмы, которые помогают находить водителей на заказы оптимальным способом, чтобы пользователи быстрее получали машины, а водители бóльшую долю времени проводили с пассажирами. 

В статье я расскажу про виртуальную очередь заказов, которую мы сделали в приложении Яндекс Go. Напомню кратко, как устроен поиск водителей в Такси, поговорим про предпосылки внедрения очереди, посмотрим на то, как устроена очередь и, наконец, обсудим результаты. 

Как устроен поиск водителей в Яндекс Такси

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

Базовый алгоритм назначения водителей в Яндекс Такси — буферный диспатч. Чтобы он работал максимально эффективно, мы накапливаем (буферизуем) заказы и не делаем назначения моментально. То есть чтобы найти оптимального исполнителя после того, как пользователь нажимает кнопку заказа, происходит следующее:

• мы собираем все активные заказы вокруг пользователя; 

• далее собираем всех доступных для заказа исполнителей; 

• помещаем водителей и пользователей на дорожный граф (структура, в которой каждый участок дороги представляет собой ребро графа с заданным расстоянием, временем проезда и прочими характеристиками). 

Далее между подходящими парами «заказ — водитель» мы рассчитываем время и расстояние от водителя до заказа по дорожному графу. Крайне важно считать время и расстояние не просто по прямой, а по дорогам, учитывая актуальную дорожную ситуацию: пробки, перекрытия и так далее. Таким образом, у нас получается связь между водителем и заказом с рассчитанным временем и расстоянием, которое требуется проехать водителю.

Далее все такие пары можем представить в виде двудольного графа, одно множество которого будет состоять из заказов, а другое — из водителей. Каждая связь между водителем и заказом в таком графе означает, что этот водитель может рассматриваться на данный заказ. Не все водители подходят на заказы: например, на заказы с детским креслом нельзя рассматривать водителя, у которого этого кресла нет.

Вес ребра в таком графе представляет собой некоторую функцию f(time,distance), где time и distance — соответственно, время, которое требуется водителю на преодоление расстояния до точки определённого заказа.

Над этим графом удобно ввести задачу оптимизации. Мы хотим максимизировать паросочетания минимального веса, а решаем эту задачу при помощи венгерского алгоритма. 

Предыстория — зачем понадобилась очередь заказов

Теперь экскурс в историю: почему же нам вообще понадобилась очередь заказов. Чтобы лучше понять проблему, давайте представим следующий пример. Вы с друзьями решили сходить на концерт любимой группы, который проводится на крупном стадионе в вашем городе, и выбрали самый простой способ добраться до стадиона — на такси. Концерт проходит отлично, звучит заключительная песня, после которой вы понимаете, что пора ехать домой, но есть нюанс: об этом же в данный момент думают и несколько сотен, а то и тысяч людей рядом с вами.

Что происходит дальше? Все начинают заказывать такси, но в окрестности стадиона нет нескольких сотен машин, которые прямо сейчас могут удовлетворить кратно растущий спрос. Мы ищем машину 10 секунд, 1 минуту, 3 минуты. Назначение фактически превращается в случайность: выигрывает тот, рядом с кем раньше освободится водитель.

Мы хотим обеспечивать пользователям надёжный и стабильный сервис независимо от ситуации в городе. Поэтому стараемся делать продукт таким, чтобы дать пользователю максимум информации о том, как и на чём лучше добраться из точки А в точку Б.

Налицо проблема: в ситуациях острого дисбаланса спроса и предложения наш сервис не показывает закулисья для клиента полностью. Из‑за нехватки обратной связи пользователи:

• испытывают дискомфорт от того, что не понимают, что происходит и сколько ещё ждать; 

• начинают делать мультизаказы (то есть один пользователь делает несколько заказов одновременно в надежде, что хоть на какой‑то заказ мы найдём водителя);

• отменяют заказы и делают перезаказы (причём часто перезаказ приходится делать по более высокой цене, так как за то время, пока они искали водителя, цена могла вырасти — заказы выросли, дисбаланс со свободными водителями рядом увеличился и к цене сработал повышающий коэффициент). 

Мультизаказы и перезаказы растят нагрузку на наши микросервисы, а «боль» про пользовательский дискомфорт мы разделяем сами, так как попадали в такие ситуации и знаем, насколько это неприятно.

Чтобы лучше понимать, насколько сильно могут отличаться спрос и предложение, давайте посмотрим на картинку: 

В центре Санкт‑Петербурга возникло очень много заказов, которые сейчас мы не можем обработать. Чтобы лучше справляться с такими моментами, мы и сделали виртуальную очередь заказов.

Как работает очередь заказов для пользователя

В пиковые моменты спроса, например концерты, массовые мероприятия или дождь, в тарифе «Эконом» Яндекс Go включается виртуальная очередь. Сейчас очередь работает только в этом тарифе, в повышенных или специальных тарифах (детский, тариф для людей с ограниченными возможностями) очереди нет. 

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

Более подробный пользовательский флоу со скриншотами:

Таким образом очередь решает проблему мультизаказов или перезаказов. Конечно, пользователь всё ещё может сделать повторный заказ, но в таком случае встанет в конец очереди. 

Как устроена очередь заказов изнутри

Очередь заказов включается, когда спрос кратно превышает предложение, а, соответственно, нам как‑то надо отслеживать такие ситуации. У нас есть повышающий коэффициент (мы его называем «сурж»), но иногда он недостаточно чётко отражает ситуацию в отдельных районах. 

Поэтому мы сделали сервис, который используется в периоды экстремально высокого спроса — чтобы сделать процесс более прозрачным, сгладить ценовые колебания и показать, что происходит с заказами в реальном времени.

Под капотом сервис использует шардированный Redis Cluster для хранения геопространственного индекса заказов. Пара (зона, тариф) задаёт отдельный индекс и используется как хештег для шардирования. Заказ добавляется в свой индекс при создании и удаляется оттуда после его отмены или назначения на него исполнителя. Рядом с индексами с тем же хештегом хранится и дополнительная информация по заказам: время создания и позиция в очереди. Данные о заказе и его окружении читаются и обновляются в lua‑скриптах, запускаемых на соответствующем шарде кластера.

Так мы можем, например, добавить заказ в индекс и сразу же просчитать его позицию. Конфигурация удобна в использовании, тем более что буферное назначение, которому сервис предоставляет информацию о позиции заказа в очереди, тоже происходит по зонам. 

Но у неё есть и минус: зон у нас всего несколько сотен, и они могут сильно отличаться по размеру, а значит, шарды кластера неизбежно оказываются нагружены неравномерно. С этим мы в итоге были готовы мириться, и в нашем кластере разница между шардами по количеству ключей может достигать 30%.

Таким образом, в момент, когда пользователь ставит точку А заказа, мы можем для точки А получить информацию о текущих заказах в окрестности точки А и сколько времени мы уже пытаемся найти на них водителей.

Время поиска у соседних заказов — довольно важная фича:

• Если заказов много, но они быстро получают водителей, — очереди не будет. В такой ситуации много спроса, но и предложения в виде водителей хватает — очередь не нужна.

• Если заказов много и значительная часть никак не может получить своего исполнителя — это сигнал, что в данный момент нам может не хватать исполнителей. Возможно, в такие моменты сработает очередь.

• Если же заказов много, но какой‑то один заказ уже несколько минут не может найти своего водителя, то в такой ситуации очередь не нужна. Скорее всего, дело в особенностях этого заказа.

Таким образом, порог включения очереди определяется двумя факторами:

1. В радиусе X от точки алгоритм считает количество активных заказов по тарифу «Эконом». 

2. Алгоритм учитывает, сколько времени эти заказы уже ждут назначения. 

Как очередь заказов встроена в назначения

Как мы уже обсудили выше, в механизм назначения водителя у нас входит двудольный граф, а весом ребёр для каждой пары «заказ — водитель» служит некоторая функция f(time,distance), которая зависит от времени и расстояния. Но на самом деле ничего не мешает нам изменить вес данного ребра, добавив в него третью составляющую f(time,distance)+bonus.

Вес ребра — это не просто время/расстояние по графу, которое требуется водителю, но и какая‑то наша бизнес‑логика, так как составляющую bonus мы можем задавать, как захотим. Именно так мы и формируем виртуальную очередь.

В моменты, когда очереди нет, нет и составляющей bonus — водители назначаются как обычно. Если же по ответу сервиса мы поняли, что в сервисе образовалась очередь, то мы добавляем составляющую bonus в систему (по сути бонус за номер в очереди).

Таким образом, мы начинаем приоритизировать водителей на заказы, которые были сделаны раньше и стоят в начале очереди. Чем раньше пользователь вошёл в очередь, тем больший бонус он получит и тем раньше ему назначится водитель. Для водителей же ничего не меняется.

Чтобы понять истинный эффект виртуальной очереди, мы провели поюзерный A/B‑эксперимент.

Валидация новой функциональности

Завершающий этап любого внедрения — проверить, как пользователи реагируют на изменения. С очередью заказов было так же: мы хотели выяснить, насколько понятно, что это за инструмент, и действительно ли виртуальная очередь делает работу удобнее.

Как и большинство изменений в Яндекс Go, мы раскатывали виртуальную очередь через A/B‑эксперимент, в котором поделили пользователей на две группы:

• В контроле для пользователей в продукте ничего не менялось.

• В тестовой группе пользователи начинали видеть виртуальную очередь.

Сразу скажу, что в этом эксперименте мы хотели проверить реакцию пользователей на продукт, а не влияние виртуальной очереди на назначения (это было проверено раньше в отдельном эксперименте). Именно поэтому в контрольной и тестовой группах для обоих вариантов на бэкенде формировалась виртуальная очередь (да, даже в контроле), а единственным отличием между группами был исключительно интерфейс в продукте.

Что мы увидели в эксперименте:

• Пользователи стали по‑другому распределяться между тарифами, из‑за чего выросла «вывозимость» заказов. Так как стало больше заказов в тех тарифных классах, в которых водителей в данный момент хватает. 

• Счётчик номера в очереди на поиске даёт пользователям обратную связь, как скоро мы можем назначить водителя, из‑за чего пользователи стали меньше отменять заказы. 

Так что можно считать, что продукт справлялся с функцией объяснения виртуальной очереди: пользователи стали понимать, каковы их шансы получить машину в момент сверхвысокого ажиотажа.

Какие плюсы приносит очередь заказов

Очередь заказов даёт немало преимуществ: 

• Она включается довольно редко, но в такие моменты пользователи могут быстрее принимать решение, какой транспорт и тариф им выбрать. 

• В очереди на протяжении всего времени поиска водителя за пользователем фиксируется стоимость поездки.

• Продукт стал более понятным, теперь пользователи получают обратную связь на экране поиска и видят, сколько человек перед ними ждут своё такси.

Мы понимаем, что номер в очереди мало что говорит пользователю и клиенты хотят знать, сколько времени займёт ожидание. На первый взгляд может показаться, что задача предсказания времени поиска не такая сложная, но это не так. Ведь нам нужно с хорошей точностью предсказать время ожидания в ситуациях, когда спрос кратно превышает предложение. Мы любим сложные и интересные задачи и уже работаем над тем, чтобы сделать экран поиска ещё более понятным:) 

Заключение

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

Да, полностью убрать дисбаланс спроса и предложения невозможно — мероприятия и погодные условия всё равно будут создавать всплески. Но мы можем сделать так, чтобы в эти моменты пользователи понимали, что происходит, и могли принять наилучшее для себя решение.