Как прогнозы и математическая оптимизация используются в логистике последней мили.

В DoorDash мы хотим, чтобы наши услуги были удобными ежедневно, предлагая своевременные поставки и стабильные цены. Достижение этих целей требует хорошего баланса между предложением Dashers (наш термин для обозначения драйверов доставки) и спросом на заказы.

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

Учитывая сложность предложения оплаты за пиковый спрос Dashers, мы создали новую систему мобилизации, которая распределяет стимулы перед любым ожидаемым дисбалансом спроса и предложения. При построении этой системы мы сосредоточили внимание на следующих вещах:

  • Четкое определение наших показателей измерения спроса и предложения и целей проекта
  • Составление точных прогнозов спроса и предложения
  • Настройка нового процесса оптимизации для распределения стимулов при ограничениях
  • Управление неопределенностью
  • Повышение надежности и ремонтопригодности системы

Как количественно оценить дисбаланс спроса и предложения?

Обрисовывая проблему дисбаланса спроса и предложения, полезно принять контекст всех затронутых сторон:

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

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

Напротив, баланс на уровне рынка означает, что на рынке имеется относительно равное количество Dashers и заказов, но не обязательно оптимальные условия для каждой из этих групп на уровне доставки. На практике уровень дисперсии спроса и предложения, обусловленный Dasher и предпочтениями потребителей, а также другими изменяющимися условиями окружающей среды, такими как движение транспорта и погода, затрудняет балансирование спроса и предложения на уровне доставки. Следовательно, мы сосредоточились на показателях рыночного уровня, чтобы определить состояние каждого рынка, даже несмотря на то, что показатель уровня поставки обеспечил бы более идеальный результат.

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

Чтобы понять, как эта метрика будет работать на практике, рассмотрим пример. Представим, что сейчас воскресенье, время обеда в Нью-Йорке, и, по нашим оценкам, для удовлетворения ожидаемого спроса необходимо 1000 часов водителя. Мы также можем подсчитать, что, если мы не предоставим дополнительные стимулы, только 800 часов, скорее всего, будут обеспечены органически. Без мобилизационных мероприятий нас бы недоставало примерно на 200 часов.

Обычно мы вычисляем эту метрику, когда Dashers регистрируются в Dash, и единицы времени, которые могут варьироваться от почасовой продолжительности до таких единиц времени, как обед и ужин. Очень важно не выбирать такой уровень агрегирования, который может привести к искусственному сглаживанию спроса и предложения. Например, в течение дня у нас может быть избыток на завтрак и недостаток на обед. Оптимизация на целый день приведет к сглаживанию любого дисбаланса и приведет к неправильным мобилизационным действиям.

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

Как мы прогнозируем спрос и предложение на локальном уровне?

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

Определение требований к прогнозированию

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

Поддержка многомерного прогнозирования

Многие одномерные подходы к прогнозированию плохо масштабируются, когда дело доходит до создания тысяч региональных прогнозов с низким уровнем детализации. Наш опыт убедительно подтверждает тезис о том, что некоторые из лучших моделей создаются в процессе быстрого прототипирования, поэтому мы искали подходы, позволяющие быстро перейти от гипотезы улучшения модели к получению конечного результата. LightGBM можно использовать для обучения и создания тысяч региональных прогнозов в рамках одного обучающего прогона, что позволяет нам очень быстро выполнять итерацию при разработке модели.

Поддержка экстраполяции

По мере того, как DoorDash расширяется как на национальном, так и на международном уровне, нам нужна наша система прогнозирования, чтобы иметь возможность формировать некоторые ожидания относительно того, как будет выглядеть рост нашего предложения и спроса в местах, где мы в настоящее время не предлагаем наши услуги. Например, если мы запускаемся в новом городе, мы все равно можем делать разумные прогнозы относительно траектории спроса и предложения даже без исторических данных. В этом случае особенно хорошо работают подходы, основанные на глубоком обучении и традиционном машинном обучении (ML), поскольку скрытую информацию, которая помогает при экстраполяции, можно получить либо с помощью встраивания векторов, либо с помощью хорошей разработки функций. Информация о численности населения, общих условиях движения, количестве доступных торговцев, климате и географии может быть использована для обоснования экстраполяции.

Поддержка опровержений

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

Небольшой размер зависимости

Мы хотели, чтобы система прогнозирования имела минимальный след зависимостей, а это означало, что мы не слишком полагались на множество сторонних библиотек. Это требование немедленно устранило множество подходов к автоматическому прогнозированию, при которых установка одной библиотеки часто означала установку более 100 дополнительных библиотек, или подходов, которые предоставляли унифицированные наборы инструментов и имели большое количество транзитивных зависимостей. Раздутый след создает проблемы совместимости, проблемы с обновлением и большую подверженность уязвимостям безопасности. LightGBM имеет очень небольшой размер зависимостей, и выполнять обновления относительно безболезненно.

Процветающее сообщество

Наконец, мы хотели положиться на экосистему с процветающим сообществом и сильной основной группой сопровождающих. Поддерживать библиотеку с открытым исходным кодом сложно. Библиотека может быть создана аспирантом или одним-тремя основными разработчиками, работающими в компании. Тем не менее, люди находят новые интересы, новую работу, меняют работу, находят новую карьеру или отказываются от нее. Отслеживание проблем и ошибок, связанных с библиотекой, часто не является приоритетом через несколько лет или месяцев. Это возможное отсутствие поддержки затем вынуждает пользователей создавать внутренние вилки, чтобы адаптировать инструменты прогнозирования для своих вариантов использования или участвовать в полном упражнении по ремоделированию. По этим причинам при выборе инструмента мы учитывали такие показатели, как циклы выпуска, количество звездочек и участие сообщества, чтобы гарантировать хорошее обслуживание сообщества в будущем.

