Александр Аникин руководит в «Яндекс.Такси» подразделением Marketplace efficiency. Приближённый перевод этого термина на русский язык — «эффективность платформы».
Для блога компании на vc.ru Аникин рассказал об алгоритмах, используемых в сервисе, задачах, которые решаются за доли секунды для каждого пользователя, и ключевых показателях, за которыми следит команда. Spot выбрал ключевые моменты:
Когда вы только открыли приложение
1. Сервис определяет, где вы находитесь
Система по геолокации ищет точку на карте, куда вы, скорее всего, хотите вызвать такси. Это не всегда просто, потому сам по себе сигнал GPS довольно шумный, и точная геолокация иногда определяется не сразу.
В районах с плотной застройкой, где сигналу спутников мешают высотки, иногда лучше подождать несколько секунд, чтобы местоположение определилось точнее и машина приехала к тому месту, где стоит человек.
2. Из тысяч водителей города, которые сейчас свободны, алгоритм ищет ближайших, чтобы посчитать время ожидания
Каждый раз, когда пользователь «Яндекс.Такси» открывает приложение, сервис запускает алгоритм поиска ближайших к нему водителей. При этом учитывается не линейное расстояние до автомобиля, а дистанция с точки зрения дорожного графа.
Граф — специализированная база данных, при помощи которой «Яндекс.Такси» строит все маршруты. Для этого используются все базовые функции «Яндекс.Навигатора» — умение строить маршрут в зависимости от количества и сложности манёвров, скорости перемещения по улицам, заездов со шлагбаумами, номеров подъездов и прочего. «Яндекс.Такси» также учитывает движение по полосам для общественного транспорта, по которым могут ехать таксисты.
Поэтому, например, такси, которое находится в 100 метрах от пассажира, но на соседней односторонней улице со сложной развязкой, не подойдёт для заказа, потому что водителю придётся потратить слишком много времени, чтобы объехать квартал. При этом машина, находящаяся в 500 метрах, но на той же улице, что и пассажир, больше подойдёт для заказа — она прибудет к месту посадки уже через две минуты.
После того как алгоритм выбрал машины, которые могли бы принять потенциальный заказ, он определяет среднее время, которое понадобится водителю, чтобы приехать к пассажиру — эти данные и отображается при запуске приложения.
3. Приложение показывает на экране определённые специальным алгоритмом оптимальные точки посадки
Параллельно с вычислением времени ожидания система загружает список оптимальных мест посадки. Такие точки помогают пассажиру и водителю быстрее найти друг друга там, где «опознать» нужную машину бывает трудно: например, вокруг больших торговых центров, на площадях, возле аэропортов, стадионов. Такие точки показываются в приложении синим цветом.
Иногда пассажира не устраивает предложенная системой точка посадки, и он двигает булавку на карте в другое место — например, из-за ремонта тротуара или если в том же ТЦ вдруг закрывают один из выходов. Такое поведение тут же становится известным машинному обучению, и «Яндекс.Такси» быстро убирает или, наоборот, добавляет новые точки на карту. Анализ актуальности происходит раз в сутки.
4. При помощи машинного обучения «Яндекс.Такси» выбрал и подсказал наиболее вероятные точки назначения
Чтобы пользователь мог быстрее перейти к поездке, «Яндекс.Такси» старается сэкономить время и уже на главном экране предлагает выбрать один из наиболее вероятных пунктов назначения, чтобы не пришлось вводить его вручную. Здесь тоже подключаются алгоритмы машинного обучения. Их KPI в этом случае — увеличить точность рекомендации, чтобы человек нашёл нужный адрес точки Б прямо на главном экране.
Чтобы сформировать рекомендацию, алгоритм анализирует все точки из истории поездок пользователя и начисляет для каждой из них баллы. Точка получает их, если в неё или из неё часто совершаются поездки. Больше всего баллов получают те точки, в которые пользователь ездил в это же время из того же места, где находится сейчас.
Когда вы выбрали, куда ехать
5. Строятся возможные маршруты до пункта назначения, чтобы выбрать оптимальный
Как только пользователь выбирает пункт назначения, алгоритмы «Яндекс.Такси» с использованием дорожного графа вычисляют несколько наиболее оптимальных маршрутов от точки посадки до точки назначения, чтобы выбрать самый лучший по нескольким параметрам, включая расстояние и время в пути.
Если алгоритм обнаружит, что можно сэкономить более четырёх минут на времени подачи или в пути — и, как следствие, уменьшить стоимость поездки, то предложит пассажиру воспользоваться альтернативной точкой посадки. Например, перейти дорогу, чтобы такси не пришлось делать разворот на магистрали.
6. Вычисляется точная стоимость поездки
Оптимальный маршрут определяется ещё и для того, чтобы вычислить стоимость поездки и показать её пользователю перед там, как он сделает заказ. При этом алгоритм должен вычислить её достаточно точно. Если сильно завысить стоимость, то можно потерять клиента. Если занизить — то оставить недовольным водителя.
При формировании стоимости алгоритм учитывает количество поворотов на маршруте, их сложность, среднюю скорость, наличие выделенных полос и многие другие факторы. Из-за этого стоимость поездки на разных сторонах улицы и даже на расстоянии нескольких метров может существенно отличаться — потому что водителю предстоит выполнить разное количество манёвров.
На стоимость поездки влияют и пробки, причём алгоритмы машинного обучения умеют учитывать не только текущие заторы, но и прогнозируемые на маршруте. Если нужно посчитать поездку, которая занимает 45 минут, при этом она начинается за 10 минут до часа пик и пройдёт по улицам, которые будут загружены, алгоритм посчитает её согласно прогнозу.
Пожалуй, главный фактор, влияющий на стоимость поездки — баланс спроса и предложения. В утренний час пик любой город испытывает нехватку водителей — желающих уехать существенно больше, чем машин, которые могут вывезти пассажиров. Здесь у сервисов возможны два поведения, объясняют в «Яндекс.Такси»: можно ничего не делать, но тогда доступные машины быстро закончатся, часть пассажиров просто не уедет и вызов такси превратится в лотерею.
Стоимость поездки из конкретной точки растёт минимальными шагами. Водители могут узнать о растущем спросе через приложение «Таксометр» — там карта города размечена на гексагоны площадью примерно 2 км², которые в реальном времени в зависимости от спроса окрашиваются в разные оттенки фиолетового цвета — от светлого до насыщенного.
Сервис вместе с таксопарками-партнёрами рассылает уведомления водителям, которые не вышли на линию, но при этом находятся в зоне повышенного спроса. В отдельных случаях — например, во время сильных снегопадов или чрезвычайных происшествий, «Яндекс.Такси» устраивает массовые рассылки — в том числе через SMS и по телефону.
Утренний час пик — это такой период, когда сколько бы водителей ни было на линии, всё равно ощущается недостаток.
Коэффициент рассчитывается в реальном времени, поэтому стоимость поездки может меняться несколько раз за секунду — просто потому, что так же быстро меняется количество доступных машин и интенсивность заказов в районе заказа.
Когда нажимаете на кнопку «Вызвать»
7. Алгоритм выбирает среди ближайших водителей наиболее подходящего
Алгоритм уже делал это при открытии приложения. Однако с тех пор прошло уже несколько десятков секунд — те водители, которые нашлись тогда, уже уехали из района или поменяли местоположение. Поэтому система начинает заново оценивать ситуацию — выбирать наиболее подходящих для поездки водителей. При этом очевидный вариант — предложить поездку ближайшему водителю — не всегда самый лучший.
Прежде всего система ориентируется на показатель ETA (estimated time of arrival), то есть тот самый расчётный показатель в минутах, за который водитель доедет до клиента. Но водителей с одинаковым ETA в моменте может быть несколько, поэтому система берёт в расчёт ещё несколько показателей — например, рейтинг водителя на основе отзывов и его долю принятия и выполнения заказов.
Затем система анализирует время получения последней GPS-координаты от водителей, чтобы оценить их достоверность. Если смартфон или планшет водителя присылал системе информацию о своём местоположении несколько секунд назад, то алгоритм понимает, что водитель сможет сразу отреагировать на предлагаемый заказ.
Если же система не получала координату от машины несколько минут, она поймёт, что возможно связаться с водителем будет сложнее — он может ехать в тоннеле или быть в районе с плохим покрытием связи.
Есть факторы, которые связаны с местонахождением машины. Допустим, у нас есть два водителя с одинаковым ETA и прочими показателями. Но один из них находится в зоне, где очень высокий спрос, а второй — там, где заказов сейчас почти нет. Очевидно, лучше отдать заказ второму водителю, чтобы «вывести» его из этого района. Он, конечно, может уехать из него и сам, но тогда увеличится холостой пробег, при прочих равных хочется этого избежать.
Когда заказ принят и водитель начинает ехать к клиенту, пользователь может следить по карте, где именно находится машина. Когда машина приезжает и водитель на своём планшете нажимает кнопку «В пути» — начинается отсчёт того самого полезного пробега, когда водитель везёт пассажира.
Пока мы едем
8. Алгоритм оценивает корректность построенного маршрута
Во время поездки алгоритм сравнивает построенный маршрут с реальным графом движения машины. Это нужно для того, чтобы оценивать эффективность маршрутизатора и выявлять проблемные участки дороги. Например, если все водители избегают поворота на улицу, которую рекомендует навигатор, то алгоритм понимает, что на участке есть какое-то ограничение. Это сигнал для алгоритма и для разработчиков — нужно выяснить, почему этот поворот нежелателен.
Поиск водителей, построение маршрута, вычисление стоимости и подбор оптимальных точек посадки — лишь самые основные этапы работы платформы «Яндекс.Такси». Сервис производит ещё около миллиона небольших расчётов, поправок и операций, которые проходят на каждом этапе.
За время, которое проходит от открытия приложения и определения водителя до момента, когда машина начинает двигаться к пользователю, «Яндекс.Такси» использует несколько «ручек» — интерфейсных связок с сервисами «Яндекса», например, с «Картами» и «Навигатором». При этом для того, чтобы приложение было отзывчивым и не тормозило, все вычисления и подключения должны отрабатываться в течение 300−400 мс.
