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

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

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

Александр Аникин
Александр Аникин

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

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

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

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

Как вы думаете, какой процент времени водитель классической диспетчерской в среднем везет пассажира?
Какую долю смены везут пассажиров водители, принимающие заказы от «Яндекс.Такси»?

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

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

В простейшем варианте достаточно сделать элементарный алгоритм поиска ближайшего водителя. Тогда он меньше времени будет тратить на путь до клиента.

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

Сразу тройная экономия — время для водителя, время и цена для пассажира. Таких функций десятки, оценить эффект от каждой из них — сложная статистическая задача, ведь классические A/B-тесты невозможны в системах с сильным сетевым эффектом.

Александр Аникин, руководитель отдела эффективности платформы

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

Когда вы только открыли приложение

1. Сервис определяет, где вы находитесь

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

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

2. Из тысяч водителей города, которые сейчас свободны, алгоритм ищет ближайших, чтобы посчитать время ожидания

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

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

Маршрут такси и построение графа для этого же участка

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

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

Он поселился в 400 метрах от офиса, но дорога до дома на такси у него занимала 25 минут, потому что так был устроен дорожный граф в его районе на время ремонта.

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

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

Если бы у нас не было «Яндекс.Карт», «Навигатора» и собственного графа и мы вынуждены были бы использовать API сторонних картографических сервисов, то большинство даже самых простых данных нам стоили бы очень дорого, а некоторые вещи мы бы вообще не могли реализовать.

Александр Аникин

3. Приложение показывает на экране определённые специальным алгоритмом оптимальные точки посадки

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

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

Кластеризация точек посадки

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

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

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

4. При помощи машинного обучения «Яндекс.Такси» выбрал и подсказал наиболее вероятные точки назначения

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

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

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

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

Когда вы выбрали, куда ехать

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

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

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

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

Поиск оптимальной точки для начала маршрута

6. Вычисляется точная стоимость поездки

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

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

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

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

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

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

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

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

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

Утренний час пик — это такой период, когда сколько бы водителей ни было на линии, всё равно ощущается недостаток.

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

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

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

Москва живёт в режиме «целых часов». Никто не назначает встречу на 9:12 — обычно договариваются на 9:00. Поэтому за 15-20 минут до целых часов люди начинают заказывать такси, спрос резко повышается. В час пик перед началом рабочего дня это проявляется наиболее ярко.

Если вы хотите сэкономить утром по дороге на работу, то не нужно выезжать в 40 минут часа (например, в 8:40). Это самое пиковое время. Лучше заказать поездку пораньше, в 8:20, или чуть позже, в 9:10 — к этому времени много машин освобождается с заказов, по которым они развозили людей на работу к 9:00.

Когда нажимаете на кнопку «Вызвать»

7. Алгоритм выбирает среди ближайших водителей наиболее подходящего

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

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

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

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

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

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

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

Пока мы едем

8. Алгоритм оценивает корректность построенного маршрута

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

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

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

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

Как присоединиться к команде «Яндекс.Такси»

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

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

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

Описание задачи

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

Дом водителя находится в точке H. Пользователь заказывает поездку из точки A в точку B. Все попарные расстояния между точками известны. Предложите одно неравенство (формулу), которую можно было бы использовать для принятия решения — предлагать водителю такой заказ или нет.

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

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

129129
277 комментариев

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

94
Ответить

Ага... Значит для экономии времени Яндекс.такси дает заказы с адресом подачи за 3- 4 км? Ни в одном другом такси такого нет. Ни в ""Везет", ни в "Максиме".

Ответить

Забавно читать такую большую статью и понимать, что весь этот алгоритм пойдёт в пизду после звонка таксиста «дорогой, я туда не поеду, отмени заказ, пожалуйста»

41
Ответить

Штрафы за такое есть?

1
Ответить

И в убере и яндексе такие уроды! Только в убере с тебя еще в добавок спишут 50р за отмену заказа :)

Ответить

Два минуса за коммент от двух пиарщиков Яндекса:) А спросить что не так?

24
Ответить

Нормальные люди выведут Вам карму в плюс)) Спасибо за Punto ;)

4
Ответить