Сложно не заметить, как сильно за последние два года изменилась доставка товаров. Меры, принятые для сдерживания пандемии, вынудили многих впервые полностью положиться на онлайн-заказы. Рынок онлайн-продаж резко вырос, и компании довольно быстро подстроились под новые условия, наладили доставку и даже стали предлагать дополнительные услуги вроде «оставить заказ у двери». У нас сформировались новые привычки и новые ожидания от доставки: она должна быть быстрой и комфортной. А бизнес понял, что в современном мире нужно уметь быстро подстраиваться под изменения и планировать разные сценарии.
Самой, наверное, впечатляющей услугой сегодня является экспресс-доставка из дарксторов – например, из Яндекс.Лавки. Получив ваш заказ, сборщик даркстора формирует его и передает курьеру. Дарксторы расположены так, что до любой точки в радиусе обслуживания (около 1–2 км) можно добраться в срок от 10 минут. Эти условия гарантируют беспрецедентную скорость
Но важно обеспечить бесперебойное снабжение дарксторов товарами. С раннего утра от распределительных центров к дарксторам едут сотни машин. Чтобы они вышли на дороги, логисты рассчитывают необходимое количество машин на следующий день, их характеристики, распределяют товары по машинам, строят маршруты. Результат планирования, например, может выглядеть так:
Завтра необходимо задействовать n «газелей» грузоподъемностью 3,5 т, n1 машин-холодильников и n2 машин грузоподъемностью 5 т
При построении маршрутов приходится сталкиваться с различными ограничениями и особенностями. Например, жилые зоны не могут принимать пятитонные грузовики – туда можно отправить только менее габаритные машины. Конечно, для этого у логистов должны быть сведения обо всех подобных правилах.
Кроме особенностей складов, Яндекс.Лавке приходится учитывать особые условия перевозки товаров. Для обозначения специфичных характеристик товарам, точкам доставки и машинам присваиваются теги. Например, если товар должен ехать в машине с холодильным оборудованием, то в логистической системе он отмечается тегом «холод». Этим же тегом помечаются и сами машины-холодильники.
Вместе с водителями, которые доставляют товары в дарксторы, на улицы просыпающегося города выезжают тысячи их коллег, которые снабжают обычные магазины, склады и пункты выдачи заказов, развозят заказы и посылки напрямую по клиентам или же забирают их, чтобы вернуть на склад или в сортировочный центр.
Крупные магазины, доставляющие напрямую покупателям, выполняют десятки тысяч заказов в день. Все эти заказы нужно распределить по машинам, учитывая их вместимость и наличие требуемого оборудования, принципы и пределы загрузки курьеров, их перерывы на отдых, обещанные клиентам интервалы доставки, сервисное время у клиента на дополнительные услуги вроде примерки и установки оборудования. Таких ограничений множество
Основу этой пирамиды параметров составляет дорожная ситуация и пробки в частности. Можно очень аккуратно, с учетом всех операционных условий спланировать маршруты, но без информации о пробках доставка вовремя будет невозможна. Мы сталкиваемся с пробками, когда запускаем навигатор или заказываем такси, но для логистов, которые планируют маршруты курьеров, важны пробки в прогнозе на день вперед или даже больше.
В Яндекс.Маршрутизации рассказывают, что для точного прогноза времени прибытия курьера нужно понимать, какими с большой вероятностью будут пробки в определенном временном срезе конкретного дня на каждом дорожном сегменте.
Причем спланировать оптимальный маршрут недостаточно. Для обеспечения качества доставки логисты мониторят исполнение заказов в реальном времени. Так можно видеть местоположение машин, точно прогнозировать поставки товаров в ретейл-сети, быть на связи с курьерами. Если же произойдет непредвиденная ситуация, логисты, использующие современные системы, могут быстро перераспределять товары по другим курьерам или перенести доставку – в зависимости от ситуации и правил компании.
Мониторинг качества доставки в Яндекс.Маршрутизации
Есть и еще один важный аспект, о котором мы, покупатели, не задумываемся, но который имеет огромное значение для некоторых компаний и их курьеров – это изменение объемов продаж из-за сезона или периода распродаж или ковидных ограничений в сфере торговли. В среднем в пиковые периоды количество заказов возрастает на 20–30%. Для крупной компании, которая выполняет по несколько тысяч или десятков тысяч в день, это сотни и тысячи дополнительных заказов. И вот тут компаниям приходится решать вопрос управления логистикой при разных условиях. Одни на пиках нанимают дополнительных курьеров (аутсорс), другие, у которых спрос вырастает не настолько сильно, рассчитывают количество курьеров так, чтобы максимально нагружать их в пиковые периоды и держать среднюю нагрузку в течение остального года.
Все это происходит за кулисами: в кабинетах логистов, в офисах компаний и на складах, в телефонах курьеров. Чтобы составить маршрут, нужно объединить сотни тысяч точек конечной доставки и различные необходимые для нее параметры, а это миллионы возможных комбинаций. Перебрать эти варианты вручную и выбрать оптимальный, да еще и учесть все параметры, не получится. А ведь решать приходится, по сути, одну из самых знаменитых оптимизационных задач – задачу коммивояжера.
Задача коммивояжера в современном прочтении
Постановка задачи коммивояжера, или бродячего торговца, очень проста: нужно объехать некоторое количество пунктов и вернуться в исходный максимально «дешевым» образом. «Цену» переезда из одного пункта в другой можно определять и через длину маршрута, и через время в пути, и через оплату проезда, если дорога платная. Главное, нужно проехать оптимальным способом.
Как вы можете себе представить, задачку с пятью пунктами вполне можно решить ручным перебором. Проблема в том, что с каждой новой точкой перебирать придется в разы больше вариантов. Так, добавление шестой точки увеличивает количество вариантов в шесть раз, седьмой – еще в семь раз. Знающие математику, конечно, догадались, что для n точек будет n! вариантов комбинаций. И это все без учета дорожной ситуации и множества ограничений и требований, которые предъявляет к доставке современный город. К тому же классическая задача коммивояжера строит маршрут для одного человека, а ритейл сегодня должен строить их для десятков и сотен курьеров. И тут в игру вступают силы математики, вычислительные мощности и огромное количество данных. Конечно, вручную выполнить все эти расчеты и найти оптимальный маршрут невозможно – логисту необходима помощь алгоритмов.
Алгоритм Дейкстры и задача маршрутизации транспорта (VRP)
Самый известный (и он того заслуживает!) алгоритм поиска кратчайшего пути между точками (с определенными ограничениями) – это алгоритм Дейкстры. Его изобрел в 1959 году нидерландский ученый Эдсгер Вибе Дейкстра, получивший в 1972 году премию Тьюринга, по сути, «нобелевку» по информатике, за свой вклад в развитие языков программирования и многочисленные научные статьи, в том числе по теории графов. Именно графом проще всего представить задачу доставки.
Адреса клиентов и склады становятся вершинами графа, а пути между ними – ребрами, которые, конечно, имеют свою «цену», будь то длина маршрута или время в пути. Алгоритм «пробегает» по вершинам, проверяя все пути к ним и определяя минимальные из них. Так, если путь в точку по прямой «стоит» 10 единиц, а через другую точку 2 + 5 = 7, то алгоритм отбросит первый вариант и в результате выдаст вам стоимость 7! (Если, конечно, не найдется какой-то еще более «дешевый» путь – возможно, через другой адрес или через несколько других адресов.)
Как рассказывал сам Дейкстра, он разработал этот алгоритм всего за 20 минут во время похода по магазинам со своей невестой. Дейкстра задумался, как найти кратчайший путь между двух городов и, когда они остановились выпить по чашечке кофе, составил алгоритм в голове, без бумаги и карандаша.
Через три года вышла публикация. Все описание проблемы и алгоритма уместилось на трех страницах. У алгоритма есть свои ограничения. В частности, он не работает с отрицательными «ценами» дорог и может долго искать кратчайший путь до удаленной точки, так как для его вычисления алгоритм «бежит» из точки А по всем направлениям, пока одно из них не приведет ко встрече с целевой точкой Б. Тем не менее именно его модификации используются во многих картах.
Доставка товаров – это не только задача поиска кратчайших маршрутов, ведь нужно учитывать и сам товар. Так родилась задача маршрутизации транспорта, которая лежит на пересечении задачи коммивояжера и задачи об упаковке рюкзака (как запихнуть как можно больше «ценных» вещей, если место ограничено). В реальной жизни гораздо больше параметров, чем простая «цена» дороги, но, как ни крути, именно с нее все и начинается.
Начнем с решения проблемы прогнозирования пробок. Чем больше данных, тем лучше будет прогноз. Где взять достаточно данных? Например, Яндексу помогает, с одной стороны, большой опыт в картографии, а с другой – данные сервисов (например, пользователей навигатора), которые могут использоваться и в задаче маршрутизации коммерческого транспорта. Для точного прогноза пробок на следующий день Яндекс.Маршрутизация анализирует исторические данные на всех участках маршрута.