Электронная коммерция сильно повлияла на то, как мы покупаем товары и услуги. Это может быть связано с различными факторами, такими как — удобная доставка заказа на дом в нужное время (например, 10:00–10:30), возможность просмотра и поиска в огромном каталоге товаров. в несколько кликов, скидки, распродажи и т. д. и т. д.. В этой статье мы даем общий обзор процесса доставки и того, как мы используем машинное обучение для лучшей оценки времени доставки клиенту (CDT). CDT влияет на окончательный план доставки, который должны выполнить наши сотрудники, и тесно связан с качеством обслуживания клиентов и нашим бизнесом.

Прогнозирование времени доставки уже давно является частью городской логистики, но в последнее время точность уточнения стала очень важной для таких сервисов, как Deliveroo, Foodpanda и Uber Eats, которые доставляют еду по требованию.

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

Доставка «последней мили» — это последний шаг в типичной цепочке поставок, когда посылка (заказ, посылка и т. д. и т. д.) доставляется по нужному адресу клиента из магазина, склада или любого объекта. Системы доставки «последней мили» очень сложны для ритейлера, поскольку нам нужно обслуживать разных клиентов, разбросанных по районам, где доступно выполнение (доставка на дом). Кроме того, нам нужно иметь возможность выполнять различные заказы в определенные временные интервалы.

Это также имеет решающее значение для бизнеса, поскольку есть большая вероятность понести значительные убытки, если выполнение доставки на последней миле будет неоптимальным. Недостаточное использование или перегрузка физически ограниченных частей системы (например, принятие новых заказов, которые не помещаются в транспортное средство доставки, потому что оно почти заполнено, или консервативное резервирование пространства и времени, что приводит к плохому занятое транспортное средство доставки) — это два простых сценария возникновения убытков в логистике «последней мили». Это может привести к увеличению цен на товары или стоимости доставки для клиентов. Такой клиентский опыт может нанести ущерб доходам и коэффициенту удержания клиентов. Кроме того, мы также хотим уловить тенденцию, когда маршруты могут быть затронуты такими сценариями, как COVID, что имеет решающее значение для выполнения операций.

Чтобы избежать этих проблем, многие операторы доставки имеют систему оптимизации последней мили, которая решает версию задачи ограниченного маршрута транспортного средства с временными окнами (CVRP-TW), которая является хорошо изученной темой в сообществе исследований операций и компьютерных наук. Это NP-сложная задача комбинаторной оптимизации, что означает, что найти точное решение для нее не менее сложно, чем в случае недетерминированной задачи с полиномиальным временем. Схема проблемы представлена ​​ниже

Источник:

Существует несколько методов решения CVRP-TW, близких к оптимальности. Однако всем этим методам требуется своего рода матрица расстояния/времени, которая показывает общее расчетное время доставки между каждой точкой (отправной точкой) и любой другой точкой (назначением), указанной в задаче. Допустим, есть 100 заказов, которые вы хотите выполнить в магазине, матрица расстояния/времени имеет размер 101 * 101. Мы можем уменьшить ее до половины размера, получив треугольную матрицу, если предположим, что дорожная сеть симметрична, т.е. упрощая предположение, однако. Учитывая эту матрицу расстояний вместе с другими входными данными, алгоритм оптимизации пытается максимизировать целевую функцию, которая может быть как простой, как минимизация общего времени или расстояния в пути, так и очень сложной, включающей другие аспекты бизнес-показателей, такие как доступность слотов, обещание слотов, удовлетворенность клиентов и т. д. при соблюдении ограничений. В промышленных условиях существует множество ограничений и буферов, которые необходимо учитывать, чтобы обеспечить бесперебойную работу. Алгоритм оптимизации пытается итеративно оптимизировать решение проблемы CVRP-TW и выводит решение в удобочитаемом формате, известном как план доставки. План доставки состоит из множества деталей для руководителей операций и сотрудников по доставке, чтобы иметь возможность выполнять процесс выполнения последовательно в течение дня наиболее оптимальным образом.

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

Что такое время доставки клиенту (CDT)?

Его можно определить как время, необходимое сотруднику службы доставки для доставки заказа покупателю без учета времени в пути или запланированных перерывов. Проще говоря, для доставки заказа мы можем определить общее время доставки (TDT) как сумму времени в пути (DT) и времени доставки клиенту (CDT) и любого времени перерыва (BT).

TDT = DT + CDT + BT

Поскольку CDT является значительной частью TDT, которая является входом для алгоритма оптимизации, результирующее решение и план доставки сильно зависят от него. Нам необходимо учитывать CDT, чтобы обеспечить бесперебойную работу, хорошее удовлетворение клиентов и своевременную доставку, особенно для продуктовых заказов, содержащих скоропортящиеся продукты. Например, сотруднику службы доставки может быть нелегко найти парковку рядом с местом нахождения клиента — отсутствие уличной парковки в многолюдных городских районах, невозможность найти дом клиента (дом может быть закрыт) и т. д.. В других сценариях клиент мог заказать много товаров, требующих, чтобы сотрудник по доставке выполнил заказ в несколько этапов. Недооценка CDT может утомить сотрудника службы доставки, поскольку у него меньше времени на выполнение заказа и последующих. Завышение CDT приведет к неэффективному использованию рабочего времени и плохим метрикам слота, т.е. мы могли бы доставить дополнительный заказ. Типичные системы/службы GPS и навигации не предоставляют эту информацию. В этом контексте мы говорим о том, как мы прогнозируем CDT (как можно точнее) с помощью машинного обучения.

