Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

OPERATIONAL LEVEL PROBLEMS IN TRANSPORT LOGISTICS

Yusupova N.I. 1 Valeev R.S. 1
1 Ufa State Aviation Technical University
Статья посвящена задаче поиска наилучших маршрутов при доставке грузов различным клиентам, которая относится к классу задач маршрутизации (VRP), являющихся одними из важных задач операционного уровня в транспортной логистике. Рассматривается задача маршрутизации для доставки груза автомобильными транспортными средствами различным клиентам с возможностью дозагрузки недостающего груза в специализированных пунктах, в которой, в отличие от известных постановок, дополнительно решается задача размещения грузов в автомобильные транспортные средства (решается задача трехмерной упаковки). При этом наличие таких пунктов позволяет не тратить время на обратный путь в депо за грузом для очередного клиента. Приведена математическая модель рассматриваемой задачи, учитывающая следующие ограничения: вместимость транспортного средства, возможность доставки груза клиентам различными транспортными средствами, стоимость арендуемых транспортных средств, стоимость бензина. Поскольку задачи маршрутизации, как известно, являются труднорешаемыми задачами комбинаторной оптимизации, для их практического применения разрабатываются различные современные метаэвристические методы. В статье приводится алгоритм решения рассматриваемой задачи, базирующийся на эволюционных стратегиях. В частности, приведены две реализации эволюционных стратегий (1 + 3)-ЕА и (1 + 4)-ЕА, а также показана часть результатов проведенных численных экспериментов, показан пример практической задачи маршрутизации.
The article is devoted to the problem of finding the best routes for delivering goods to various customers. It belongs to the class of Vehicle Routing Problems (VRP), one of the important problems of the operational level in transport logistics. We consider the routing problem for the delivery of goods by automobile vehicles to various customers with the possibility of reloading the missing goods in specialized points, which, in contrast to the well-known statements, additionally solves the problem of the placing goods in automobile vehicles (the three-dimensional packing problem is solved). Moreover, the presence of such points allows not to waste time on the return trip to the depot for goods for the next client. The mathematical model of the problem is considered, it takes into account the following restrictions as: vehicle capacity, the ability to deliver goods to customers by various vehicles, the cost of rented vehicles, the cost of gasoline. Since routing problems are known to be hard to be resolved by combinatorial optimization, various modern metaheuristic methods are being developed for their practical application. The article provides the algorithm for resolving the problem that is based on evolutionary strategies. In particular, two implementations of the evolutionary strategies (1 + 3)-ЕА and (1 + 4)-ЕА are given, and also a part of the results of numerical experiments is shown, the example of a practical routing problem is shown as well.
routing problems
mathematical models of routing problems
vehicle routing problem with satellite facilities
three-dimensional packing problem
evolutionary strategies

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

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

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

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

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

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

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

ysup11.wmf (1)

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

ysup12.wmf (2)

ysup13.wmf (3)

ysup14.wmf (4)

ysup15.wmf (5)

ysup16.wmf (6)

ysup17.wmf (7)

ysup18.wmf (8)

ysup19.wmf (9)

ysup20.wmf

где

ysup21.wmf

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

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

ysup22.wmf (10)

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

ysup23.wmf (11)

ysup24.wmf (12)

ysup25.wmf (13)

ysup26.wmf (14)

ysup27.wmf (15)

ysup28.wmf;

ysup29.wmf.

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

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

ysup30.wmf (16)

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

ysup31.wmf (17)

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

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

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

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

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

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

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

иначе

Цикл по λ

ysup34.wmfysup35.wmf

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

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

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

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

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

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

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

qi ≤ K),

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

иначе

Если qi > Qv, то

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

иначе

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

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

Конец _Если

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

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

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

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

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

Конец_если

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

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

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

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

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

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

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

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

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

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

Ys1.tif Ys1b.tif

а) б)

Диаграммы для результатов таблицы и среднего времени работы алгоритмов (1 + 3)-EA и (1 + 4)-EA для 400I и 500I: а) cравнение средних стоимостей маршрутов; б) среднего времени работы алгоритмов для 20 клиентов

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

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

 

(1 + 3)-ЕА(400I)

(1 + 4)-ЕА(400I)

K25L5

3778,518

2673,211

K25L4

3654,789

2565,561

K25L3

3586,780

3335,722

K25L2

4063,111

3909,575

K25L1

4256,881

4034,111

K25L0

4733,366

4583,175

Заключение

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

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