Эволюция прогноза времени в Delivery Club25.02.2021 12:35

Всем привет! Меня зовут Сергей Яныкин, я руководитель команды Dynamic Time в R&D-направлении Delivery Club. Хочу вам рассказать, как наша команда перешла на тёмную сторону к динамическому расчёту прогнозов и стала ответственной за время в сервисах Delivery Club.

Для начала давайте подумаем, насколько сильно время, которое используется в логистических системах, может влиять на работу всей системы?
В нашей компании время — одна из главных сущностей, потому что оно является важным атрибутом для всех участников заказа:

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

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

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

Что это значит?

Немного истории

Давайте рассмотрим пример, как раньше в Delivery Club считали прогноз.

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

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

Какие из этого вытекают проблемы

1. По сути, у нас не было инструмента, чтобы понимать, насколько хорошо курьеры выполняли свои заказы, потому что время, которое мы прогнозировали, не являлось «прозрачным».
2. Клиенты часто жаловались в техподдержку, тем самым увеличивая Contact Rate, а это дополнительные расходы.
3. Также клиенты жаловались, что еда приезжает холодной, а это следствие того, что время прибытия курьера в ресторан оказывалось неточным.

В общем, одни проблемы.

Что же можно сделать

Мы начали улучшения с момента назначения заказа: посчитали дистанцию, которую нужно преодолеть курьеру относительно его текущего положения до ресторана и от ресторана до клиента. Для этого мы используем Open Source-сервис, который умеет строить маршруты и рассчитывать время и дистанцию по переданным координатам. Тем самым мы получаем два отрезка:

• от текущего положения курьера до ресторана (в логистике принято называть first mile);
• и от ресторана до клиента (last mile).

Теперь нам нужно рассчитать прогноз для каждого участника заказа — курьера, ресторана и клиента. Это можно сделать по формулам:

atVendor (время, к которому нужно прийти в ресторан) = acceptOrderTime + firstMileTime

pickupTime (время, когда нужно забрать заказ из ресторана) = atVendor + cookingTime

atClient (время, когда нужно быть у клиента) = pickupTime + lastMileTime

После расчёта мы отдаём прогнозы каждому участнику заказа. Сюда мы можем закладывать различные коэффициенты и дополнительные этапы доставки: парковка у ресторана или клиента, если курьер на автомобиле, или длительность задержки курьера у клиента, которая зависит от типа оплаты заказа (наличными или картой).

Кажется, становится лучше

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

Мы достаточно хорошо научились прогнозировать будущий маршрут курьера с учётом разных коэффициентов. Но представьте, что будет, если у ресторана час пик и он не успевает отдавать заказы курьерам вовремя. Это приводит к задержке на выдаче (pickupTime). Как следствие, курьер не успевает к клиенту, и мы опять повышаем Contact Rate. Или, например, курьер идёт к клиенту №1, мы назначаем второй заказ и рассчитываем прогнозы относительно того времени, когда курьер передаст заказ клиенту №1. Но тот долго не открывает дверь курьеру, и мы не успеваем вовремя к клиенту №2.

Заложить в прогноз все возможные случаи и погрешности почти невозможно. Поэтому мы пришли к тому, чтобы сделать наше время динамическим: оно может меняться и пересчитываться на определённых этапах заказа. Каких именно, вы узнаете дальше.

Но здесь мы столкнулись с другой проблемой: логика расчёта времени была размазана по многим командам. Не было чёткого понимания, в каком сервисе нужно подкрутить, чтобы сделать прогноз лучше и не сломать его в других сервисах. Поэтому мы решили сформировать команду с говорящим названием Dynamic Time.

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

В чём, собственно, сложность

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

В каком из сервисов вы бы решили делать изменения по улучшению прогноза для клиентов? А для курьеров?

Для нас правильный ответ звучал так:

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

Почему для этого нужна отдельная команда

В компании не хватало команды, сосредоточенной на конкретной и важной задаче — прогнозе времени. Вызовом для такой команды было разработать единую платформу (мастер-систему прогноза времени доставки) и внедрить новый прогноз во все компоненты Delivery Club, которые работают со временем.

Так как мы используем Inner Source-подход, то становится логичным, что держать логику в разных сервисах и размывать ответственность по разным командам не очень правильно.

Создавая новую команду и делегируя ей эту ответственность, мы снижаем время разработки и доставки фич до production.

Как мы прогнозируем время

В логистической доставке, как мы уже выяснили, есть два термина: First mile и Last mile. Но также в рамках каждого заказа есть и другие отрезки, например:

• PickupTime — время, проведенное курьером в ресторане, пока заказ готовят и упаковывают;
• ClientLag — время, проведенное у клиента для передачи заказа, в том числе время на парковку.

У каждого заказа есть жизненный цикл: создание, назначение курьера, подтверждение заказа курьером, забор из ресторана и доставка клиенту.

До образования нашей команды были сделаны первые попытки расчёта динамического времени прогнозов в сервисах логистики. Они заключались в том, чтобы считать время от назначения заказа на курьера и пересчитывать его, когда курьер забирает заказ из ресторана. Тем самым мы старались скорректировать First mile и Last mile. Так как результаты были хорошими, мы продолжили двигаться в этом направлении.

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

Мы решили переписать 1 в 1 существующую логику в новый сервис, далее сервис логистики вызывал синхронно наш сервис, передавая необходимые данные для подсчёта динамического времени. После мы сравнивали два прогноза, и если они отличались на n секунд, то мы выводили эти различия в лог. Таким образом мы смогли протестировать тот код, который перенесли, и дальше отказаться от подсчёта динамического времени в логистическом сервисе.

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

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

Но здесь может возникнуть вопрос, а какое время должно показываться в тот момент, когда курьер ещё не назначен или событие из топика ещё не пришло?

