Как алгоритмы Яндекса помогают автоматизировать маршрутизацию логистики
Можно ли оптимизировать работу логистов, опираясь на большие данные? Как распределять тысячи заказов и точек доставки за несколько минут? Какую экономию можно получить за счёт автоматизации создания маршрутов для курьеров и экспедиторов? Рассказывает директор по маркетингу Яндекс.Маршрутизации Павел Распутин.
— Яндекс.Навигатор, Яндекс.Карты и Яндекс.Такси и другие b2c-сервисы, которыми ежедневно пользуются миллионы человек, помогают нам собирать первичные данные. На их основе мы можем строить b2b-решения, например, алгоритмы маршрутизации.
Как выглядит обычный день службы логистики? Мы собрали данные с наших клиентов и попробовали визуализировать то, как работают курьеры. Получились следующие результаты. Утром курьеры находятся поблизости от складских точек. В течение дня по Москве происходит достаточно много перемещений, а вечером они возвращаются назад.
О чем это говорит? Логистика является довольно сложной оптимизационной задачей. Логист может быть квалифицированным специалистом, но реальность говорит о необходимости учитывать всё больше и больше параметров при построении маршрутов. Трафик на дорогах меняется очень быстро, в зависимости от погоды, праздников, ремонта дорог, пробок и ДТП. Автоматизация обработки этих данных позволяет подойти к решению вопроса более эффективно, поскольку базовая задача по прокладке маршрутов для курьеров и экспедиторов идеально подходит для алгоритмического решения.
Карты
Одной из ключевых метрик для характеристики качества карт, является количество объектов, которые в них есть. Например, это количество и качество прорисованных на картах дорожных сегментов, а также частота обновлений. У Яндекса одни из самых подробных и детальных карт и в России, и в СНГ — порядка 10 миллионов адресов и различных объектов, более 25 миллионов дорожных сегментов.
Яндекс делает до трёх обновлений в неделю. Туда попадают данные из «Народных карт», комьюнити неравнодушных пользователей, которые помогают добавлять новые объекты и отмечать какие-то изменения в уже существующих дорогах или адресах. Мы работаем с муниципалитетами для того, чтобы вовремя обновлять информацию о каких-либо перекрытиях, ремонтах и так далее. Вся эта информация нужна для того, чтобы правильно маршрутизировать логистику.
Дорожные сегменты по России зачастую настолько детальные, что мы знаем даже как ездить по закрытым территориям, которые находятся за шлагбаумом. Там тоже прорисованы дороги и, в целом, мы можем помочь проложить путь, например, до склада №3, который находится в большой промзоне.
Пробки
Вторым немаловажным элементом в любой маршрутизации является учёт пробок. Их требуется анализировать, чтобы маршруты получались проходимыми.
Например, есть участок дороги, который можно без пробок проехать за 8 минут, но если вы попадете в пробочное время, то простоите там более 40 минут, а это в 5 раз дольше.
Это не один пример. Мы знаем и много других участков, и не только в Москве, ибо такая ситуация характерно для всех крупных городов. Пробки обязательно нужно учитывать, но можно делать правильно или неправильно.
Неправильно — это учёт пробок по коэффициентам. Очень часто встречаются ИТ-решения, которые просто накладывают утренние, дневные и вечерние коэффициенты на свой дорожный граф — таким образом регулируя скорость и получая маршруты.
Яндекс.Маршрутизация собирает данные из многочисленных источников и строит на их базе прогноз пробок на будущие периоды. Наш прогноз пробок выглядит следующим образом — все дорожные сегменты мы разделяем в течение дня на 15-минутные интервалы и, накладывая один на другой, знаем — какая скорость будет на каждом из дорожных интервалов каждые 15 минут каждого дня. Такой подход даёт возможность прогнозировать пробки.
Мы же взяли и сравнили три разных роутера. Роутеры – это инструменты, которые сделаны для того, чтобы рассчитывать ожидаемое время прибытия и строить маршруты. Есть роутер Яндекс.Навигатора, есть роутер, который встроен в Яндекс.Маршрутизацию и есть беспробочный роутер, который оперирует коэффициентами, но не учитывает пробки.
Яндекс.Навигатор знает состояние дорог здесь и сейчас. Это даёт самую высокую точность в моменте, но не позволяет строить маршруты на завтра, на послезавтра и на ещё какой-либо другой день.
На этом графике синяя черта обозначает ожидаемое время прибытия, совпадающее с фактическим временем прибытия. По вертикальной оси — количество поездок, которое мы разложили по этому графику. Самое точное и самое большое количество поездок, где ожидаемое время прибытия и фактическое совпадают — у Яндекс.Навигатора. Немного ниже стоит Яндекс.Маршрутизация, поскольку это офлайн-режим и мы не можем спрогнозировать какие-либо аварии, которые случаются на дороге в течение дня.
Беспробочный роутер всегда прогнозирует ожидаемое время меньше, чем фактическое. Если использовать его, то в план будет закладываться большое количество опозданий. Как с этим борются компании? Они «накидывают» какое-то определенное количество транспорта, зная, что в целом им надо эти пробки учесть.
Мы сравнили несколько десятков решений логистов, которые пользовались либо ручным клонированием, либо маршрутизацией с беспробочным роутером. Обычно такая подстраховка дает примерную дельту в 20% относительно оптимального решения, то есть примерно 20% от стоимости доставки — цена условного учёта этих пробок.
Алгоритм
В любом маршрутизаторе обязательно должен быть алгоритм, который можно разработать самостоятельно или взять готовый. Команда бизнес-аналитиков Яндекса ежедневно занимается улучшением алгоритма, добавляя в него новые режимы планирования, поддержку операционных схем. Например, так выглядят маршруты крупного интернет-магазина с 250 машинами и курьерами, который развозят 3000 заказов по Москве в течение дня.
Логисту этого интернет-магазина пришлось бы потратить около двух часов на маршрутизацию и сортировку заказов, распределение их по машинам, а в автоматическом режиме такое планирование займёт 15 минут.
Алгоритм должен уметь учитывать все параметры бизнеса, он должен давать оптимальный результат за минимально возможное время. Условные 15 минут — это хороший интервал, когда логист приблизится к условному оптимуму. За это время алгоритм переберёт около миллиарда итераций, благодаря распределённым мощностям Яндекса.
Какой эффект можно увидеть от автоматического планирования? Во-первых, сокращается и сводится на ноль количество опозданий. Компания может более точно заявлять как у себя и на сайте, так и напрямую клиентам, что они могут выбрать узкий интервал доставки, даже полчаса. Во-вторых, сокращается время на планирование маршрутов за счёт использования стабильного автоматизированного решения. Логист будет вносить минимальные ручные правки, что позволяет сократить транспортные затраты.
Экономический выигрыш относительно ручного или статичного планирования довольно стабилен и может варьироваться от 10 до 25%.
Ещё одним фактором, который нужно учитывать при выборе решений для маршрутизации, является гибкость алгоритма. Все компании, которые хотят внедрить маршрутизацию, хотят, чтобы она умела поддерживать их операционную схему. Менять бизнес-процессы достаточно проблематично. Поэтому нужно, чтобы алгоритм был достаточно гибким и обладал всеми необходимыми параметрами, которые позволят комбинировать или составить операционную схему. Например, Яндекс только за последний год добавил несколько операционных схем — с автоматическим планированием, с планированием в онлайн-режиме, с поддержкой работы складов, с кольцевыми курьерами и т. д. Эти схемы можно подстроить под текущие бизнес-процессы, сделав незначительные изменения, например, в параметрах.
