Как мы с помощью ML вылечили проблему, не дававшую перейти на автомаршрутизацию курьеров

Привет, Хабр! Меня зовут Наталья Макарова, я ведущий разработчик команды геоданных в CDEK. В этой статье расскажу, как мы с помощью Машинное обучение (англ. machine learning, ML) — класс методов искусственного интеллекта, характерной чертой которых является не прямое решение задачи, а обучение за счёт применения решений множества сходных задач.</p>" data-abbr="ML">ML решили проблему, не дававшую нашей компании перейти на автоматическую маршрутизацию курьеров.

Мы умеем отслеживать прохождение грузом всей транспортной цепочки, включая промежуточные склады. Но посылку нужно ставить на конкретный маршрут до того, как весь груз придет на склад доставки. И даже до того, как он попадет в ERP‑систему СDEK (посылки оформят в офисах). То есть задача такая: определить, на какой маршрут поставить конкретный заказ до того, как появился сам маршрут!

 Статья будет полезна:

• участникам продуктовых команд — продактам, аналитикам, ведущим разработчикам — для пополнения «копилки кейсов» решения задач с нечеткими требованиями и демотивированными стейкхолдерами;

• специалистам из логистической сферы.

Содержание

• Сбор анамнеза

  • Как сейчас? Автоматизированная система управления маршрутами

• Диагностика

• Диагноз

• Лечение

  • Предпланирование

  • Прохождение маршрута

• Вывод

Сбор анамнеза

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

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

1. Ручная система — без использования ЭВМ. Знаете, как почта в 19 веке.

2. Автоматизированная — функции системы обеспечиваются миксом действий системы и человека. Мы находимся здесь.

3. Автоматическая — без участия человека. Мы хотим быть здесь.

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

Как сейчас? Автоматизированная система управления маршрутами

CDEK, не для кого не секрет — логистическая компания. Мы принимаем посылку в точке А и везём в точку В. Дальше (по желанию клиента) курьером доставляем её до двери. Процесс доставки от последнего склада до двери клиента называется доставкой на последней миле.

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

Зона городской доставки разбита на постоянные полигоны, которые мы называем «макрозонами». В каждой из них за доставку заказов и выполнение заявки отвечает один курьер. Клиент говорит свой адрес, мы вычисляем его координаты и распределяем заказ в нужную макрозону. Когда фура приходит на склад, все заказы собраны в огромные паллеты. Их разбирают кладовщики, и заказ отправляется на полку, закрепленную за конкретной макрозоной. Приходит курьер, загружает посылки с полки в машину и выходит на маршрут.

А вот дальше — внимание! Курьер открывает приложение и изучает: что, куда и когда он должен доставить. Там есть:

• Простые заказы: без временных интервалов, можно доставить в любой момент дня.

• Заказы, которые нужно доставить в определенный временной интервал (клиент согласовал: «Доставьте мне с 13:00 до 15:00»).

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

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

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

Диагностика

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

Помимо этих непростых коммуникаций нас ждали новые задачи:

• наблюдения за работой складов (обязательно в нескольких городах);

• поездки вместе с курьерами на выдачу посылок;

• встречи с бригадирами, начальниками доставок складов, региональными менеджерами;

• и даже полноценный event storming.

В итоге мы выявили такую выгоду для бизнеса и пользу для клиентов и сотрудников CDEK:

• одна из ключевых выгод — снижение стоимости доставки минимум на 10%;

• маршрутизация поможет оптимально планировать нагрузку курьеров, чтобы мы их не перегружали и не требовали невозможного;

• благодаря этому у нас будет информация, где именно находится курьер;

• технология позволит увеличить попадание в интервалы доставки: раз клиент сказал, что будет ждать с 13:00 до 15:00, надо и везти ему с 13:00 до 15:00, а не как курьеру удобно.

  

Диагноз

Основное заболевание

Наши бизнес‑процессы были настроены так, чтобы как можно быстрее привезти посылки пользователям. Мы называем это принципом «выдачи с колес» — груз должен проводить в обработке на складке как можно меньше времени и сразу передаваться на доставку.

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

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

Тут вы могли бы мне возразить: «Вам же не обязательно держать все посылки в одном месте. Вы же знаете, когда придет фура? Вот и выберите время, когда она приедет по расписанию. Вы же клиентам как‑то сообщаете, что их заказ придёт в определённый день. Не по кофейной гуще же вы гадаете?»

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

Во‑первых, нам нужно предсказывать объем работы за несколько суток, помните? Но у нас есть супер короткие магистрали — например, Барнаул‑Новосибирск. Расстояние между ними 250 км. Груз из фуры Новосибирск‑Барнаул живет в системе очень недолго (часов двенадцать), а предсказать, сколько курьеров должно работать в конкретный день, нам нужно за неделю.

