Рост электронной коммерции и ожидания потребителей быстрой доставки оказали беспрецедентное давление на логистические компании с целью устранения трений и неэффективности в логистике последней мили. «Последняя миля» обычно относится к доставке товаров из транспортного узла (например, депо) до конечного пункта доставки, такого как ваш дом. Этот последний этап является самым дорогостоящим для логистических компаний, на него приходится почти 28% затрат на доставку.

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

Коммивояжер и Н.П. Трудные проблемы

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

Решение коммивояжера - это NP-сложная задача, а это означает, что не существует «быстрого» решения (быстрое означает алгоритм с полиномиальным временем). Точный алгоритм будет включать в себя поиск всех перестановок и комбинаций маршрутов и сравнение каждого из них для извлечения кратчайшего маршрута. Алгоритм «Хельда-Карпа» может использоваться для точного решения задачи коммивояжера с использованием дополнительных путей и методов динамического программирования. Даже в этом случае такой алгоритм может решить только небольшое количество точек в разумные сроки. Любое увеличение количества точек приведет к экспоненциальному увеличению времени вычислений. Таким образом, при практическом использовании в реальном мире мы используем комбинацию приближенных алгоритмов для приближения наилучшего пути с точностью до 1% от оптимального точного решения.

Проблема с маршрутизацией автомобиля

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

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

Алгоритм сбережений Кларка Райта

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

  • Создайте изначально осуществимое решение, назначив каждое транспортное средство клиенту или местоположению.
  • Для всех пар локаций мы рассчитываем экономию при присоединении к ним, и складываем список сбережений в порядке убывания.
  • Мы берем каждый вспомогательный путь из верхней части списка сбережений и присоединяемся к другим вспомогательным путям, если не превышена максимальная вместимость транспортного средства.
  • Мы повторяем предыдущий шаг до тех пор, пока не будет рассмотрен весь список сбережений или пока ограничения емкости не позволят объединить дополнительные пути.

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

Алгоритм оптимизации муравьиной колонии

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

Google OR-инструменты

Как мы можем создать программное приложение, которое решает проблему маршрутизации транспортных средств и использует широкий спектр алгоритмов оптимизации? Оказывается, мы можем использовать пакет Google OR-tools для решения нашей логистической задачи последней мили.

В нашем примере предметной области мы сгенерируем несколько пунктов отправления и депо в непосредственной близости от центра Сиднея. Затем наши автомобили отправятся из депо, посетят каждое из этих мест и заберут груз определенного веса. В нашей задаче мы ограничиваем грузоподъемность каждого автомобиля до 15 кг, и у нас есть максимальный парк автомобилей в 10 грузовиков.

Этот проект будет состоять из простого внутреннего сервера Django и внешнего интерфейса, созданного с помощью React.js. Здесь у нас всего 2 конечных точки. Первая конечная точка просто генерирует несколько адресов, а вторая конечная точка запускает алгоритм маршрутизации емкостных транспортных средств в Google OR-tools. Мы решили использовать описанный выше алгоритм экономии, известный своим относительно быстрым временем вычислений. Входные данные для такого алгоритма включают матрицу расстояний, которая рассчитывается с использованием API матрицы расстояний Google, другие параметры включают список требований к весу в каждом заданном месте (сгенерированный случайным образом) и ряд ограничений, включая максимальное количество транспортных средств и максимальная вместимость каждого автомобиля.

Для внешнего интерфейса мы просто используем библиотеку javascript Google Maps для визуализации местоположений и маршрутов. Мы просто наносим точки доставки на карту, а затем рассчитанные маршруты отображаются в виде полилиний с цветовой кодировкой. Мы также можем видеть маршруты для каждого отдельного транспортного средства и их вместимость в каждом месте. По мере того как мы добавляем все больше и больше точек к проблеме, решение может быть получено только в том случае, если мы также увеличим размер автопарка. Например, если мы ограничим автопарк 3 автомобилями, мы не сможем проложить оптимальные маршруты для 20+ локаций с грузоподъемностью 15 кг.

Код этого проекта можно найти здесь и здесь.

Улучшение кластеризации

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

Будущие приложения

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