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

Привет! Меня зовут Юрий Беляков, я старший ML-инженер в Купере. Сегодня предлагаю вместе разобраться, что такое плановая доставка и как устроен алгоритм управления слотами в нашем сервисе. Обсудим, как проходило тестирование и масштабирование от одного магазина до всех гипермаркетов, на какие грабли мы наступили и как реализовали динамическое ценообразование на этой базе.

Этот проект и эту статью мы делали вместе с моим коллегой старшим ML-инженером Даней Богдановым.

Основы основ. Что такое плановая доставка

Купер — это онлайн-сервис доставки из магазинов и ресторанов. По сути, мы объединяем:

1. пользователей, оформляющих заказы;

2. сборщиков заказов и курьеров;

3. магазины-ритейлеры и рестораны;

4. бренды, которые продвигают свою продукцию на нашей платформе.

Мы предоставляем два типа доставки:

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

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

Плановая доставка — это в первую очередь доставка из гипермаркетов, таких как METRO и Ашан. У каждого магазина своя территория доставки, поделенная на зоны. Курьеры прикреплены к конкретному магазину и развозят заказы только оттуда. В приложении у сборщиков и курьеров видны смены, которые они могут занимать, продлевать и отменять в течение дня.

Важный термин, когда мы говорим о плановой доставке — «слот». Это временной интервал, в который мы обещаем привезти заказ. Как правило, у каждой зоны доставки свой набор слотов. Слоты имеют разную длину, пересекаются друг с другом, а кроме того — проставлены не только на сегодня, но и на семь дней вперед. Помимо слотов доставки есть слоты самовывоза — когда клиент может забрать уже собранный заказ из магазина самостоятельно.

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

Путь заказа: от оформления до передачи клиенту

1. Клиент выбирает слот доставки и оформляет заказ.

2. Примерно за пять часов до начала слота заказ попадает в диспатч — это алгоритм, который в соответствии с приоритетом назначает заказы на сборщиков. Сначала собираются заказы более ранних слотов.

3. Пока заказ в сборке, маршрутизатор подбирает рейс для него. 

4. По окончании сборки заказ ожидает доставки в соответствии с очередью — первыми доставляются заказы на более раннее время.

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

У слота плановой доставки есть несколько атрибутов. 

• Время попадания в диспатч — это нижняя граница того, когда заказ может начать собираться. 

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

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

В чем же трудности?

Как минимум в том, что слотами плановой доставки нужно управлять!

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

Для того, чтобы слоты закрывались «вовремя», и нужен алгоритм, который сможет контролировать нагрузку слотов в режиме реального времени, в том числе ночью.

Уже на старте проработки такого алгоритма мы столкнулись с несколькими проблемами.

1. На исторических данных нельзя было понять, какие действия «правильные» — размеченной выборки не было. Мы не могли сказать, что было бы, если бы в слот упал еще один заказ, или если бы слот был закрыт чуть раньше. Чтобы получить ответы, нам пришлось бы переместиться в параллельную вселенную, где события развернулись по-другому.

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

3. Когда мы начали искать информацию, мы поняли, что подобных алгоритмов на рынке просто нет. Нам неоткуда было брать идеи, и мы все придумывали с нуля. Поэтому я и делюсь кейсом в этой статье 🙂

4. Плановая доставка — очень хрупкая сущность. Когда заказы начинают опаздывать в первом слоте, это чаще всего приводит к опозданиям в последующих. Как на приеме у врача: один пациент задерживается, и вся очередь сдвигается.

Суть алгоритма

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

Скажем, в одном слоте лежит два заказа. У каждого заказа есть свои атрибуты, и с помощью какой-нибудь базовой модели типа градиентного бустинга мы получаем прогноз по времени сборки для каждого из них — например, 32 и 23 минуты. Далее мы суммируем прогнозируемое время и получаем суммарное время сборки всех заказов в конкретный слот. С процессом доставки то же самое.

Здесь возникают новые нюансы:

• Мы не знаем заранее, кто будет собирать и отвозить заказ. Опытные сборщики и курьеры работают ловчее, чем новички. Мы пытаемся учитывать общую производительность смены на точке.

• Сборщик может одновременно работать с двумя заказами. Какие заказы будут собираться параллельно тоже доподлинно неизвестно. Чтобы это учитывать, мы пользуемся различными эвристиками.

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

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

• Помимо самой доставки необходимо иметь в виду время на погрузку заказов и на возвращение курьера из рейса на точку.

Все это — кирпичики, из которых складывается наш алгоритм.

Разберем, как строится очередь, на простом примере.

