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

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

ISSN 1812-7320

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

ИФ РИНЦ = 0,940

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

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

---

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

В статье рассматривается задача VP_М поиска квазиоптимальных маршрутов для доставки заказов различным клиентам автомобильным транспортом, выполненная по заказу российской компании, занимающейся производством и доставкой некоторой химической продукции. Была разработана математическая модель для поиска квазиоптимальных маршрутов, в основу которой легли модели известных задач: задача с учетом вместимости транспортного средства маршрутизации (CVRP), задача маршрутизации с учетом вместимости и размещения трехмерного груза в транспортное средство (3DBPСG), задача маршрутизации с временными интервалами (VRPTW), задача маршрутизации с множеством депо (MDVRP), задача маршрутизации с раздельной доставкой (SDVRP), задача маршрутизации с возвратом заказов (VRPPD); задача маршрутизации EVRP. При этом учитывались такие практические ограничения, как вместимость транспортных средств, временные интервалы, раздельная доставка заказов клиентам, различная вместимость транспортных средств, возможность возврата заказа клиентами. Кроме того, в модели вошли такие параметры, как возможность проезда по платным дорогам, стоимость бензина и арендная плата за транспорт. Одновременно при поиске маршрутов решалась задача поиска квазиоптимальной трехмерной упаковки заказов внутри автомобильного транспорта. Известно, что задачи маршрутизации и задачи трехмерной упаковки относятся к трудным задачам дискретной оптимизации. Для задачи VP_М разработан метаэвристический алгоритм ACР-VP_М, в основу которого легли модифицированный алгоритм муравьиной колонии, основанный на популяции, и эволюционный алгоритм (1,4)-ЕА, базирующийся на эволюционной стратегии (?, ?)-EA.

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

0 KB

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

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

основанный на популяции

эволюционный алгоритм (1

4)-еа

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

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

1. Venkatesan S.R., Logendran D., Chandramonah D. Optimization of capacitated vehicle routing problem using PSO. International Journal of Engineering Science and Technology (IJEST). 2011. vol. 3 (10). P. 7469–7477.

2. Gendreau M., Iori M., Laporte G., S. Martello A tabu search algorithm for a routing and container loading problem . Transportation Science. 2006. vol. 40. no. 3. P. 342–350.

3. Schmid V., Doerner Karl F. Gilbert L. Rich Routing Problems Arising in Supply Chain Management. European Journal of Operational Research. 2013. vol. 224. no. 3. P. 435–448.

4. Ramalingam A., Vivekanandan K. Genetic Algorithm based Solution Model for Multi-Depot Vehicle Routing Problem with Time Windows. International Journal of Advanced Research in Computer and Communication Engineering. 2014. vol. 3 (11). P. 8433–8439.

5. Archetti C., Hertz A., Speranza M.G. A tabu search algorithm for the split delivery vehicle routing problem . Transportation Science. 2006. no. 40. P. 64–73.

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

7. Валеева А.Ф., Гончарова Ю.А., Валеев Р.С. Об одном подходе к решению задач операционного планирования по доставке однородной продукции различным клиентам. Часть 1 // Информационные технологии. 2016. Т. 22. № 10. С. 741–746.

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

9. Валеева А.Ф., Гончарова Ю.А., Валеев Р.С. Задачи маршрутизации при транспортировке: оптимизация доставки однородного груза различным клиентам // Логистика и управление цепями поставок. 2019. № 5 (94). Ч. 2. С. 26–40.

10. Guntch M., Middendorf M. Applying Population Based ACO to Dynamic Optimization Problems. Proc. 3rd Int. Workshop (ANTS 2002). Lecture Notes in Computer Science. 2002. vol. 2463. Р. 111–122.

11. Кочетов Ю.А., Хмелев А.В. Гибридный алгоритм локального поиска для задачи маршрутизации разнородного ограниченного автопарка О сравнении некоторых эволюционных алгоритмов // Дискретный анализ и исследование операций. 2015. Т. 22. № 5. С. 5–29.

Доставка заказов клиентам в определенные сроки предполагает решение двух задач: поиск оптимального маршрута доставки и оптимальное размещение заказов (3DBPСG) в имеющемся транспорте. Первая задача позволяет сэкономить транспортные расходы компании, занимающейся перевозками, вторая – экономить ресурсы, в частности число единиц используемого транспорта для осуществления перевозок. Поскольку задачи маршрутизации и задачи трехмерной упаковки являются трудными задачами дискретной оптимизации, для их практической реализации используются различные эвристики. Предлагается к рассмотрению задача VP_М, возникшая в компании, занимающейся доставкой заказов химической продукции в различные регионы России. Компания арендует автомобильные транспортные средства различной вместимости, имеет ряд депо. Перед отправкой заказ размещается в емкости, имеющей форму параллелепипеда, все автомобильные транспортные средства, загруженные заказом различных клиентов, выезжают из депо, а после обслуживания клиентов возвращаются обратно в депо, при этом по пути следования допускается остановка в определенные часы. Требуется определить наилучшие маршруты доставки заказов различным клиентам с наименьшими расходами (аренда автомобиля, платные дороги), а также организовать рациональную упаковку заказов в автомобильные транспортные средства.

Математическая модель задачи VP_М

В основу математической модели рассматриваемой задачи VP_М легли ограничения из следующих известных задач: задача маршрутизации с учетом вместимости автомобильных транспортных средств (CVRP) [1]; задача маршрутизации с учетом упаковки заказов (3L-CVRP) [2]; задача маршрутизации с временным интервалом (VRPTW) [3], задача маршрутизации с различными депо (MDVRP) [4], задача маршрутизации с возможностью доставки заказа в одном транспортном средстве различным клиентам (SDVRP) [5], задача маршрутизации с возможностью возврата заказа по требованию клиента (VRPPD) [6]; задача маршрутизации EVRP [7]. Обозначения для описания задачи VP_М, являющейся модификацией задачи EVRP, введенные в перечисленных задачах, сохраняются.

Примем в качестве модели дорог, по которым заказ будет доставлен различным клиентам, ориентированный граф, в котором вершины делятся на следующие непересекающиеся подмножества: подмножество вершин (города доставки заказа) Vc = {1,…,n} и подмножество вершин (депо) Vh = {0, n + 1,…,n + k}. Обозначим через mu – количество автомобильных транспортных средств, находящихся в депо (); ru – число автомобильных транспортных средств, расположенных в депо; известны характеристики кузова автомобильных транспортных средств и их вместимости: Wv – ширина кузова автомобильного транспортного средства v, Lv – длина кузова автомобильного транспортного средства v, Hv – высота, Qv – вместимость. Заказ размещается в емкости, имеющие форму параллелепипеда, известны их характеристики: lpkp – длина емкости kp, wpkp – ширина, hpkp – высота, mpkp – масса емкости kp (Itempar – количество емкостей). Известны потребности клиентов , имеется информация о заказе, который требуют возвратить клиенты: . Компания имеет затраты costpetrolv на бензин, costrentv – затраты на арендную плату автомобильных транспортных средств. По пути следования могут встретиться платные дороги, тогда в транспортные расходы включается и величина costroadij. Кроме того, возможна остановка транспортного средства в определенные промежутки времени [ai, bi]. Пусть cij – время между посещением клиентов, si – время, в течение которого выполняется заказ для некоторого клиента. При этом вводится денежный штраф penalty_timei за обслуживание после заданного времени bi; wiv – время, в которое начинает обслуживаться клиент с прибывшим для него заказом; tiv – время, в которое автомобильное транспортное средство прибывает из депо к клиенту. Решение задачи – переменная xijv , равная 1 при условии, что транспортное средство прибывает из депо от клиента i к клиенту j, и 0 в противном случае. Количество заказа, доставляемого транспортным средством для каждого клиента, – это величина . Если есть заказ, который следует принять обратно от клиента, то его количество вычисляется как . Вводится денежный штраф penalty_pack_ν за маршрут, в котором не удалось рационально разместить заказы клиентов в транспортное средство. Для того чтобы знать, помещается ли заказ в транспортное средство, вводится параметр fpack_ν: при выполнении условия заказ помещается в транспортное средство; если fpack_ν > 1, то заказ не помещается.

Математическая модель задачи VP_М:

Найти наименьшие транспортные расходы:

(1)

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

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

Для реализации условия (11) решается задача трехмерной упаковки 3DBPСG, цель которой – минимизация количества транспортных средств с укомплектованными в них палетами с емкостями:

(12)

где P – множество всевозможных расположений емкостей. При этом выполняются следующие ограничения: емкости не находятся за границей палеты; стороны емкостей параллельны граням палеты; стороны палеты параллельны граням области загрузки транспортного средства; палеты в одном транспортном средстве взаимно не перекрываются; палеты не выходят за пределы транспортного средства; максимальная высота Hmax укомплектованных на палете емкостей не превосходит максимально допустимую высоту hpod max палеты:

; (13)

стороны емкостей параллельны граням области загрузки транспортного средства; масса укомплектованных на палете емкостей не превышает допустимой вместимости qpod палеты: , где mi – масса i-ой емкости. Практически эффективность трехмерной упаковки принято оценивать следующим параметром – коэффициентом упаковки:

где – размеры емкостей, имеющих форму параллелепипеда, W – ширина кузова размещения транспортного средства (параллелепипед), соответственно, L – длина и Н – высота.

Упаковка палет с емкостями в транспортное средство осуществляется с учетом центра масс, причем при погрузке следует учитывать, что центр масс укомплектованного автомобильного транспортного средства должен быть в цилиндрической области допущения G:

, , (14)

где x, y, z – координаты емкости в транспортном средстве, R – радиус основания цилиндра, h1, h2 – границы допустимой высоты области G [8].

Следует так разместить палеты с емкостями, чтобы минимизировать девиацию центра тяжести упакованного транспортного средства:

(15)

где в формуле (15) используются обозначения (Xцт, Yцт, Zцт) для координат центра масс заказов, упакованных в транспорт для отправки;

(16)

(17)

(18)

(19)

Метод решения задачи VP_ М

Для решения задачи VP_М разработан алгоритм ACР-VP_М, являющийся модификацией алгоритма P-ACO-EVRP [9] и алгоритмов [10, 11], для решения задачи 3DBPСG – алгоритм (1,4)-ЕА, являющийся модификацией известного эволюционного алгоритма (μ, λ)-EA [11].

Общая схема алгоритма ACР-VP_М

Шаг 1. Преобразовать исходный ориентированный граф (модель дорог) в матрицу расстояний между клиентами.

Шаг 2. Преобразовать матрицу расстояний в матрицу стоимостей.

Шаг 3. Распределить заказы клиентов по депо и транспортным средствам.

Шаг 4. Поиск квазиоптимальных маршрутов (по критерию минимальной стоимости):

Шаг 4.1. Формировать маршруты с учетом ограничений (1)–(11).

Шаг 4.2. Сформировать популяцию квазиоптимальных маршрутов из маршрутов, полученных на шаге 4.1.

Шаг 4.3. Получить таблицу размещения заказов по транспортным средствам (алгоритм (1,4)-ЕА с учетом (12)–(19)).

Шаг 4.4. Преобразовать популяцию квазиоптимальных маршрутов.

Было разработано программное обеспечение на языке C++, реализующее алгоритм ACР-VP_М. Приведем численный эксперимент, проводимый на тестах, в которые включена следующая информация: местоположения депо и клиентов (координаты), спрос каждого клиента, вместимости арендуемого компанией автомобильного грузового транспорта. Разработанный алгоритм сравнивался с результатами алгоритма P-ACO-EVRP. Результаты экспериментов приведены в табл. 1. Для корректного сравнения результатов алгоритмов в качестве целевой функции взята длина искомого маршрута.

Таблица 1

Сравнение результатов работы алгоритмов ACР-VP_М и P-ACO-EVRP

Как видно из результатов эксперимента, целевая функция – длина маршрута – при количестве клиентов 200, 399, 420, 480 оказалась лучше в модифицированном алгоритме ACР-VP_М по сравнению с алгоритмом P-ACO-EVRP.

Следующий эксперимент (табл. 2) проводился для того, чтобы оценить вычислительные возможности разработанного алгоритма ACР-VP_М в зависимости от количества клиентов, подавших заявки на доставку заказа. При проведении численного эксперимента использовались тесты с различным количеством клиентов из международной библиотеки тестов OR-Library для тестирования задач исследования (http://people.brunel.ac.uk/~mastjjb/jeb/info.html).

Таблица 2

Среднее время выполнения алгоритма ACР-VP_М

Заключение

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

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

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