Hi-Tech

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

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

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

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

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

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

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

Как вы думаете, какой процент времени водитель классической диспетчерской в среднем везет пассажира?

Меньше 10%

Больше 60%

Остальное — ожидание заказа или путь к клиенту ?. Всего лишь 10-15% времени.

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

Меньше 10%

Больше 60%

Современным платформам удалось значительно повысить эффективность — у них этот показатель составляет 60% и выше.

(function($) ); $.addClass(el, 'selected'); $.css(message, 'display', 'block'); message.textContent = (isCorrect ? 'Да. ' : 'Нет. ') + message.textContent; }); }); })(AirInterface.$);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пока мы едем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Показать больше

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

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

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

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