Новости такси
Чтобы понять принципы работы системы, нужно разобраться с тем, что собой представляет непосредственно Яндекс Такси. Рассматриваемый сервис является агрегатором такси, т. е. он через программное обеспечение и другие инструменты объединяет в единую систему водителей и таксопарки.
С противоположной стороны, через возможность заказа машин, к этой программной системе получают доступ пассажиры.
Система строится на двух приложения:
– Яндекс Про (Таксометр) — для водителей
– Яндекс GO — для клиентов.
Как из вышесказанного можно охарактеризовать суть работы Яндекс Такси?
– Сервис выступает посредником между водителями такси (таксопарками) и пассажирами.
– Посредничество выражается в поддержании и развитии программного обеспечения — приложений для таксопарков, водителей и пассажиров.
– Все сервисные приложения объединены в единую систему.
Как работать в Яндекс такси
– Интеграция всех ПО в единую сеть позволяет принимать заявку от пассажира, обрабатывать его данные и распределять доступным водителям через использование специальных алгоритмов.
– За доступ к системе распределения заказа водители и таксопарки отчисляют Яндексу определённую комиссию с каждой прошедшей через систему заявки пассажира. Пассажиры получают доступ к сервису бесплатно.
– Сервис для привлечения в систему максимального количества пользователей (таксопарков, водителей и пассажиров) берёт на себя вопросы развития бренда, рекламы, отладки и совершенствования рабочих механизмов и процессов, обучения водителей и персонала таксопарков.
Теперь вы понимаете Как устроена система “Яндекс Такси”!
Источник: voditelvtaxi.ru
Как мы распределяем заказы между водителями в Яндекс.Такси
Одна из главных задач в Яндекс.Такси — как сделать так, чтобы к пользователю быстро приезжала машина, а у водителя сокращалось время «холостого пробега» (то есть время, когда он на линии без пассажира). Казалось бы, всё просто: пользователь выбирает тариф, указывает дополнительные пожелания (детское кресло, например). Остаётся отфильтровать водителей на линии по этим критериям, выбрать ближайшего и предложить ему заказ. Однако всё так просто только на первый взгляд.
Сегодня я расскажу сообществу Хабра о том, как мы выбираем наиболее подходящего водителя и как этот процесс эволюционировал со временем. Вы узнаете о двух подходах к решению задачи.
Общая архитектура поиска
Когда пользователь нажимает кнопку «Вызвать такси», в бэкенде создаётся объект заказа и начинается его обработка в соответствии с конечным автоматом. Чтобы заказ перешёл из состояния «В ожидании» в «Водитель назначен» — нужно найти водителя, предложить ему заказ и дождаться подтверждения, что заказ принят.
Подработка в ЯНДЕКС такси (инструкция для новичков)
Жадный (Greedy) подход
Очень долго в Яндекс.Такси работал жадный подход. При таком подходе на этапе поиска исполнителя делается запрос в микросервис Tracker, отвечающий за водителей. Tracker знает об автомобилях всё: от цвета и брендирования до текущего местоположения.
В Tracker’e есть локальный геоиндекс по водителям и коннекторы к сервисам маршрутизации (роутерам) для построения маршрутов от точки А до точки Б (и даже через точки В, Г, Д). Поэтому, когда поступает запрос на поиск водителя, Tracker сначала определяет в локальном геоиндексе ближайшие машины по прямому радиусу с учётом «жёстких» ограничений заказа (класс автомобиля, требования — детское кресло, жёлтые номера). Затем уточняется время и длина маршрута подачи автомобиля и с учётом этой информации выбирается лучший вариант.
Позже эта логика эволюционировала: для каждого водителя стали рассчитывать его «скоринг» на заказ — функцию от времени подачи автомобиля. И ранжировали водителей уже по значению скоринга. В функции учитывается не только непосредственно время подачи, но и множество других факторов: от уровня спроса в точках А и Б до «опытности» водителя. Такое жадное назначение называется бонусным.
Буферный (балковый) подход
Однако при жадном подходе ближайшего водителя получит тот, кто первый заказал такси. При этом некоторые пользователи могут вообще остаться без машины.
При повышенном спросе, когда начинается конкуренция за исполнителей, жадный подход не годится. Чтобы максимально удовлетворить спрос даже в самые нагруженные часы, мы используем множество подходов и алгоритмов. Один из них — буферное (балковое) назначение водителей на заказы. В его основе лежит хорошо известная задача из области комбинаторной оптимизации — задача о назначениях. Вкратце её суть: пусть у нас есть N работ и M исполнителей, любой работник может выполнить любую задачу за время p(i,j)[0
При решении такой задачи о назначениях наша «стоимость» выполнения работы (заказа) исполнителем (таксопарком и водителем) — значение функции скоринга от времени подачи автомобиля к пользователю. Задачу можно описать в терминах двудольных графов: с одной стороны — заказы, с другой — исполнители. Между заказами и исполнителями есть взвешенные рёбра (скоринг). Таким образом, одна из наших целей — минимизировать суммарное время подачи автомобилей, максимизировав количество выполненных заказов (максимальное паросочетание). Один из наиболее известных способов решить такую задачу — венгерский алгоритм.
 |
 |
Очевидно, что при буферном назначении мы не можем дать водителя по запросу, как при жадном подходе. Сначала нужно положить заказ в очередь, потом разыграть, а после этого сообщить о найденном водителе. Это совсем не вписывалось в конечный автомат обработки заказа, и его пришлось немного усовершенствовать. Чтобы тестировать и создавать новое решение, не влияя на коллег, мы сразу договорились, что всё будем делать в отдельном микросервисе DriverDispatcher. Он станет принимать заказы, класть к себе в очередь, находить водителей и сохранять результаты розыгрышей.
Первым делом нам надо было подготовить Tracker к новому профилю нагрузки. Если при жадном подходе запросы на водителей просто индивидуально попадали на балансировщик Tracker’a и перенаправлялись на его инстансы с распределением нагрузки, то в буферном назначении все запросы были с одной машины: индивидуальные запросы просто забили бы пул соединений. Поэтому мы добавили в трекер возможность батчевой обработки запросов, которые внутри трекера обрабатывались параллельно. Попутно нам также пришлось решить проблему разумного количества запросов на батч-обработку. Со стороны клиента (DriverDispatcher’a) мы разбивали большой батч на несколько маленьких и отправляли на разные инстансы Tracker’a.
Итак, трекер подготовлен, скоринг считается и в Tracker’e (жадное назначение), и в новом сервисе (DriverDispatcher’e), алгоритм решения задачи о назначениях отлажен и корректно работает. Появился вопрос, как интегрировать это всё в конечный автомат обработки заказа. Мы добавили отправку и удаление метаинформации о заказе в DriverDispatcher при переходе заказа из состояния в состояние.
И это уже почти работало. Почти — потому что итерации поиска исполнителя на заказ не контролировались извне. Мы могли просто заменить поход в трекер за водителем на поход в наш сервис и отдавать водителя, когда он найден, а до этого просто отдавать 404.
Но это плохо, потому что нужно предлагать заказ водителю сразу, как только мы нашли заказ, и даже несколько секунд задержки тут играют роль: водитель может просто повернуть не в ту сторону, и заказ станет неактуален. Для этого мы сделали возможность вызвать процесс поиска исполнителя, не влияя на запланированные задачи. Так мы сохранили логику поиска (с перезапросами) и добавили возможность вызвать его вне планировщика.
Таким образом нам удалось совместить основной конечный автомат обработки заказа с конечным автоматом обработки в буферном диспатче без влияния на работающую логику и без гонок между состояниями. Можно запускать первые эксперименты на живых пользователях.
Это всё очень здорово, но как же время поиска исполнителя, спросите вы. Если поиск происходит не сразу после поступления заказа, значит, время поиска увеличивается и в итоге компенсируется более быстрой подачей? Это не совсем так: с помощью различных методик (в т.ч. с помощью машинного обучения), мы смогли выделить кейсы, когда ожидание имеет смысл, в остальных же случаях время ожидания не меняется.
Розыгрыш на пине
Ещё один способ найти исполнителя быстрее — начать искать его ДО создания заказа. Когда появляется новый пин (то есть пользователь только вводит данные о заказе в приложение), алгоритмы машинного обучения оценивают вероятность того, что далее последует заказ, и решают, учитывать ли его при буферном поиске водителей. Мы можем найти машину заранее, а когда пользователь нажмёт кнопку заказа — тут же сделать предложение подходящему водителю.
Матчинг заказов и водителей — непростая задача, она требует учитывать множество факторов. Один из них — это контекст перемещений водителей при выборе кандидатов на заказ. Об этом мы расскажем в следующих постах.
Другие посты о технологиях Такси
- Динамическое ценообразование, или Как Яндекс.Такси прогнозирует высокий спрос
- Как с помощью компьютерного зрения оценить состояние автомобиля. Опыт Яндекс.Такси
- Как Яндекс.Такси прогнозирует время подачи автомобиля с помощью машинного обучения
Источник: habr.com
Как устроена программа яндекс такси
В блоге компании на vc.ru рассказали об алгоритмах, используемых в сервисе, задачах, которые решаются за доли секунды для каждого пользователя, и ключевых показателях, за которыми следит команда. Spot выбрал ключевые моменты.
Александр Аникин руководит в «Яндекс.Такси» подразделением 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 мс.
Источник: www.spot.uz