Гипотеза:

Гипотеза состоит в том, что CDT зависит от некоторых переменных:

  • Местоположение : адрес, тип адреса (квартира, дом, квартира)
  • Связанные с заказом: размер заказа (насколько он большой и тяжелый), время доставки (вечер, утро, день)
  • Внешние: погода, события в конкретный день, новый клиент (найти адрес может быть сложнее)
CDT = g(X)        ... hypothesis that CDT depends on variables X

Для проверки этой гипотезы мы собрали исторические данные более чем за год.

X = [ address, address_type, order_size, delivery_time_of_day, weather, events, new_customer ]

Мы преобразуем этот набор входных функций для использования нашим алгоритмом машинного обучения. Например, мы анализируем адрес, чтобы определить этаж, на котором находится клиент (например, 1-й этаж или 5-й этаж сильно повлияет на CDT, особенно если сотруднику приходится совершать несколько поездок от автомобиля к покупателю). Допустим, после преобразования мы получаем

X_transformed = f(X)        ... f represents various transformations

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

y = CDT                     ... to be predicted

Поэтому мы можем использовать контролируемое обучение, чтобы узнать взаимосвязь между нашими функциями (X_transformed) и целью (y). Обратите внимание, что это проблема регрессии, поскольку нам нужно предсказать оценку CDT. Мы обучили различные модели на основе различных алгоритмов, таких как линейная регрессия, случайный лес, ближайший сосед, нейронные сети и т. д. а также выполнять настройку гиперпараметров, чтобы добиться максимальной производительности с точки зрения точности без недообучения или переобучения. Мы также учли задержку прогнозов при принятии решения о развертывании модели, что обсуждается в следующем разделе. Мы выбираем функцию потерь L2 в качестве нашей цели и сообщаем о различных показателях ошибок, таких как RMSE, MAE, MAPE. L2 выбран, поскольку мы можем допустить +/- ошибки в прогнозах, которые близки к фактическому значению, но мы не можем допустить больших ошибок, поскольку они имеют последствия для реальной жизни.

# Notice y = CDT is y_actual
# y0 = CDT predicted by our modelimport numpy as np
N = len(y)  # number of samples being evaluatedMAE =  (1/N) * np.sum(np.abs(y - y0))
RMSE = (1/N) * np.sum(np.square(y - y0))
MAPE = (1/N) * np.mean(np.abs((y - y0) / (y + 1e-6))) * 100

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

определение CDT

В приведенном выше сценарии покупатель покупает товары X, Y, Z, F, которые добавляются в корзину. На основе входных данных, необходимых для модели CDT, мы получаем прогноз CDT1, и отображается доступность слота. Если по какой-то причине клиент решит передумать и удалить элементы Z, F и добавить N и M, это изменит CDT, поскольку мы можем видеть здесь, что обновленное значение CDT, предсказанное моделью (принимая новый набор входных данных), равно CDT2. Есть много причин, по которым CDT1 > CDT 2 или CDT 1 ‹ CDT 2. В следующем разделе мы уделим внимание пониманию того, как сделать систему масштабируемой и надежной.

Реализация

Мы используем Docker© для контейнеризации различных частей нашей системы. Мы упаковываем все зависимости, необходимые для сбора входных данных, определения характеристик, вызова модели и запускаем ее как независимый сервис. Это делается для того, чтобы служба прогнозирования была переносимой. Кроме того, это дает преимущество в том, что оно не зависит от облака. Мы используем Python для создания API и инфраструктуры для обслуживания конвейера прогнозирования. Чтобы обеспечить высокую пропускную способность запросов, мы используем асинхронный веб-фреймворк FastAPI. Затем мы развертываем это приложение FastAPI на готовом к работе сервере Uvicorn, который также является ASGI (Интерфейс асинхронного шлюза сервера). Запускается несколько рабочих процессов Uvicorn, и из-за их асинхронной природы мы видим значительный прирост производительности, особенно при высокой пропускной способности. FastAPI+ Uvicorn — одна из самых быстрых платформ, использующих Python, и обеспечивает производительность, очень близкую к обслуживанию на основе NodeJS. Здесь — сравнение различных вариантов обслуживания приложений на питоне.

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

Архитектура службы CDT

Кэширование и многопоточность

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

Механизм кэширования

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

import threadingthread = threading.Thread(target=_setcache, args=(cdtrequest,feature,cdtvalue))

Это значительно улучшило время отклика и сделало сервис более отказоустойчивым.

Заключение

Планирование маршрута необходимо для сокращения транспортных расходов и обеспечения эффективности логистики и операций. Онлайн-заказы на доставку составляют ~ 20–25 млн в год для ASDA, и правильная оценка CDT может увеличить это количество примерно на 15–20% в дополнение к эффективному планированию маршрутов, которые импровизируют планирование последней мили примерно на 10%. Это дает нам экономию средств и дополнительный доход более чем на 4–5 миллионов долларов в год.