Всем привет! Я Лиля Царёва, руководитель группы развития технологий батчинга в Яндекс Доставке. В этой статье расскажу, что же такое батчинг, как он помогает нам экономить и почему более долгие доставки не равно менее счастливые пользователи.
Что такое эффективность в Доставке (следите за руками)
Яндекс Доставкой пользователи отправляют самые разные вещи: документы, забытые ключи, цветы и подарки. А ещё есть корпоративные клиенты: рестораны доставляют горячую пиццу, магазины — продукты, бытовую технику, товары для дома и многое другое.
Наша задача — найти на каждую посылку курьера, точно так же, как Такси ищет водителя для пассажира.
Но, во-первых, мы доставляем не людей, а посылки. Во-вторых, не за каждой посылкой нужно ехать срочно, как за только что приготовленной пиццей: товары для дома, например, можно доставлять в течение дня.
Всё это позволяет нам класть несколько посылок в одну машину:
В команде Эффективности мы работаем над тем, чтобы удовлетворить больше спроса имеющимся предложением. Отсюда наша главная метрика — как много заказов мы смогли доставить всеми курьерами. Формула выглядит так:
Эффективность = Σ посылок / Σ курьеров = DH / SH,
где количество заказов мы выражаем в суммарном времени всех доставок (demand hours, DH), а количество курьеров — в суммарном времени, которое они провели на линии (supply hours, SH).
Как мы увеличиваем эффективность
Мы объединяем посылки по пути.
Рассмотрим простой пример. Допустим, поступило два заказа с 47 минут demand-часов. Чтобы их развезти, потребуется два курьера, которые суммарно потратят 65 минут supply-часов. А если мы объединим эти заказы и доставим их одним курьером, то на 47 минут demand-часов мы потратим 47 минут supply-часов.
В первом случае эффективность составляла 72%, а во втором — 100%.
Один большой маршрут, состоящий из нескольких заказов, мы назвали батчем. А технологии, которые за это отвечают, — батчингом.
Как оцениваем эффективность
Главной метрикой для оценки качества батчинга мы сделали экономию supply-часов. Так, в прошлом примере доставка батчем занимала 47 минут, а по отдельности (мы называем такой маршрут P2P, peer-to-peer) — 65 минут. То есть батчинг сэкономил 18 минут курьерского времени.
Экономию считаем по формуле:
Экономия SH = (Σ P2P SH - Batch SH) / Σ P2P SH
И узнаём, насколько доставка с батчингом выгоднее, чем без батчинга.
В нашем примере экономия составит 28%:
Экономия SH = (65 - 47) / 47=18 / 65 = 28
Как разрабатывали технологию батчинга
Шаг 1. Научились строить мёртвые батчи
Это подход, в котором мы сначала строим сложный маршрут из нескольких заказов, а затем предлагаем этот маршрут курьеру.
Как это работает: у каждого заказа есть точки отправителя и получателя. Вокруг этих точек рисуем окружности заданных радиусов и набираем другие заказы, точки которых попадают в соответствующие окружности.
Таким образом мы объединяем все заказы в городе в кластеры, которые мы назвали сегмент-паками.
Далее из заказов, попавших в один сегмент-пак, строим маршруты. Чтобы создать батч из двух заказов, перебираем все варианты попарно (brute force), а для более длинных батчей применяем алгоритм лучевого поиска (beam search).
На выходе получаем множество маршрутов с разным составом заказов и порядком обхода точек. Убираем неоптимальные, а также те, которые не удовлетворяют внешним требованиям — допустим, не доставлять готовую еду вместе с машинным маслом. А те, что подошли, отправляем на следующий этап поиска курьеров.
Шаг 2. Научились строить живые батчи
Мы решили, что можно батчить ещё не назначенные заказы не только между собой, но и с заказами, которые доставляются прямо сейчас. Так, мы вставляем точки нового заказа в уже выполняющийся маршрут и предлагаем это изменение курьеру. Мы назвали это живым батчингом.
Как это работает: Берём всех курьеров, которые сейчас доставляют заказы. Далее для каждого неназначенного заказа рисуем окружность вокруг точки отправителя и отбираем всех курьеров, в заказах которых в окружность попадает либо сам курьер, либо одна из ещё не посещённых точек его маршрута.
Получаем пары «заказ — маршрут», которые далее пропускаем через ряд фильтров, например:
- соответствует ли курьер требованиям заказа (допустим, если доставляется горячая еда — у курьера должен быть термокороб);
- по пути ли новый заказ для курьера;
- не придётся ли курьеру возвращаться на уже посещённую точку.
Все пары, которые прошли фильтрацию, попадают на следующий этап, где могут выиграть назначение на конкретного курьера.
Но это всё теория. На практике же мы столкнулись с тем, что заказы крайне редко доставлялись в батчах. И мы стали искать причину.
Шаг 3. Научились создавать искусственную плотность заказов
Возьмём три розыгрыша с разницей в минуту и посмотрим на заказы на карте.
Мало какие из этих заказов можно сбатчить: нет вариантов ни рядом, ни по пути.
Проблема в отсутствии плотности: новые заказы непрерывно поступают в систему распределения заказов — диспатч — но очень быстро назначаются на курьеров, и мы не успеваем поймать удачную пару заказов, которые можно было бы сбатчить.
Посмотрим, что будет, если все заказы этих трёх розыгрышей собрать вместе:
Выбора становится больше, однако для этого требуется какое-то время не назначать курьеров на новые заказы.
Мы решили это с помощью буфера: его задача — некоторое время запрещать P2P-назначение, чтобы заказы накопились и сформировалась необходимая плотность. В широком смысле буферизация позволяет обменивать время поиска исполнителя на эффективность.
Технически буфер реализован как один из фильтров, через которые мы пропускаем сгенерированные маршруты. Он не пропускает маршруты-одиночки первые Х минут разыгрывания заказа, где Х зависит от разных факторов, например от требуемой скорости доставки.
Чем дольше заказ находится в буфере, тем лучше он может сбатчиться и больше supply-часов сэкономить.
Шаг 4. Осознаём, что клиент, конечно, рад за нас, но не от всего сердца
Рассмотрим ещё один пример. Допустим, мы доставляем три новых заказа, и по отдельности это будет стоить нам 95 минут supply-часов, а с батчингом — 59 минут, то есть мы сэкономим 38% курьерского времени.
Счастливы мы, счастливы курьеры, но точно не три клиента, каждый из которых очень ждёт свою горячую пиццу, игровую приставку и цветы, заказанные маме на 8 марта.
Изначально ожидалось, что доставку можно выполнить за 45, 20 и 30 минут соответственно. Но из-за объединения в батч время доставки отдельной посылки увеличивается, потому что курьер отклоняется от прямого маршрута и развозит другие заказы.
Чтобы поддерживать SLA для клиента, мы ограничили допустимый уровень «замедления» доставки. Для этого ввели параметр масди (MASDI, Max Absolute Segment Duration Increase), который пропускает только батчи, удовлетворяющие условию.
Например, если доставка посылки отдельно занимает 30 минут и мы не хотим, чтобы это время увеличивалось больше чем на 10 минут, фильтр не пропустит все батчи, в которых доставка займёт более 40 минут.
В нашем сервисе также бывают ситуации, когда известно конкретное время, в которое нужно забрать посылку, и время, к которому требуется её доставить. Тогда мы не можем ни на сколько превысить сроки доставки и выбираем только те батчи, при которых курьер приедет без опоздания на все точки маршрута.
Таким образом, мы улучшили клиентский опыт и снизили задержки, но с батчингом заказы всё равно доставляются медленнее, чем по отдельности.
В чём выгода для клиента
1 минута курьерского времени стоит для нас Х — допустим, 10 рублей. Тогда P2P-доставка заказа, которая займёт 65 минут, обойдётся нам в 650 рублей, а доставка батчем за 47 минут — в 470 рублей, на 28% дешевле. Настолько же дешевле мы сделаем её и для клиента. Мы рассчитываем все варианты:
И предлагаем клиенту выбор: экспресс-доставка без экономии, доставка на 30 минут дольше и на 15% дешевле или на полтора часа дольше и на 30% дешевле.
Таким образом, батчинг делает наш сервис дешевле для тех, кому не так важна скорость.
Шаг 5. Улучшили генерацию маршрутов алгоритмом Яндекс Маршрутизации
В 2022 году к Доставке присоединился сервис Яндекс Маршрутизация, который помогает компаниям планировать маршруты и мониторить заказы. Он решает ту же задачу, что и мы — распределяет заказы по исполнителям — но использует для этого алгоритм имитации отжига RouteQ.
Алгоритм имитации отжига вдохновлён процессом отжига в металлургии, когда металл нагревается и контролируемо охлаждается, что увеличивает его кристаллизованность и уменьшает дефекты. Основные принципы алгоритма:
- использование случайных операций — позволяет исследовать различные области пространства поиска;
- использование случайных операций — позволяет исследовать различные области пространства поиска;
- принятие худших решений с постепенным снижением их вероятности по аналогии с охлаждением при отжиге в металлургии. Это позволяет сначала исследовать пространство поиска более широко, а затем сосредоточиться на улучшении решения.
Мы протестировали его на своих задачах и поняли, что он лучше справляется с генерацией длинных батчей. Но оказалось, что он работает медленнее — доходит до нескольких десятков секунд, тогда как наш алгоритм справляется в среднем за 3 секунды.
Чтобы значительно не замедлять розыгрыш, мы встроили его асинхронно.
Как это выглядит: Диспатч работает итерационно: получает на вход ещё не назначенные заказы, строит маршруты, разыгрывает их среди курьеров; в следующей итерации всё повторяется, и так далее. Параллельно он дублирует все заказы в RouteQ. Этот алгоритм работает со своей скоростью и по готовности передаёт построенные маршруты в диспатч в ближайшем розыгрыше. Так наш алгоритм ищет кандидатов по большему списку маршрутов: и своим, и из RouteQ.
При этом собственные алгоритмы диспатча генерируют множество вариаций, которые затем фильтруются по набору эвристик (оптимальности, SLA, различным бизнес-требованиям), а RouteQ сразу выдаёт только подходящие маршруты.
В теории всё хорошо, но батчи от RouteQ редко назначались на курьеров: пока алгоритм работал, диспатч уже успевал построить другие, менее эффективные маршруты с этими же заказами. При этом батч RouteQ разрушался — алгоритм отрабатывал впустую.
Чтобы это исправить, мы стали давать RouteQ на каждый заказ несколько минут эксклюзивного поиска, когда он работает один. Тогда сгенерированные им маршруты точно используются. Этот механизм назвали букингом: «бронируем» алгоритм первые несколько минут.
С этой технологией мы быстро увеличили все метрики батчинга. Для крупного маркетплейса алгоритм увеличил размер батчей на 24%, экономию supply-часов — на 3,5 п. п., а экономию дистанции — на 7,7 п. п.
В результате за полтора года экономия supply-часов в сегменте доставок в течение дня (за 2–4 часа) выросла в 2,5 раза.
Наконец-то счастливы все: мы, курьеры, пользователи и даже новый алгоритм, который стал полноценным членом нашего семейства алгоритмов и больше никогда не работает впустую.