В магазине один курьер и один сборщик. У нас есть два двухчасовых слота: 11:00-13:00 и 12:00-14:00. Сборщик выходит на смену в 9:00. Мы знаем, что в первом слоте лежит три заказа с суммарным временем сборки полтора часа, а значит — заказы первого слота будут собираться до 10:30. Второй слот начнет собираться после первого, и если там два заказа с суммарным временем сборки один час, то сборка заказов второго слота продлится 11:30. С доставкой все так же, с одной ремаркой: сборка не зависит от доставки, а вот доставка завязана на сборке и не может начаться до того, как будут собраны заказы рейса.

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

Нагрузка на слот

Для приведения нагрузки к числовому виду мы придумали метрику, которая показывает вероятность опозданий, и назвали ее surge-level.

У каждого слота есть левая граница — по сути, минимальное время начала погрузки. Также мы можем вытащить ожидаемое время окончания доставки для слота. Берем разность между этими двумя моментами времени и получаем числитель (на картинке ниже — два часа и пять минут).

В знаменателе мы вычитаем время начала погрузки не из ожидаемого времени окончания доставки, а из правой границы слота (на картинке — два с половиной часа).

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

Разумеется, есть нюансы. И нам нужно учитывать контекст работы с очередями. Здесь для визуализации я привлеку разноцветных человечков.

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

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

Подытоживая все вышесказанное, флоу алгоритма выглядит так:

1. Берем самые актуальные данные о заказе и точке.

2. Прогнозируем время сборки и доставки каждого заказа.

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

4. Понимая очередь, рассчитываем surge-level.

5. Зная surge-level и учитывая контекст очереди, принимаем решение, что делать со слотом: закрывать или открывать.

Далее действия становятся видны пользователю: некоторые слоты закрываются, а некоторые могут открыться по новой.

Поехали тестировать

Изначально алгоритм представлял собой DAG в Airflow. Он прогонял весь флоу от начала до конца раз в пять минут. Эффекта памяти предусмотрено не было. Каждый раз алгоритм выстраивал очередь с нуля, поскольку одно маленькое изменение влияет на всю последующую очередь.

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

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

Все основные изменения в алгоритм вносились на основании фидбека от супервайзеров и сити-менеджеров. Получился Reinforcement Learning разработчиков with Human Feedback от супервайзеров.

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

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

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

2. Со второй проблемой мы столкнулись, когда расширили горизонт работы алгоритма до суток, то есть когда он уже умел управлять слотами в том числе на завтра. Оказалось, что сборщики и курьеры не слишком заранее проставляют смены на последующий день: иногда это происходит утром, за час до выхода на работу. Если на завтра уже есть много заказов, но смен нет, алгоритм думает, что заказы просто некому будет собирать и доставлять, а значит — надо закрыть все слоты. Чтобы это решить, мы настроили модель, которая прогнозирует количество сборщиков и курьеров. Утром происходит переход с прогноза на фактические данные о проставленных сменах.

3. Третья интересная проблема — алгоритм плохо работал при дисбалансе партнеров (например, когда курьеров, было сильно больше, чем сборщиков). Для решения этой проблемы мы разделили показатель нагрузки. Раньше это был один surge-level, теперь показателя два:  по одному на сборку и доставку. Все действия алгоритма основаны на наибольшем из двух показателей.

Кроме того, каждая из тысячи точек обладает целым рядом уникальных особенностей. Чтобы алгоритм подстраивался под них, мы настроили простой механизм адаптации параметров его работы, по духу похожий на Reinforcement Learning.

Динамическое ценообразование

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

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

Первая версия алгоритма динамического ценообразования выглядела как лесенка. Surge-level на 0,7 — включается первый уровень наценки, на 0,8 — второй уровень, на 0,9 — третий уровень. Дальше слот закрывается.

Быстро сделали лесенку и начали тестирование. Сразу хорошо не получилось, потому что нам вновь нужно было учитывать контекст очереди.

Вернемся к разноцветным человечкам.

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

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

Рефлексируем

В мае 2023 года мы развернулись в одном магазине в Рязани и быстро масштабировались на весь город. В июне присоединились Волгоград и Челябинск. Уже в июле алгоритм работал во всех городах-миллионников! И хотя изначально планировалось, что алгоритм будет лишь помогать людям управлять слотами, в августе было автоматизировано управление 99% слотов. За четыре месяца, к сентябрю, мы выросли до динамического ценообразования, а к концу сентября внесли правки и успешно масштабировались до всех гипермаркетов страны.

На достигнутом мы не останавливаемся, есть несколько идей для развития — в том числе почерпнутые из чатов тестирования. Например, surge-level сейчас предпринимает действия, когда все заказы уже сделаны, а мы хотим, чтобы он предвидел повышенный спрос. Также в планах поиск оптимальных наценок через поюзерные A/B-тесты. Самое сложное и масштабное — это полный переход на рельсы обучения с подкреплением. Будем надеяться, что получится!

В комментариях вы можете пожелать удачи и задать вопросы о деталях нашего алгоритма 🙂

Псс, подписывайся на tg-канал ML-команды СберМаркета ML Доставляет.