Прогнозирование с помощью машинного обучения

Прогнозирование в контексте проблемы чистой регрессии может иметь свои проблемы, одна из которых связана с пониманием процесса генерации данных и причинно-следственной связи между входными и выходными данными. Например, на Рисунке 1 ниже показано, как наши стимулы соотносятся с увеличением количества часов Dasher.

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

Более вероятно, что в модели просто отсутствует смешивающая переменная. Например, в периоды, связанные с плохой погодой или праздниками, Дашеры хотят проводить время дома или со своими семьями. Мы с большей вероятностью увидим снижение доступности в это время, заставляя наши системы спроса и предложения предлагать более высокие стимулы для поддержания баланса на рынке.

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

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

Рассмотрим следующие три субрегиона, описывающие суточный спрос, путем составления выборок, как показано на рисунке 2 ниже, из нормального распределения со средним значением 100 и стандартным отклонением 25, что дает нам коэффициент вариации 25%. Когда мы объединяем эти регионы, мы просто суммируем ожидаемое среднее значение, чтобы получить ожидаемый совокупный спрос, равный 300. Тем не менее, комбинированное стандартное отклонение равно не сумме стандартных отклонений, а сумме дисперсий.

, что дает нам коэффициент вариации комбинированного прогноза 14,4%. Путем простого агрегирования случайных величин мы смогли уменьшить дисперсию по отношению к среднему более чем на 40%.

Выбор оптимизатора

Одним из преимуществ использования алгоритмов машинного обучения является то, что они обеспечивают более точные ожидания того, что произойдет, с учетом входных данных. Тем не менее, алгоритмы машинного обучения часто являются просто строительным блоком в более крупной системе, которая использует прогнозы и пытается сгенерировать набор оптимальных действий. Решения, основанные на смешанном целочисленном программировании (MIP) или обучении с подкреплением (RL), отлично подходят для создания систем, ориентированных на максимизацию вознаграждения при определенных бизнес-ограничениях.

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

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

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

Работа с неопределенностью

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

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

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

Чтобы решить проблему дисперсии, мы генерируем ожидаемые оценки разрыва в часах на основе прогнозов, используя процесс повторной выборки. Выполняя повторную выборку, мы, по сути, измеряем влияние недостаточного предложения в контексте вероятности того, что это произойдет. Например, на Рисунке 3 выше вероятность того, что у города B будет недостаточное предложение, составляет всего 34%. Однако, если это произойдет, мы сможем более точно оценить влияние значительных изменений дефицита предложения. Любой из этих подходов приводит к более оптимальному решению в распределении стимулов вместо простого использования средних оценок из исходных данных прогнозирования.

Повышение надежности и ремонтопригодности

DoorDash значительно вырос за последний год. Более 70% людей в DoorDash присоединились в период с 2020 по 21 год. Это, как правило, привело к появлению новых проектов, связанных с разработкой, продуктами, платформами и инфраструктурой, которые способствовали постоянному росту, расширению и масштабируемости. Например, у нас были десятки внутренних проектов, связанных с разрушением нашего монолита и принятием архитектуры, более ориентированной на микросервисы. У нас были сотни мелких и крупных проектов, связанных с улучшением продукта или новым вертикальным запуском. Многие из этих проектов были связаны с изменениями в наших моделях данных и в наших процессах создания и сбора данных. К сожалению, модели машинного обучения могут быть ужасно ненадежными, когда экосистема того, как создаются и публикуются данные, постоянно меняется, поэтому нам нужно было внести некоторые изменения, чтобы повысить надежность нашей системы.

Разделение цепочек зависимостей данных

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

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

Второе, что мы сделали, - это удалили зависимости промежуточных данных. Мы осознали, что если наши входные сигналы поступают от заданий ETL с очень длинными цепочками зависимостей в их направленных ациклических графах (DAG), мы увеличим нашу поверхность для сбоев. Следовательно, мы стремимся полагаться на первичные таблицы, тщательно проверенные нашей командой Business Intelligence, или на копии производственных источников данных, для которых генерация данных не скрыта за сложными ETL.

Сосредоточьтесь на экспериментах

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

Точно так же, если система остается неизменной в течение длительного периода времени (например, шести месяцев или более), это также может указывать на то, что что-то не так, потому что это означает, что мы создали систему, которая является жесткой и не требует улучшений, идей. , и эксперименты. Непрерывное экспериментирование - это функция, побуждающая к принятию лучших практик, таких как использование системы CI / CD для автоматизации, настройка управления зависимостями библиотек, разделение кода на бизнес-области и добавление тестирования, предупреждений и документации.

Полученные результаты

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

Заключение

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

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

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

Благодарности

Большое спасибо Джареду Бауману и Дэну Мэдведу за помощь в мозговом штурме архитектуры новой системы, Гэри Рену за руководство через сложность инженерных компонентов спроса и предложения, Генри Ляо за оптимизацию экспериментов, а также Мэтью Ферро и Юджина Брауде за стремление к усилению автоматизации. .

Чтобы найти исходную версию этого сообщения, загляните в блог DoorDash Engineering.