Пассажир может изменить маршрут, т.е. конечный пункт назначения. Это можно сделать до того, как водитель нажмет кнопку End Ride на устройстве.
Uber: Обзор главных алгоритмов управления платформой
Такие онлайн-платформы пассажирских перевозок, как Uber, DiDi и Yandex, только недавно появились на рынке, но быстро достигли внушительных размеров и, несмотря на свой молодой возраст, существенно изменили и дополнили систему городского транспорта. Технологии и теоретические модели, используемые (или разработанные) для этих платформ, сегодня являются активной областью исследований для широкого круга специалистов научного сообщества: экономистов, математиков, программистов и инженеров.
В этой статье мы (представляющие команду Uber Marketplace Optimisation) дадим краткое представление об основных рычагах, используемых для контроля эффективности онлайн-платформ: Алгоритмы, отвечающие за принятие диспетчерских решений (согласование), динамическое ценообразование и одна из новых концепций — динамическое время ожидания. Основываясь на реальном практическом опыте, мы покажем, что все три алгоритма играют важную роль в создании системы с высокой эффективностью и низким временем ожидания для пассажиров и водителей.
Описание представленных алгоритмов носит ознакомительный характер и намеренно лишено технической глубины и строгости. Заинтересованному читателю предлагается ознакомиться с оригинальной статьей (Dynamic Pricing and Matching in Ride-Hailing Platforms — N.Korolko, D.Woodard, C.Yan, H.Zhu — 2019), опубликованной исследователями Uber Marketplace, на которой основан этот краткий вводный обзор.
Описание главных алгоритмов
За последнее десятилетие отрасль транспортных решений быстро развивалась благодаря новым идеям и технологиям, таким как онлайн-платформы для перевозки пассажиров, разработка самодвижущихся автомобилей и электромобилей. Синергия этих технологий, над которыми одновременно работают многочисленные компании и лаборатории, обещает огромную революцию, которая позволит снизить удельную стоимость пассажирских перевозок в 10 раз в течение нескольких десятилетий.
Самым взрывным событием в этом списке технологий в настоящее время являются онлайн-платформы для пассажирских перевозок. Например, компания Uber за 10 лет своего существования обеспечила более 10 миллиардов поездок в более чем 80 странах и 700 городах мира. К 2030 году мировой рынок таких онлайн-перевозок достигнет ошеломляющей суммы в 285 миллиардов долларов. Поэтому неудивительно, что эффективность этих платформ, которые динамично управляют двусторонним рынком для пассажиров и водителей, имеет большое практическое значение.
Эмпирические исследования показывают, что онлайн-платформы могут более эффективно использовать рабочее время водителей и сократить время ожидания пассажиров по сравнению с традиционной службой такси благодаря автоматизированным алгоритмам обработки данных, планирования маршрутов, ценообразования и заказа. Более того, эти две ключевые характеристики системы (использование времени в пути и время ожидания пассажиров) тесно связаны с надежностью и устойчивостью услуги: внезапные локальные пики спроса (например, по окончании большого концерта или в канун Нового года) могут значительно ухудшить оба показателя, делая услугу непривлекательной для обеих сторон рынка. Это происходит потому, что водители на линии в районе повышенного спроса быстро занимают небольшой процент от общего числа рабочих мест, а водители из отдаленных районов занимают остальные. Это увеличивает время забора, которое обычно не вознаграждается водителю (тем самым уменьшая его заработок на единицу времени), и в то же время создает негативное впечатление у пассажира. Таким образом, обе стороны, использующие платформу, начинают меньше ее использовать. В результате оба показателя продолжают ухудшаться, что приводит к тенденции снижения производительности платформы и сводит эффективность к нулю. В англоязычной литературе это негативное явление называют Wild Goose Chase (WGC), что буквально означает «погоня за дикими гусями».
Двумя ключевыми технологиями для повышения устойчивости и производительности платформы являются алгоритмы распределения заказов и динамическое ценообразование. Первая технология контролирует принятие диспетчерских решений, а динамическое ценообразование балансирует сильно колеблющиеся спрос и предложение пассажиров в режиме реального времени. Динамическое ценообразование необходимо для поддержания работоспособности системы, сокращения времени ожидания транспорта и увеличения числа пассажиров в периоды высокого спроса. Более того, эмпирические и теоретические исследования показывают, что динамическое ценообразование может уменьшить патологическое явление WGC.
1 Алгоритмы распределения заказов (matching)
Простейшим диспетчерским алгоритмом для назначения водителя на заказ является так называемый первый диспетчерский протокол. Несмотря на простоту и хорошую практическую эффективность, можно легко продемонстрировать, что этот алгоритм неэффективен в большом количестве распространенных ситуаций. Во-первых, он выбирает только одного водителя из подмножества водителей, доступных на момент назначения, игнорируя водителей, которые могут быть близки к завершению поездки вблизи нового назначения Рис. 4. Во-вторых, этот простой алгоритм учитывает только информацию о системе в данный момент времени, в то время как большинство водителей, работающих в системе, не имеют доступа к информации о системе.
Другое популярное семейство алгоритмов диспетчеризации основано на идее объединения нескольких заданий на вождение в течение короткого промежутка времени и решении централизованной задачи оптимизации парных заданий. Другими словами, вместо того, чтобы напрямую и последовательно назначать автомобиль на каждый отдельный заказ, система собирает информацию о поступающих заказах и назначает накопленные заказы свободным водителям на линии через определенные промежутки времени. Если заказы остаются без водителей, они остаются в системе и участвуют в задаче распределения на следующем временном шаге. Объективная функция задачи оптимизации, решаемой на каждом шаге, может содержать широкий спектр метрик, описывающих качество генерируемых диспетчерских заказов: Время ожидания автомобиля пассажира, расстояние между заказом и назначенным водителем, вероятность отмены заказа пассажиром или водителем и т.д.
На практике алгоритмы диспетчеризации представляются гораздо более сложными, поскольку им приходится учитывать большое количество характеристик различных продуктов, одновременно отображаемых в интерфейсе приложения. Например, автомобили, зарегистрированные на одной платформе, могут иметь разные классы комфорта и разную грузоподъемность. На некоторых электронных платформах разные пассажиры могут пользоваться одним и тем же автомобилем одновременно (UberPool, Lyft Line), если их маршруты достаточно близки. Кроме того, решения по диспетчеризации часто должны учитывать предпочтения водителей в отношении районов работы и мест назначения поступающих заказов. Поэтому спектр оптимизационных задач, возникающих для повышения эффективности диспетчерских решений, которые также необходимо решать в режиме реального времени, постоянно расширяется и включает новые и более сложные формулировки.