Сейчас мы используем время зоны для таких случаев. То самое время, которое было в начале статьи и с которого мы стали вводить улучшения. Это так называемое время «на выдаче», которое видит клиент в карточке ресторана. Его мы также используем как fallback-логику, если по каким-то причинам сервису не удалось создать прогноз по заказу.

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

Текущий алгоритм прогнозирования

Когда заказ создаётся в системе, у него проставляется fallback-прогноз, то же самое происходит в случае непредвиденных ситуаций. Клиент после создания заказа видит именно время «по умолчанию». Далее сервис автоназначения подбирает подходящего курьера, и после его назначения мы имеем достаточный набор данных для подсчёта прогноза:

• дистанцию и время между координатами курьера и рестораном;
• дистанцию и время между координатами ресторана и клиентом;
• тип передвижения курьера;
• идентификатор ресторана.

С помощью этих данных мы можем прогнозировать:

• во сколько курьер будет в ресторане в зависимости от типа его передвижения;
• во сколько ресторан должен подготовить заказ;
• во сколько курьер будет у клиента.

В нашем расчёте мы учитываем несколько факторов:

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

А где, собственно, динамика?

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

• когда курьер забирает предыдущий заказ из ресторана;
• когда курьер доставляет предыдущий заказ;
• когда курьер забирает текущий заказ из ресторана.

Соответственно, для цепочки заказов пересчёты будут аналогичные.

Что нам это даёт?

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

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

Также возможны случаи, когда заказ отменяется или переназначается на другого курьера. Тогда мы тоже применяем механизм пересчёта прогнозов.

Рассчитывать динамическое время нам помогает Kafka и чтение событий из топика по изменению статуса заказа.

Ещё мы в Delivery Club умеем батчить заказы: это когда клиент №2 сделал заказ в том же ресторане, что и клиент №1. Если оба находятся недалеко друг от друга, то мы учитываем прогноз для клиента №2, основываясь на прогнозе для клиента №1.

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

Что ещё мы можем улучшить?

Сейчас мы идём к тому, чтобы везде работал JIT (Just In Time) — механизм минимизации времени, которое проводит курьер в ресторане. Подробнее об этом мы писали в статье «Как мы побеждаем неопределенность в Delivery Club». Для этого ребята из команды автоназначения курьеров на заказ используют наши прогнозы прихода в ресторан и забора заказа. Они пытаются подобрать наиболее подходящего курьера в зависимости от времени приготовления блюда рестораном. Этим мы хотим свести к минимуму время ожидания курьера в ресторане.

Как всё это контролировать?

Если говорить про метрики, то перед нами стояло несколько задач:

• Улучшить метрику forecast accuracy. Она показывает, насколько прогноз точен относительно факта.
• Улучшить метрику delays share. Это процент заказов с ранними и поздними приходами курьеров.
• Уменьшить forecast error. Это метрика, которая коррелирует с forecast accuracy.
• Снизить time to market. Многие наверняка знают эту метрику — это время доставки фич на прод.

Конечно, мы всё это не смогли бы контролировать без метрик в Grafana. Мы очень любим различные графики и метрики и решили построить несколько графиков, которые в реальном времени показывают, как ведёт себя прогноз. Например, для контролирования forecast error мы слушаем ещё один топик по фактическим меткам заказа. Вычитаем из факта наш прогноз, делим на количество заказов и получаем процент ошибки. Допустим, сервис спрогнозировал приход в ресторан в 15:00, а по факту курьер нажал в приложении статус «пришел в ресторан» в 15:05. Значит, можем вычислить ошибку по формуле:

длительность прогноза = (прогноз прихода в ресторан) — (факт начала заказа)

фактическая длительность = (факт прибытия в ресторан) — (факт начала заказа)

ошибка в секундах = длительность прогноза — фактическая длительность

Ошибка по модулю в этом случае будет равна 300 секунд.

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

Улучшаем прогноз, используя ML-модель

Мы, как и многие другие крупные компании, не стоим на месте, а внедряем проверенные временем модели данных.

Недавно у нас появилась ещё одна команда в R&D, которая смогла создать pipeline для обучения и использования ML-моделей в production. Благодаря этому мы стали использовать ML-модели в боевых условиях.

Улучшать качество прогноза нам помогают ребята из команды Data Science. На исторических данных с помощью библиотеки CatBoost они обучили модель градиентного бустинга для прогнозирования отрезка Last mile. На каждом прогнозе наш сервис ходит в сервис экспериментов, где получает идентификатор модели, с которым мы ходим в ещё один сервис, передавая идентификатор и данные для прогнозирования:

• информацию о ресторане;
• информацию о курьере;
• время создания заказа.

Затем получаем чистое время, к которому курьер должен прийти к клиенту. Весь этот процесс для нас выглядит как чёрный ящик, поэтому если мы захотим переобучить и протестировать модель, нам достаточно получить новый идентификатор эксперимента и сходить с ним за новыми прогнозами. В ходе плавного перехода на прогноз от ML-модели мы уменьшили MAE (среднеквадратичную ошибку) по Last mile.

Также совсем недавно мы начали эксперимент с новой ML-моделью, в котором пытаемся улучшить Pickup time. Помимо тех же данных, что и для Last mile, мы передаём средний чек заказа, тем самым лучше прогнозируя время приготовления блюда. А это, как мы знаем, отражается на всём прогнозе.

В дальнейших планах у нас полный переход на прогнозы от ML-модели для всех отрезков маршрута.

Какие ещё остались проблемы

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

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

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

Через тернии к звёздам

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

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

Спасибо, что дочитали статью до конца. Мы знаем, что наши прогнозы ещё не идеальны, но стремимся сделать так, чтобы они становились только точнее!

И не забывайте, время — деньги!