Хабрахабр

Как в Яндекс.Такси ищут машины, когда их нет

image

Пользователь не станет вдаваться в детали: ему важно, чтобы он нажал кнопку «Заказать» и как можно быстрее получил машину, которая доставит его из точки А в точку Б. Хороший сервис для заказа такси должен быть безопасным, надёжным и быстрым. Но если плашка «Нет машин» будет высвечиваться слишком часто, то логично, что человек просто перестанет пользоваться этим сервисом и уйдёт к конкуренту. Если рядом нет машин — сервис должен сразу об этом сообщить, чтобы у клиента не складывалось ложных ожиданий.

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

Предыстория

Чтобы вызвать такси, пользователь совершает несколько простых действий, а что при этом происходит во внутренностях сервиса?
Про ETA в пине, расчёт цены и выбор наиболее подходящего водителя мы уже писали. А это история о поиске водителей. Когда создаётся заказ, поиск происходит два раза: на пине и на заказе. Поиск на заказе проходит в два этапа: набор кандидатов и ранжирование. Сначала находятся свободные водители-кандидаты, ближайшие по дорожному графу. Потом применяются бонусы и фильтрации. Оставшиеся кандидаты ранжируются, и победителю приходит предложение заказа. Если он соглашается, то назначается на заказ и едет к точке подачи. Если отказывается, то предложение приходит следующему. Если кандидатов больше нет, то поиск запускается заново. Это продолжается не более трёх минут, после чего заказ отменяется — сгорает.

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

Вот что видел пользователь в приложении:

Поиск машин без машин

Однажды у нас появилась гипотеза: возможно, в некоторых случаях заказ всё же можно выполнить, даже если на пине не нашлось машин. Ведь между пином и заказом проходит какое-то время, а поиск на заказе более полный и иногда повторяется несколько раз: за это время свободные водители могут появиться. Ещё мы знали обратное: если водители нашлись на пине, то ещё не факт, что они найдутся при заказе. Порой они исчезают или все отказываются от заказа.

е. Чтобы проверить эту гипотезу, мы запустили эксперимент: перестали проверять наличие машин во время поиска на пине для тестовой группы пользователей, т. Результат получился довольно неожиданным: если машина не находилась на пине, то в 29% случаев она находилась позже — при поиске на заказе! Более того, заказы без машин не сильно отличались от обычных по частоте отмен, оценкам и прочим показателям качества. у них появилась возможность сделать «заказ без машин». Число заказов без машин составило 5% всех заказов, но чуть более 1% всех успешных поездок.

Чтобы понять, откуда берутся исполнители этих заказов, посмотрим на их статусы во время поиска на пине:

  • Свободен: был доступен, но по каким-то причинам не попал в кандидаты, например был слишком далеко;
  • На заказе: был занят, но успел освободиться или стать доступным для заказа по цепочке;
  • Занят: возможность принимать заказы была отключена, но потом водитель вернулся на линию;
  • Недоступен: водителя не было в сети, но он появился.

Добавим надёжности

Дополнительные заказы — это замечательно, однако 29% успешных поисков означают, что в 71% случаев пользователь долго ждал и в итоге никуда не уехал. Хотя с точки зрения эффективности системы в этом нет ничего ужасного, но на самом деле, пользователь получает ложную надежду и тратит время, после чего расстраивается и (возможно) перестаёт пользоваться сервисом. Чтобы решить эту проблему, мы научились предсказывать вероятность того, что машина на заказе будет найдена.

Схема такая:

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

В приложении это выглядело так:

То есть регулировать соотношение надёжности и числа заказов без машин с помощью precision-recall модели. Использование модели позволяет аккуратней создавать новые заказы, не обнадёживать человека напрасно. е. Надёжность сервиса влияет на желание и дальше пользоваться продуктом, т. в итоге всё сводится к числу поездок.

Немного про precision-recall

Одна из базовых задач в машинном обучении — задача классификации: отнести объект к одному из двух классов. При этом результатом работы алгоритма машинного обучения часто становится числовая оценка принадлежности к одному из классов, например оценка вероятности. Однако действия, которые совершаются, обычно бинарные: если машина будет — то даём заказать, а если нет — то нет. Для определённости назовём моделью алгоритм, который выдаёт числовую оценку, а классификатором — правило, которое относит к одному из двух классов (1 или –1). Чтобы на основе оценки модели сделать классификатор, нужно подобрать порог оценки. Как именно — сильно зависит от задачи.

По результатам теста мы или отправляем пациента на более подробное обследование, или говорим: «Здоров, иди домой». Предположим, мы делаем тест (классификатор) на какую-то редкую и опасную болезнь. То есть мы хотим, чтобы тест срабатывал для как можно большего количества реально больных людей. Для нас отправить домой больного человека гораздо хуже, чем зря обследовать здорового. У идеального классификатора recall равен 100%. Эта величина называется recall =$\frac{число\ всех\ больных}$. Вырожденная ситуация — отправлять на обследование всех, тогда recall тоже будет 100%.

Например, мы делаем тестирующую систему для студентов, и в ней есть детектор списывания. Бывает и наоборот. С другой стороны, крайне плохо незаслуженно обвинять студентов в том, чего они не совершали. Если вдруг на какие-то случаи списывания не сработает проверка, то это неприятно, но не критично. Значит, нужно максимизировать precision = $\frac{число\ верных\ срабатываний}{число\ всех\ срабатываний}$. То есть нам важно, чтобы среди положительных ответов классификатора было как можно больше правильных, возможно, в ущерб их количеству. Если срабатывания станут происходить на всех объектах, то precision будет равен частоте определяемого класса в выборке.

Если алгоритм выдаёт числовое значение вероятности, то, подбирая разные пороги, можно добиться разных значений precision-recall.

Recall — число заказов, которое мы можем предложить, precision — надёжность этих заказов. В нашей задаче ситуация следующая. Если не разрешать никому, то recall будет 0: мы не создаём заказов, но зато никакой из них не станет провальным. Вот так выглядит precision-recall кривая нашей модели:

Есть два крайних случая: не разрешать заказывать никому и разрешать заказывать всем. е. Если разрешать всем, то recall будет 100% (мы получим все возможные заказы), а precision — 29%, т. 71% заказов окажутся плохими.

В качестве признаков мы использовали различные параметры точки отправления:

  • Время/место.
  • Состояние системы (число занятых машин всех тарифов и пинов в окрестности).
  • Параметры поиска (радиус, число кандидатов, ограничения).

Подробнее о признаках

Концептуально мы хотим различить две ситуации:

  • «Глухой лес» — машин тут в это время не бывает.
  • «Не повезло» — машины есть, но вот при поиске подходящих не оказалось.

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

Поэтому хорошими фичами оказались различные показатели системы в окрестностях точки А:

  • Общее число машин.
  • Число машин на заказе.
  • Число недоступных для заказа машин в статусе «Занят».
  • Число пользователей.

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

Для обучения использовали данные, полученные из эксперимента. В качестве алгоритма обучения модели применяли CatBoost. После внедрения пришлось собирать обучающие данные, иногда позволяя небольшому числу пользователей делать заказ вопреки решению модели.

Итоги

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

Причём в некоторых городах с небольшой плотностью машин доля таких поездок доходит до 15%. На данный момент механизм запущен во всех городах и странах и с его помощью происходит около 1% успешных поездок.

Другие посты о технологиях Такси

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть