Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Юсупова Н.И. 1 Валеев Р.С. 1

---

1 Уфимский государственный авиационный технический университет

Статья посвящена задаче поиска наилучших маршрутов при доставке грузов различным клиентам, которая относится к классу задач маршрутизации (VRP), являющихся одними из важных задач операционного уровня в транспортной логистике. Рассматривается задача маршрутизации для доставки груза автомобильными транспортными средствами различным клиентам с возможностью дозагрузки недостающего груза в специализированных пунктах, в которой, в отличие от известных постановок, дополнительно решается задача размещения грузов в автомобильные транспортные средства (решается задача трехмерной упаковки). При этом наличие таких пунктов позволяет не тратить время на обратный путь в депо за грузом для очередного клиента. Приведена математическая модель рассматриваемой задачи, учитывающая следующие ограничения: вместимость транспортного средства, возможность доставки груза клиентам различными транспортными средствами, стоимость арендуемых транспортных средств, стоимость бензина. Поскольку задачи маршрутизации, как известно, являются труднорешаемыми задачами комбинаторной оптимизации, для их практического применения разрабатываются различные современные метаэвристические методы. В статье приводится алгоритм решения рассматриваемой задачи, базирующийся на эволюционных стратегиях. В частности, приведены две реализации эволюционных стратегий (1 + 3)-ЕА и (1 + 4)-ЕА, а также показана часть результатов проведенных численных экспериментов, показан пример практической задачи маршрутизации.

Статья в формате PDF

0 KB

задачи маршрутизации

математические модели задач маршрутизации

задача маршрутизации с возможностью дозагрузки

задача трехмерной упаковки

эволюционные стратегии

1. Toth P., Vigo D. The Vehicle Routing Problem. Philadelphia, Society for Industrial and Applied Mathematics. 2002. 386 p.

2. Aby K. Abraham, Bobin Cherian Jos, Georgekutty S. Mangalathu. The Pickup And Delivery Vehicle Routing Problem For Perishable Goods In Air-Cargo Industry. International Journal of Emerging Technology and Advanced Engineering. 2012. V. 2. №12. P. 790–794.

3. Andres Figliozzi M. The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Research Part E: Logistics and Transportation Review. 2012. V. 48. P. 616–636.

4. Dhahri A., Zidi K., Ghedira K. A Variable Neighborhood Search for the Vehicle Routing Problem with Time Windows and Preventive Maintenance Activities. Electronic Notes in Discrete Mathematics. 2015. V. 47. P. 229–236.

5. Валеева А.Ф, Янтурин И.А., Валеев Р.С. Об одной задаче доставки груза различным клиентам с возможностью дозагрузки // Информационные технологии. 2020. Т. 26. № 1. С. 9–15.

6. Юсупова Н.И., Валеев Р.С. Рациональное размещение грузов в контейнеры с учетом их физических характеристик с помощью роботизированного комплекса // Информационные технологии. 2011. № 5. С. 30–36.

7. Борисовский П. А., Еремеев А. В. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. № 2. С. 3–9.

При принятии логистических решений компаниям, занимающимся транспортировкой некоторой продукции, требуется решать задачи так называемого операционного уровня. Одними из таких задач являются задачи поиска рациональных маршрутов различными транспортными средствами маршрутизации (VRP) [1]. Существует множество различных постановок таких задач, которых объединяет, прежде всего, наличие парка транспортных средств (депо) и клиентов, спрос которых необходимо удовлетворить. При этом любой искомый маршрут должен начинаться и заканчиваться в депо, задана матрица неотрицательных стоимостей (расстояний) между клиентами. Необходимо определить такой маршрут доставки заказов автомобильными транспортными средствами всем клиентам, чтобы общие затраты были минимальными. Известны различные постановки задач маршрутизации с ограничениями, которые встречаются при решении реальных задач. Целью исследования является решение практической задачи маршрутизации с возможностью дозагрузки недостающего груза в специализированных пунктах с предварительным размещением груза в автомобильные транспортные средства (решается задача трехмерной упаковки, 3DBPP).

Постановка задачи и математическая модель

В статье рассматривается задача маршрутизации для доставки груза различным клиентам с возможностью дозагрузки и его размещения в автомобильные транспортные средства (MVRPSF), в основу которой легли следующие известные задачи [2–4]: задача маршрутизации с учетом вместимости транспортного средства (CVRP); задача маршрутизации с условием обслуживания клиентов одновременно несколькими транспортными средствами (SDVRP); задача маршрутизации с возможностью дозагрузки груза в специализированных пунктах или депо (VRPSF).

Задача маршрутизации MVRPSF возникла в компании, занимающейся доставкой оборудования для установки освещения в различных регионах России арендуемыми автомобильными транспортными средствами одинаковой вместимости, находящимися в депо. На пути следования к клиентам имеются пункты дозагрузки, в которых автомобильные транспортные средства могут пополнять недостающий запас оборудования, не возвращаясь в депо. Известны данные о спросе клиентов на оборудование, о времени обслуживания клиентов (населенные пункты), о максимально разрешенном времени маршрута, о стоимости в единицу времени пройденного пути автомобильного транспортного средства (в стоимость входят стоимости аренды и бензина). Следует найти маршрут доставки оборудования с минимальными общими затратами при выполнении следующих условий: все пути для доставки груза начинаются в депо; после выполнения заказов автомобильные транспортные средства должны возвратиться обратно в депо; весь объем груза, доставляемого различным клиентам, не должен превосходить вместимости транспортных средств (CVRP); требования клиентов на поставку груза разделяются между несколькими транспортными средствами (SDVRP).

В задаче MVRPSF маршруты между клиентами представляются в виде графа. Вершины графа разбиваются на два непересекающихся множества, одно из которых I – множество клиентов (, где вершина 0 – это депо; i, j – номера клиентов; ); другое множество F – это пункты дозагрузки; α – индекс, используемый для описания пунктов дозагрузки или депо, Fα – множество вершин, соответствующее потенциальным посещениям пунктов дозагрузки; F0 – депо, используемое в качестве пункта для дозагрузки; nα – количество дополнительных пунктов для дозагрузки; – количество пунктов в сети; dij – расстояние либо между клиентами i и j, либо между клиентами и депо, либо между дозагрузочными пунктами; τij – время в пути между пунктами i и j; m – количество используемых транспортных средств; Qv – вместимость транспортных средств v; – максимальное количество разрешенного в транспортном средстве v остатка груза до его пополнения, < Qv; cos trent – стоимость аренды транспортного средства в единицу времени; cos tpetrol – затраты на бензин транспортного средства; Tv – максимально разрешенное время маршрута для транспортного средства v; qi – спрос клиента i; piv – время обслуживания клиента i транспортным средством v время загрузки в дозагрузочных пунктах, либо в депо.

В качестве решения выступает xvij – переменная, принимающая значение 1, если автомобиль v перемещается из депо в направлении от клиента i к клиенту j, и 0 в противном случае. Используемые переменные: – время начала обслуживания клиента j; yjv – загрузка остатка заказанного груза непосредственно перед посещением клиента j; количество заказа, доставляемого клиенту i автомобилем v;

Математически задача MVRPSF формулируется следующим образом [5]

(1)

при следующих ограничениях:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

где

Приведем известные постановки задач CVRP и SDVRP, условия которых применялись в задаче MVRPSF.

Требуется найти маршрут минимальной стоимости (CVRP):

(10)

при выполнении следующих условий:

(11)

(12)

(13)

(14)

(15)

;

.

В задаче SDVRP при поиске маршрута минимальной стоимости (10), кроме условий (12)–(15), используются следующие условия:

маршрут включает каждую вершину не менее одного раза:

(16)

исключаются замкнутые маршруты:

(17)

Для решения задачи MVRPSF с учетом перечисленных условий (11)–(17) был разработан алгоритм VRPSF на базе эволюционной стратегии [4], который находит рациональный маршрут доставки грузов и осуществляет их предварительное размещение в кузове автомобильных транспортных средств с учетом центра тяжести размещаемых грузов (решается задача трехмерной упаковки 3DBPP [6]).

Для применения алгоритма VRPSF следует определиться с кодировкой решения – маршрута, начинающегося и заканчивающегося в депо. В данном алгоритме кодировка искомого решения – маршрута представляется в виде перестановки целых чисел 1,...,n. Приведем общую схему алгоритма VRPSF решения задачи (1)–(9).

Общая схема алгоритма VRPSF

Шаг 0. Инициализация переменных

Шаг 1. Загрузка груза в ТС v (решается 3DBPP)

Шаг 2. Цикл по количеству итераций

Если маршрута нет, то генерировать λ маршрутов

иначе

Цикл по λ

Конец_цикла_по_λ

Конец_ если_маршрута_нет

Цикл по количеству маршрутов

K = Qv (решается 3DBPP)

Цикл по количеству клиентов n

Пока спрос i-го клиента qi не будет удовлетворен, выполнить:

Если в автомобиле v все грузы i-го клиента размещены (т.е. спрос

qi ≤ K),

то спрос i-го клиента удовлетворен

иначе

Если qi > Qv, то

Поиск ближайшего пункта дозагрузки от клиента

иначе

Поиск наименьшего расстояния до пункта

дозагрузки и от пункта дозагрузки до следующего клиента

Конец _Если

Если найденный пункт дозагрузки депо и если есть

незадействованные автомобили,

то новый автомобиль вводится в маршрут

Добавление найденного пункта дозагрузки в маршрут

K = Qv (решается 3DBPP)

Конец_если

Конец_цикла_пока

Конец цикла по количеству клиентов

Конец_цикла_по_количеству_маршрутов

Если выполняются ограничения (1)-(9), то сравнение стоимости

нового и текущего маршрутов и выбор наилучшего маршрута,

иначе маршрут не существует

Конец_цикла_по_итерациям

Вывод маршрута и получение карты размещения грузов в ТС

Численные результаты

Для исследования эффективности разработанного алгоритма VRPSF проводились численные эксперименты. При этом в основу реализации алгоритма VRPSF были положены эволюционные стратегии (1 + 3)-ЕА и (1 + 4)-ЕА [7]. Приведем результаты одного из экспериментов, для которого были сгенерированы тестовые наборы данных: расстояния между клиентами, между клиентами и пунктами дозагрузки, величины спроса соответственно для 20 клиентов, пункты дозагрузки варьировались от 1 до 5. В тестовом наборе данных KnEq обозначение Kn – это количество клиентов (n = 20); – количество пунктов дозагрузки (nα = 0,..,5); Eq – количество прогонов (q = 7); 400I и 500I – количество итераций алгоритмов. Каждый тестовый набор прогонялся семь раз. В таблице приведено сравнение средних стоимостей маршрутов для 20 клиентов и пяти дозагрузочных пунктов лишь для количества итераций 400I, на рисунке, а, б, приведены диаграммы для результатов таблицы и среднего времени работы алгоритмов (1 + 3)-EA и (1 + 4)-EA для 400I и 500I.

Как показали численные эксперименты, лучший результат показал алгоритм (1 + 4)-EA, алгоритм (1 + 3)-EA затрачивает меньше вычислительного времени, при этом на стоимость маршрута оказывает влияние количество пунктов дозагрузки: она меньше при их количестве, равном пяти (в данном эксперименте).

Сравнение средних стоимостей маршрутов для 20 клиентов

Заключение

В представленной статье рассмотрена практическая задача маршрутизации с возможностью дозагрузки и приведены ее математическая модель и алгоритм, позволивший получить рациональный маршрут доставки грузов клиентам с возможностью дозагрузки и с предварительным размещением их в ТС, который базируется на эволюционных стратегиях (1 + 3)-EA и (1 + 4)-EA. Для проведения численного эксперимента были сгенерированы тестовые наборы данных для 20, 25, 30, 35 и 40 клиентов. В статье приведены результаты численных экспериментов для 20 клиентов, при этом лучшие по целевой функции решения были получены алгоритмом (1 + 4)-EA.

Работа поддержана грантом РФФИ 18-07-00193-а.

Библиографическая ссылка