Под капотом «Яндекс.Такси»

Что происходит за секунды между открытием приложения и отправлением машины к точке посадки.

Александр Аникин руководит подразделением Marketplace efficiency. Приближённый перевод этого термина на русский язык — «эффективность платформы». Для блога компании на vc.ru Аникин рассказал об алгоритмах, используемых в сервисе, задачах, которые решаются за доли секунды для каждого пользователя, и ключевых показателях, за которыми следит команда.

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

Первый — доля времени за смену, когда водитель везёт пассажира. Это так называемое время «чистого» заработка. Когда водитель ждёт заказ, едет к клиенту или ожидает его — это неэффективное время, и задача платформы «Яндекс.Такси» свести его к минимуму.

Второй ключевой показатель — это заработок водителя за час смены. При этом речь идёт не про средний чек, а именно про заработок в час. Этот показатель важнее, потому что в какой-то момент система может предложить водителю «дешёвый» заказ, но таким образом он попадёт в зону высокого спроса, и следующим заказом будет «дорогой».

Или, например, сервис с помощью недорогого заказа «приведёт» водителя туда, где его вызовет следующий пользователь, направляющийся в аэропорт — это одни из самых выгодных заказов в системе.

Очевидно, что идеальный показатель — 100%, при которых водитель всегда везёт пассажира и зарабатывает деньги. Однако это теория — в реальном мире достичь его невозможно.

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

Система по геолокации ищет точку на карте, куда вы, скорее всего, хотите вызвать такси. Это не всегда просто, потому сам по себе сигнал GPS довольно шумный, и точная геолокация иногда определяется не сразу.

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

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

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

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

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

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

Для их поиска «Яндекс.Такси» анализирует все исторические данные о том, где реально начинаются поездки — то есть точки, в которых водитель открывает заказ, а не только точки, куда пользователи обычно вызывают такси. Для этого используется алгоритм кластеризации, который удаляет те точки, которые находятся не на дороге — такое случается из-за погрешности GPS, — а затем вычисляет центр масс — среднее значение координат всех входящих в группу точек.

Иногда пассажира не устраивает предложенная системой точка посадки, и он двигает булавку на карте в другое место — например, из-за ремонта тротуара или если в том же ТЦ вдруг закрывают один из выходов. Такое поведение тут же становится известным машинному обучению, и «Яндекс.Такси» быстро убирает или, наоборот, добавляет новые точки на карту. Анализ актуальности происходит раз в сутки.

Данные о запланированных перекрытиях «Яндекс.Такси» получает от разных источников — от официальных сообщений местных властей до публикаций в СМИ.

Чтобы пользователь мог быстрее перейти к поездке, «Яндекс.Такси» старается сэкономить время и уже на главном экране предлагает выбрать один из наиболее вероятных пунктов назначения, чтобы не пришлось вводить его вручную. Здесь тоже подключаются алгоритмы машинного обучения. Их KPI в этом случае — увеличить точность рекомендации, чтобы человек нашёл нужный адрес точки Б прямо на главном экране.

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

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

Алгоритм учитывает и город, в котором находится пользователь. В Москве он получает московские рекомендации. Как только он прилетит в Сочи, то они изменятся на местные.

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

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

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

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

При формировании стоимости алгоритм учитывает количество поворотов на маршруте, их сложность, среднюю скорость, наличие выделенных полос и многие другие факторы. Из-за этого стоимость поездки на разных сторонах улицы и даже на расстоянии нескольких метров может существенно отличаться — потому что водителю предстоит выполнить разное количество манёвров.

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

Пожалуй, главный фактор, влияющий на стоимость поездки — баланс спроса и предложения. В утренний час пик любой город испытывает нехватку водителей — желающих уехать существенно больше, чем машин, которые могут вывезти пассажиров. Здесь у сервисов возможны два поведения, объясняют в «Яндекс.Такси»: можно ничего не делать, но тогда доступные машины быстро закончатся, часть пассажиров просто не уедет и вызов такси превратится в лотерею.

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

Стоимость поездки из конкретной точки растёт минимальными шагами. Водители могут узнать о растущем спросе через приложение «Таксометр» — в нём карта города размечена на гексагоны площадью примерно 2 км², которые в реальном времени в зависимости от спроса окрашиваются в разные оттенки фиолетового цвета — от светлого до насыщенного.

Сервис вместе с таксопарками-партнёрами рассылает уведомления водителям, которые не вышли на линию, но при этом находятся в зоне повышенного спроса. В отдельных случаях — например, во время сильных снегопадов или чрезвычайных происшествий, «Яндекс.Такси» устраивает массовые рассылки — в том числе через SMS и по телефону.

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

Повышенный спрос в первую очередь отражается на тарифе «Эконом» — самом популярном в «Яндекс.Такси». В пиковые моменты стоимость поездки в «Экономе» может превысить стоимость «Комфорта». Однако разница в цене вскоре быстро сокращается из-за того, что больше пользователей начинает заказывать «Комфорт» вместо «Эконома».

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

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

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

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

Прежде всего система ориентируется на показатель ETA (estimated time of arrival), то есть тот самый расчётный показатель в минутах, за который водитель доедет до клиента. Но водителей с одинаковым ETA в моменте может быть несколько, поэтому система берёт в расчёт ещё несколько показателей — например, рейтинг водителя на основе отзывов и его долю принятия и выполнения заказов.

Затем система анализирует время получения последней GPS-координаты от водителей, чтобы оценить их достоверность. Если смартфон или планшет водителя присылал системе информацию о своём местоположении несколько секунд назад, то алгоритм понимает, что водитель сможет сразу отреагировать на предлагаемый заказ.

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

Дополнительно учитывается, в каком направлении движется машина, и прогнозирует её доступность. Например, планшет прислал координату 15 секунд назад, а водителю приходит предложение заказа, на которое он может отреагировать в течение 15 секунд. За эти 30 секунд водитель, двигаясь по скоростной магистрали (например, ЗСД в Петербурге или МКАД), мог уже проехать нужный поворот и перестать быть «ближайшим» к пользователю.

Когда заказ принят и водитель начинает ехать к клиенту, пользователь может следить по карте, где именно находится машина. Когда машина приезжает и водитель на своём планшете нажимает кнопку «В пути» — начинается отсчёт того самого полезного пробега, когда водитель везёт пассажира.

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

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

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

За время, которое проходит от открытия приложения и определения водителя до момента, когда машина начинает двигаться к пользователю, «Яндекс.Такси» использует несколько «ручек» — интерфейсных связок с сервисами «Яндекса», например, с «Картами» и «Навигатором». При этом для того, чтобы приложение было отзывчивым и не тормозило, все вычисления и подключения должны отрабатываться в течение 300-400 мс.

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

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

Присылайте свои идеи на cv_taxi@yandex-team.ru и получите возможность получить приглашение сразу на второй тур собеседования в отдел эффективности платформы «Яндекс.Такси».

Открытые вакансии в «Яндекс.Такси»:

#яндекстакси #транспорт