Во‑вторых, вопрос предсказания, когда посылка доберётся до конечного склада, откуда её заберёт курьер и когда отвезёт клиенту — очень непростой. Мы умеем фиксировать факт прохождения грузом промежуточных стадий. Например, когда груз из Владивостока в Москву перемещается из фуры в фуру в специальных точках — Новосибирске и Екатеринбурге. Сейчас же вовсю кипит работа, чтобы неприятности (вроде задержки фуры на 3 часа под Хабаровском из‑за проколотого колеса) были видны в системе сразу и имели влияние на прогнозное время.

Осложнение

Разница работы складов. У каждого нашего склада процессы корректируются под себя. Приведу примеры, чтобы было понятно, как это происходит. Например, на какой‑то склад может приходить много груза с утра. Какой‑то склад может получать груз равномерно, но зависеть от задержек авиасообщения. И вот от этих разнящихся обстоятельств могут отличаться и вводные. Кому‑то комфортно, если наших маршрутов придется подождать пару часов, кому‑то — нет. У кого‑то груз равномерно появляется в системе, а у кого‑то случаются «всплески» — пять дней строили, например, 10 маршрутов, а потом самолет в Магадан взял и задержался на сутки. И все его посылки нужно доставлять уже в следующую дату.

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

Лечение

Мы разделили задачу по разработке и внедрению маршрутизации на два больших этапа: предпланирование и прохождение курьером маршрута.

Предпланирование

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

На этом этапе нам нужно понять, сколько курьеров понадобится в день Х. Также желательно посмотреть, как распределяются заказы: где на карте загрузка будет выше, а где — ниже. Конкретные адреса и посылки сейчас не особо важны. И да, как уже говорилось выше, многие из них еще даже не принесли в CDEK. Это задача прогнозирования.

С недавних пор случилось позитивное изменение: мы научились оперативно фиксировать время прихода‑отъезда‑задержки фур, перевозящих посылки по маршруту.

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

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

Постепенно в системе появляются реальные заказы, которые мы будем доставлять в дату смены, на которую строим прогноз. То есть люди приходят в пункты выдачи СDEK'а или оформляют доставку в интернет‑магазинах, эти заказы упаковываются в фуры и едут по своим логистическим цепочкам, развозя грузы на конкретные склады.

Как только заказ попал в систему, она рассчитывает, когда он должен прибыть в конечную точку. Этот заказ заменяет собой один из предсказанных, фиктивных заказов. Так постепенно прогнозные заказы будут заменяться заказами, которые уже есть в системе. Но! И это важно — эти заказы тоже прогнозные! Пока посылка не дошла до конечного склада, мы не можем со 100% уверенностью утверждать, что она не придет на день раньше или на день позже. Поэтому всё это время строим маршруты с так называемым «полным перестроением» — каждый раз по‑новому делим территорию на маршруты и по необходимости меняем количество курьеров.

Дальше наступает час Х, когда первые посылки приходят на конечный склад. Нам нужно «зафиксировать» маршруты: финально определиться с их количеством и больше эту цифру уже не менять. Почему именно в этот момент? Потому что посылки, уже дошедшие до склада, мы должны «прибить гвоздями» к какому‑то маршруту и положить их на полку для этого маршрута. С этой полки их и заберёт курьер. Если начнём раз в час перекладывать посылки с полки на полку — устроим такой хаос, что конкуренту не пожелаешь!

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

Прохождение маршрута

Курьер пришёл на работу, погрузил заказы в машину, открыл мобильное приложение и готов ехать. Что нужно на этом этапе? Уметь перестраивать маршрут из‑за изменившейся обстановки. Триггерами пересчета служат:

• факт выполнения заказа;

• перенос времени или места выдачи заказа;

• поступление заявки.

Вывод

Что мы поняли после теста? Проверку делали в Омске. Потому что склад CDEK в Омске средних размеров, его руководство интересуется проектом и готово терпеть неудобства :)

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

• Экономит ли это себестоимость — пока непонятно.

• Прозрачность работы курьера безусловно повышается.

• Главное — порядок выполнения заказов. Второстепенное — это как ехать по дорогам. С ремаркой, что это касается опытных курьеров. Если курьер новенький или заменяет отпускника, то ценность маршрута в формате «как проехать» резко повышается.

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

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

Хронические проблемы — повод попробовать экспериментальные методы лечения. Без ML-прогноза мы бы не смогли (опять) решить первую часть задачи маршрутизации курьеров — предварительное планирование нагрузки на курьеров и разбиение по маршрутам.

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

Что еще почитать по теме?

1. Яндекс.Маршрутизация: как мы окунулись в логистику и решили поменять будущее

2. Как мы переучивали алгоритм построения маршрутов 2ГИС ради грузовиков

3. У нас были курьеры, десятки посылок и час на доставку: кейс со своевременностью доставки 92% в Москве

4. Как мы с друзьями собрали сервис для построения маршрутов для походов и велопутешествий ActiveTrip.me