УДК 004.021
Хубеджев Д.П., Ситникова О.Д. Формализация задачи логистики поставок и разработка ПО для формирования оптимальных маршрутов. В статье представлен модифицированный метод Кларка-Райта для решения задач развозки. Модификации позволили реализовать данный метод для работы с более точными данными, полученными с помощью сервисов Google Maps.
Ключевые слова: логистика, задача развозки, метод Кларка-Райта, маршрут, Google Maps.
Актуальность проблемы выражена в динамичном развитии розничной торговли, связанная с постоянно изменяющимися факторами внешней среды и обострением конкуренции. Товародвижение является достаточно сложной системой, динамически изменяющейся под влиянием внутренних и внешних факторов, имеющая диверсификационные взаимодействия. Таким образом, оптимизации и рационализации товародвижения не всегда достигают наивысших результатов, из-за сложности получения или переработки информации, способности к принятию решений. Преобразования логистических систем товародвижения розничных торговых предприятий в последние годы в значительной степени связаны с трансформацией отношений в контексте элементов логистической системы.
Целью работы является оптимизация алгоритма Кларка-Райта для более точных данных, полученных с помощью сервисов Google Maps.
На сегодняшний день, существующие программные системы заточены под определенные особенности предприятий. При этом, программные продукты малоизвестны и в общем доступе их найти или невозможно, или крайне маловероятно. Однако продукты, что попали в сеть не являются Open Source проектами, а их функционал или не соответствуют современным платформам, или имеет ограниченный функционал.
Из этого следует, что существующие программные проекты не соответствуют критериям предполагаемого продукта, либо перенасыщены дополнительными функциями.
Особенности:
узконаправленность;
богатый функционал;
специализированный интерфейс.
Достоинства:
индивидуальность;
возможность подключения дополнительных модулей;
возможность подключения сторонних функциональных блоков;
узкоспециализированность продукта.
Недостатки:
закрытый программный код;
коммерческий продукт;
низкая производительность
высокая стоимость;
узкая специализация.
Задача развозки – это транспортная задача по доставке мелкопартионных грузов из распределительного центра, например, оптовой базы, склада, грузового терминала и пр., множеству получателей, расположенных в районе развозки. Данная задача включает в себя построение радиальных и кольцевых маршрутов для минерализации финальной величины длинны. Когда объем, запрашиваемый получателем, больше или равен грузоподъемности автомобиля, используются радиальные маршруты,. По математической модели рассматриваемая задача является задачей нескольких коммивояжеров, а значит относится к классу NP-трудных.
Метод Кларка-Райта является одним из алгоритмов, решающих задачу развозки. В данном алгоритме вводится понятие выигрышей для оценки операций слияния маршрутов. Выигрыш являет собой меру сокращения стоимости, достигаемую благодаря комбинированию двух небольших маршрутов в один. Из этого следуют такие достоинства: простота, надежность и гибкость, при погрешности решения не превосходящей в среднем 5-10%.
Так же недостатком данного алгоритма является получение пути из одной точки в другую и обратно, как одинакового расстояния, что может не соответствовать действительности. Для решения данной проблемы в алгоритм были внесены модификации.
Суть метода заключается в пошаговом переходе к оптимальной схеме развозки с кольцевыми маршрутами. Для этого вводится понятие — километральный выигрыш.
На рисунке 1 показаны две схемы доставки.
На схеме доставке A отображается доставка грузов по радиальным маршрутам в пункты 1 и 2. В этом случае суммарный пробег автотранспорта равен:
LA = d01 + d10 + d02 + d20 |
(1) |
Схема доставки B предполагает доставку грузов по кольцевому маршруту в пункты 1 и 2. Тогда пробег автотранспорта составляет:
LB = d01 + d12 + d20 |
(2) |
|---|---|
Схема B, обычно дает лучший результат по пробегу, по сравнению со схемой A. При переходе к такой схеме рассчитывается километральный выигрыш:
S12 = LA − LB = d10 + d02 − d12 |
(3) |
В общем случае мы имеем такую формулу:
Sij = di0 + d0j − dij |
(4) |
Где:
а) Sij — километральный выигрыш, км;
б) d0i, d0j — расстояние между пунктами i и j и складом соответственно, км;
в) dij — расстояние между пунктами i и j, км.
Описать основную часть алгоритма можно в 6 шагах:
Шаг 1 — находим ячейку (i*, j*) с максимальным километральным выигрышем Smax на матрице километральных выигрышей:
Smax = maxi, jS(i,j) = S(i*,j*) |
(5) |
При поиске максимального элемента нужно учесть ряд условий:
а) точки i* и j* не входят в состав одного и того же маршрута;
б) точка i* или j* является начальным или конечным пунктом, того маршрута, в который он войдет, а другая точка не используется в других маршрутах;
в) точки i* и j* является начальным и конечным пунктом, тех маршрутов, которые они объединяют;
г) ячейка (i*, j*) или (j*, i*) не использовались ранее.
Если удалось найти такую ячейку, которая удовлетворяет трем указанным условиям, то переход к следующему шагу. Если нет, то к шагу 4.
Если точки i* и j* не использовались в других маршрутах, то создать новый.
Шаг 2 — проверить выполнения условия грузоподъемности на протяжении всего маршрута:
Q + q ≤ c |
(6) |
Где:
а) Q Q— общее количества груза требуемого маршрутом;
б) q — количество требуемого товара на добавляемую точку;
в) с — грузоподъемность транспорта.
Если условие выполняется, то переход к шагу 3, если нет – к шагу 1.
Шаг 3 — добавляем полученную точку в начало/конец маршрута и возвращаемся к шагу 1.
Шаг 4 — рассчитываем суммарное расстояние, которое необходимо пройти для покрытия всех маршрутов.
За основу реализованного алгоритма был взят алгоритм Кларка-Райта и были внесены в него оптимизации позволяющие сделать вычисления с помощью более реальных данных. Оптимизации сделаны не увеличивая общей сложности алгоритма, хотя и увеличивает общее количество шагов, которые должен сделать алгоритм. В связи с этим в основу алгоритма Кларка-Райта были добавлены дополнительные проверки, не уменьшающие эффективность и уменьшающие количество проходов в цикле, что бы покрыть затраты времени на большее количество шагов.
Сложность алгоритма равна:
O(N ) * (O(N2)+O(N)) = O(N3) + O(N2) = O(N3) |
(7) |
Такая сложность является более чем допустимой, так как задачи, имеющие такую сложность, могут обрабатывать довольно большие объёмы данных за допустимое время.
Данные о соответствии времени от размерности выборки отображены в таблице 1.
Таблица 1 – Форматирование страницы в статье
| Размерность выборки | Время |
| 100 заявок | До 1 секунды |
| 200 заявок | 7 секунд |
| 300 заявок | 34 секунд |
| 500 заявок | 4 минуты 22 секунды |
| 1000 заявок | 71 минута 24 секунды |
Результаты тестирования подтверждают расчеты и соответствует выведенной формуле сложности (см. формулу 7).
Был изучен и модифицирован метод Кларка-Райта для решения задач развозки. Модификации позволили реализовать данный метод для работы с более точными данными, полученные с помощью сервиса Googl Maps. Описан алгоритм с включенными в него модификациями и проведены тесты, показывающие, что с данными изменениями сложность алгоритма не увеличивается.
Используя данный алгоритм в реальной системе можно добиться уменьшения количества буферных складов и значительно уменьшить расходы на логистику. В перспективе для полноценной программной системы следует разработать сразу набор алгоритмов оптимизации логистики, проработав их взаимосвязь, для получения лучших результатов.
Гери, М. Вычислительные машины и труднорешаемые задачи / М. Гери, Д. Джонсон. — Москва: Мир, 1982 – 416 с.
Логистика [Электронный ресурс] // Википедия — Режим доступа: https://ru.wikiversity.org/wiki/Логистика — Загл. с экрана.
Навигационная система [Электронный ресурс] // Википедия – Режим доступа: https://ru.wikipedia.org/wiki/Навигационная_система — Загл. с экрана.
Метод Кларка-Райта. Оптимальное планирование маршрутов грузоперевозок [Электронный ресурс] // Инфостар — Режим доступа: https://infostart.ru/public/443585/ — Загл. с экрана.
Оценка сложности алгоритма [Электронный ресурс] // Хабр — Режим доступа: https://habr.com/post/104219/ — Загл. с экрана.
Руководство для разработчиков Google Maps Distans API [Электронный ресурс] // Google Maps APIs — Режим доступа: https://developers.google.com/maps/documentation/distance-matrix/intro?hl=ru#unit_systems — Загл. с экрана.