1. Введение
Онлайн-платформы пассажироперевозок, такие как Uber, DiDi и Yandex возникли достаточно недавно, при этом они быстро достигли внушительных размеров и, несмотря на свой небольшой возраст, существенно видоизменили и дополнили систему городского транспорта. Технологии и теоретические модели, используемые этими платформами (или разрабатываемые для них), на данный момент являются областью активных исследований для широкого спектра специалистов научного сообщества: экономистов, математиков, программистов и инженеров.
В этой статье мы (как представители команды Uber Marketplace Optimization) коротко представим взгляд изнутри на главные рычаги управления эффективностью онлайн-платформ: алгоритмы, отвечающие за диспетчерские решения (matching), динамическое ценообразование (dynamic pricing), а также представим одну из новых концепций — динамическое время назначения автомобиля (dynamic waiting). Основываясь на реальном практическом опыте, мы покажем, что все три алгоритма играют важную роль для создания системы с высокой производительностью и низким временем ожидания заказов как для пассажиров, так и для водителей.
Представленное описание алгоритмов будет носить ознакомительных характер и намеренно лишено технической глубины и строгости. Заинтересовавшийся читатель приглашается изучить оригинал статьи (Dynamic Pricing and Matching in Ride-Hailing Platforms — N.Korolko, D.Woodard, C.Yan, H.Zhu — 2019), опубликованной исследователями из отдела Uber Marketplace, по мотивам которой этот краткий ознакомительный обзор и создан.
2. Описание главных алгоритмов
За последнее десятилетие индустрия транспортных решений развивается стремительными темпами благодаря новым концептуальным идеям и технологиям, таким как онлайн-платформы пассажироперевозок, разработка самоуправляемых автомобилей и автомобилей с электродвигателем. Синергия этих технологий, над которой одновременно работают многие компании и лаборатории, обещает огромный прорыв в снижении удельной стоимости пассажироперевозок не много не мало в 10 раз на дистанции в пару десятилетий.
Наиболее взрывной рост из этого списка технологий на данный момент демонстрируют онлайн-платформы пассажироперевозок. Например, компания Uber за 10 лет своего существования сгенерировала более 10 миллиардов поездок в более чем 80 странах и 700 городах по всему миру [Figure 1]. Мировой рынок таких онлайн перевозок обещает достигнуть невероятного размера в 285 миллиардов долларов к 2030 году. Поэтому неудивительно, что эффективность таких платформ, динамически контролирующих двухсторонний рынок пассажиров и водителей, имеет огромное практическое значение.
Эмпирические исследования показывают, что автоматизированные алгоритмы обработки данных, маршрутизации, ценообразования и назначения заказов позволяют онлайн-платформам добиться более высокой утилизации рабочего времени водителей и менее длительного ожидания автомобиля пассажирами по сравнению с классическим сервисом такси. Причем две эти ключевые характеристики системы (утилизация времени водителей и время ожидания пассажиром) тесно связаны с надежностью и устойчивостью сервиса: внезапные локальные вспышки спроса (например, по завершении крупного концерта или в канун Нового Года) могут существенно ухудшить обе метрики, делая тем самым использование сервиса малопривлекательным для обеих сторон рынка. Это происходит из-за того, что находящиеся на линии в зоне высокого спроса водители быстро получают малую часть общего числа заказов, а на оставшуюся часть заказов назначаются водители из удаленных районов. Это увеличивает время подачи автомобиля, которое чаще всего не оплачивается водителю (а значит уменьшает его заработок в единицу времени), и одновременно формирует негативное впечатление у пассажира. Таким образом обе стороны, использующие платформу, начинают меньше ее использовать. Из-за этого обе метрики начинают ухудшаться еще больше, тем самым закручивая нисходящую спираль производительности платформы в направлении нулевой эффективности. В англоязычной литературе этот негативный феномен называется Wild Goose Chase (WGC), дословный перевод которого — “преследование дикого гуся”.
Две ключевые технологии, направленные на повышение устойчивости и производительности платформы — это алгоритмы распределения заказов и динамического ценообразования. Первая технология контролирует диспетчерские решения, а динамическое ценообразование в режиме реального времени балансирует крайне волатильное соотношение спроса и предложения на пассажироперевозки. Динамическое ценообразование критически необходимо для поддержания работоспособности системы, снижения времени ожидания подачи автомобиля и повышения количества водителей в периоды высокого спроса. Более того, эмпирические и теоретические исследования показывают, что динамическое ценообразование позволяет уменьшить масштабы патологически опасного эффекта WGC.
2.1 Алгоритмы распределения заказов (matching)
Простейшим диспетчерским алгоритмом назначения водителя на заказ является так называемый протокол назначения ближайшего водителя (first-dispatch protocol). Несмотря на свою простоту и неплохие практические показатели эффективности, легко показать, что данный алгоритм является малоэффективным в большом количестве часто возникающих ситуаций. Во-первых, он выбирает водителя только из той подгруппы водителей, которые свободны в момент заказа, игнорируя тех водителей, которые могут быть близки к завершению поездки в непосредственной близости от нового заказа [Figure 4]. Во-вторых, этот простой алгоритм учитывает только информацию о системе в данный период времени, в то время как чаще всего платформе может быть доступна достаточно точная информация о том, что произойдет с потоком заказов и пространственным распределением водителей в ближайшем будущем. В литературе класс похожих задач, дающих практические рецепты как такая информация может быть использована для улучшения качества алгоритма, носит название “проблема K серверов” (The K-server problem).
Другое популярное семейство диспетчерских алгоритмов основано на идее объединения группы заказов на поездки в рамках небольшого временного интервала и решения агрегированной оптимизационной задачи о попарном назначении. Другими словами, вместо моментального и последовательного назначения автомобиля на каждый индивидуальный заказ, система собирает информацию о поступающих заказах и с некоторой периодичностью распределяет накопившиеся заказы между имеющимися на линии водителями. Если какие-то заказы остаются без назначенного водителя, то они остаются в системе и участвуют в задаче распределения следующего временного шага. Целевая функция оптимизационной задачи, решаемой на каждом шаге, может включать в себя широкий спектр метрик, характеризующих качество генерируемых диспетчерских назначений: время ожидания автомобиля пассажиром, расстояние между заказом и назначенным водителем, вероятность отмены заказа пассажиром или водителем, итд.
На практике диспетчерские алгоритмы выглядят намного сложнее, так как они должны учитывать большое количество особенностей разных продуктов, одновременно представленных в интерфейсе приложения. Например, автомобили, зарегистрированные на платформе, могут быть разных классов комфорта и разной вместимости. Некоторые продукты онлайн-платформ подразумевают одновременное использование одного автомобиля разными пассажирами (UberPool, Lyft Line), в том случае если их маршруты оказываются достаточно близки. Более того, диспетчерские решения часто должны учитывать предпочтения водителей по зонам обслуживания и направлениям поступающих им заказов. Таким образом, спектр возникающих оптимизационных задач, направленных на повышение эффективности диспетчерских решений, которые к тому же необходимо решать в режиме реального времени, непрерывно пополняется новыми все более сложными формулировками.
2.2 Алгоритмы динамического ценообразования (Dynamic pricing)
Одной из главных операционных сложностей управления онлайн-платформой пассажироперевозок является непрерывно меняющиеся в пространстве и времени объемы спроса и предложения на услуги такси. На рисунке ниже [Figure 5] изображено отношение количества онлайн-запросов на поездки со стороны пассажиров и количества часов, которое водители провели на линии, для двух районов Сан-Франциско: финансового центра и спального района Сансет на окраине города. Данный график хорошо иллюстрирует высокую волатильность и отсутствие баланса между спросом и предложением (соотношение которых иногда может принимать крайне высокие значения), а также разнообразие поведения этого баланса в зависимости от географической локации.
Для того, чтобы контролировать баланс спроса и предложения в пространстве и времени, онлайн-платформы используют алгоритмы динамического ценообразования, которые в режиме реального времени повышают базовый тариф, если количество поступающих со стороны пассажиров заказов существенно превышает количество свободных водителей. Польза от динамического ценообразования для поддержания стабильной работы платформы подтверждается большим количеством теоретических моделей, экспериментов и эмпирических наблюдений, связанных с рекордно высокими нагрузками на систему. Такие нагрузки могут случаться из-за большого количества предсказуемых и не очень причин: неблагоприятные погодные условия, массовые мероприятия, неисправная работа системы общественного транспорта, итд. В случае некорректной работы алгоритма ценообразования, при резком увеличении количества запросов со стороны пассажиров (или при резком снижении количества доступных автомобилей) можно наблюдать очень низкую долю пассажиров, к которым в итоге назначается автомобиль и неудовлетворительно высокое время его подачи. Ключевая роль динамического ценообразования для онлайн-платформы — это дать возможность любому пользователю в любом месте и в любой момент времени вызвать такси. Даже если предложенный тариф будет выше обычного, это будет более благоприятным вариантом, чем поставить пользователя платформы (которому срочно может быть нужна машина) в известность, что в данный момент доступных машин нет в наличии.
Популярные методы моделирования динамического ценообразования включают в себя экономические модели, описывающие стационарное состояние системы (steady-state models), модели динамического программирования, регрессионный анализ, а также оптимизационные модели, описывающие сетевые эффекты (network optimization). Недавние исследования экономистов (Castillo, 2017) показали, что динамическое повышение тарифа также позволяет платформе избежать попадания в зону негативного эффекта WGC, о котором мы говорили выше.
У динамического ценообразования есть и объективные недостатки. Во-первых, финальная цена на поездку, которую пассажиры видят при заказе такси, может существенно варьироваться из-за волатильности спроса и предложения, тем самым повышая непредсказуемость тарифа на одном и том же маршруте. С другой стороны, водители онлайн-платформ часто имеют доступ к информации в приложении о тех районах города, где активен повышающий коэффициент. Однако, из-за высокой волатильности этого коэффициента к тому времени как водитель переместится в зону более высоких цен, тариф может вернуться к базовым значениям. Более того, автоматическое повышение тарифа алгоритмом может побуждать водителей кооперироваться и искусственно создавать на локальном рынке ситуации нехватки автомобилей, доступных для заказа, тем самым активируя повышающие коэффициенты на поездки. Безусловно, такое скоординированное поведение водителей несложно обнаружить для платформ, обрабатывающих большое количество данных о заказах, и принять необходимые защитные действия, однако для пассажиров такой опыт искусственно завышенных цен может оказаться неудовлетворительным.
2.3 Динамическое время назначения автомобиля (Dynamic waiting)
Чтобы избежать проблем, связанных с динамическим ценообразованием, на практике применяются и другие алгоритмы, позволяющие сбалансировать спрос и предложение, а также избежать попадания системы в зону эффекта WGC. К ним относится идея ограничения максимального расстояния между заказом и назначаемым водителем (Maximum Dispatch Radius), а также формирование очереди заказов на поездки (queueing), поступающих в систему, заменяющее моментальное назначение водителя на каждый заказ.
Более новой концепцией, направленной на замену или дополнение динамического повышения цен, является механизм динамического контроля времени ожидания до назначения автомобиля (dynamic waiting). Один из вариантов этого механизма используется в продукте Express Pool, недавно запущенном компанией Uber на некоторых крупных рынках. Данный вид пассажироперевозок отличается максимально низким тарифами и подразумевает одновременное использование одного автомобиля несколькими независимыми пассажирами для совершения попутных поездок.
Общая идея механизма динамического времени назначения состоит в следующем. Для пассажира, заказывающего поездку, приложение не назначает водителя моментально, а предлагает подождать, но не более чем некоторое наперед обозначенное количество времени (типичные верхние границы составляют 2 или 5 минут). Причем назначение водителя может произойти в любой момент, удобный для платформы: от моментального до указанной верхней границы. В данном случае суммарное время ожидания автомобиля пассажиром состоит из двух (почти независимых) частей: время до назначения водителя и время от его назначения до прибытия на место заказа. Доставленное пассажиру неудобство ожидания компенсируется более низким тарифом.
Со стороны платформы дополнительная степень свободы со временем назначения водителей на заказы используется следующим образом. Так как продукт подразумевает комбинирование заказов и назначение одного автомобиля на одновременную перевозку нескольких пассажиров, то дополнительное время на сбор информации позволяет увеличить количество комбинаторных вариантов и в результате сгенерировать более эффективные поездки. В этом случае метрикой эффективности может являться, к примеру, близость маршрутов пассажиров, попадающих в один автомобиль. Очевидно, что как только платформа находит достаточно высокоэффективную комбинацию поездки, она тут же делает необходимое назначение водителя и оповещает всех ее участников. Если же удачная и удобная комбинация не найдена, то платформа направляет индивидуального водителя каждому из сделавших заказ пассажиров.
Описанный механизм в первую очередь оптимизирует диспетчерские решения и время, когда эти решения принимаются, причем он может быть использован одновременно с динамической оптимизацией цен. Теоретическая модель, разработанная и проанализированная в оригинале основной статьи, демонстрирует, что одновременная оптимизация цен и времени имеет большое количество преимуществ: она позволяет снизить волатильность тарифов, снизить риски эффекта WGC, а также увеличить общее количество поездок, генерируемых платформой в единицу времени. Более того, данные варианты перевозок являются экономически более выгодным как для водителей (которые одновременно получают несколько пассажиров, оплачивающих поездку), так и для пассажиров (которые получают скидку в обмен на гибкость со временем ожидания).
3. Заключение
В этой статье мы кратко описали основные оптимизационные задачи управления, которые решают онлайн-платформы пассажироперевозок для обеспечения стабильной работы и повышения своей эффективности. К таким задачам относятся построение диспетчерских алгоритмов, алгоритмов динамического ценообразования и динамического определения времени назначения водителя. Одновременное управление данными рычагами позволяет добиться высоких показателей утилизации времени водителей, низкого времени ожидания автомобиля и количества поездок, генерируемых платформой, в единицу времени. Класс указанных задач постоянно пополняется новыми, все более реалистичными примерами, открывая широкие горизонты для теоретических и практических исследований.
Все ссылки на цитируемые источники могут быть найдены в оригинале статьи (Dynamic Pricing and Matching in Ride-Hailing Platforms — N.Korolko, D.Woodard, C.Yan, H.Zhu — 2019).