Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

INTEGER MULTINOMENCLATURE OPTIMIZATION VEHICLE ROUTING PROBLEM WITH RESTRICTIONS

Iakovleva T.A. 1
1 Ufa state aviation technical university, Ufa, Russia
The article is devoted to setting and solving an optimization routing problem which belongs to the VRP class. Characteristic features of the considered problem are variety of transported product assortment and different capacity constraints of different vehicles and their ability to deliver each type of product. The appropriate mathematical model is constructed. Three step heuristic procedure for solving the problem is developed. The existence of integer solutions is proved for an integer case of the problem, methods that allow to apply the three step procedure to obtain the exact solution of the problem are described.
routing
three step heuristic procedure
exact solution
Введение

Впервые задача маршрутизации транспортных средств при перевозке грузов была поставлена Г. Данцигом и Дж. Рамсером в 1959 году [4]. На сегодняшний день сформулирован целый класс задач VRP (Vehicle Routing Problem) [1; 5; 6], и он постоянно пополняется новыми задачами, призванными учесть реальные ограничения, возникающие в связи с развитием логистических процессов. Разработан ряд алгоритмов приближенного поиска оптимальных решений [5; 6] - для большинства задач нахождение точного решения является сложным в вычислительном отношении.

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

Поставленная задача относится к классу нелинейных оптимизационных задач и является обобщением двух известных задач - задачи коммивояжера и задачи о загрузке рюкзака. Тем самым рассматриваемая задача является более чем NP-трудной.

Постановка задачи

Пусть на базе имеются грузы k видов. Грузы необходимо доставить в n пунктов потребления (ПП), в j-й ПП необходимо доставить заданное количество груза i-го вида. Доставка груза осуществляется m транспортными средствами (ТС), каждый из которых характеризуется грузоподъемностью, транспортными затратами на единицу пути, а также указанием, какие виды грузов не разрешается перевозить данным ТС. Каждое ТС должно после одного рейса вернуться на базу.

Требуется организовать доставку грузов таким образом, чтобы суммарные расходы на транспортировку были минимальными.

Для формализации поставленной задачи введем следующие обозначения:

, ,  ‑ ПП, виды грузов, ТС,

Известные величины:

 Sp‑ грузоподъемность p-го ТС,

Lij ‑ вес груза i-го вида, который необходимо доставить в j-й ПП ( , ),

 ‑ множество грузов, недопустимых к перевозке p-м ТС,

 ‑ затраты на проезд p-го ТС на единицу расстояния,

 ‑ матрица расстояний между ПП и базой.

Пусть    ‑ минимальная из длин циклов, содержащих ПП из U и нулевой пункт.

Обозначим через  ‑ вес груза i-го вида, перевозимого p-м ТС в j-й ПП   , ).

Задача имеет следующий вид.

Найти числа  такие, что:

,  при          (1)

  (2)

 (3)

 (4)

Здесь  ‑ множество ПП, в которые груз доставляется p-м ТС.

Условие (1) отражает ограничения на использование ТС для перевозки определенных видов груза, условие (2) означает полное удовлетворение потребностей во всех ПП, условие (3) ‑ это ограничения грузоподъемностей ТС, целевая функция (4) ‑ стоимость перевозок.

Существование допустимого решения

Отдельной задачей, с которой приходится столкнуться при решении мультиноменклатурной оптимизационной задачи маршрутизации с запретами на перевозку, является проверка реализуемости перевозок.

Введем следующие обозначения:

 ‑ общий вес груза i-го вида, перевозимого p-м ТС,

 ‑ суммарная потребность в грузе i-го вида.

Рассмотрим вспомогательную систему уравнений и неравенств:

 (5)

 (6)

 (7)

 при  (8)

Очевидное необходимое условие совместности системы (5)-(8) , которое является и достаточным в отсутствии условия (8), в общем случае таковым не является. В то же время из совместности системы (5)-(8) следует допустимость задачи (1)-(4). Для того чтобы убедиться в этом, рассмотрим какое-нибудь решение системы (5)-(8). Для груза i-го вида определим две совокупности чисел:

; ;...;  (9)

; ; ...;   (10)

 по определению, как сумма потребностей в грузе i-го вида,  из уравнения (37). Получаем:

 (11)

По условию, .

План перевозок  можно определить как множество, которому одновременно принадлежат элементы  и .

  (12)

Проиллюстрируем вышесказанное. Для каждого вида груза проведем построение, представленное на рисунке 1 для груза первого вида. Нижние индексы величин x наследуются от L, а верхние от y. Тем самым определяется план перевозок: сколько груза того или иного вида каждое ТС должно доставить в каждый ПП.

Рисунок 1. Формирование плана перевозок.

Трехэтапная эвристическая процедура решения

Поставленная задача не может быть решена с помощью известных способов решения задач маршрутизации напрямую в силу многономенклатурности грузов и потребности в учете ограничений на их перевозку различными ТС. Для решения задачи (1)-(4) предложена трехэтапная эвристическая процедура.

Первый этап. В случае совместности ищется какое-нибудь решение вспомогательной системы (5)-(8). Значения , полученные на данном этапе, позволяют загрузить ТС в соответствии с ограничениями, наложенными на перевозку различных видов грузов, однозначно определяя вид груза ‑ i и ТС для перевозки его потребителю ‑ p. Методы поиска решения различаются в зависимости от того, описываются ли потребности в грузах различных ПП и грузоподъемности ТС целыми числами или нет. От вспомогательной системы (5)-(8) переходим к решению исходной системы (1)-(4).

На втором этапе по значениям  и  определяются значения . Для каждого вида груза производится построение, представленное на рисунке 1, в ходе которого для каждого ТС определяется множество ПП, в которые ему следует доставить грузы разных видов.

На третьем этапе для каждого ТС решается задача коммивояжера, это позволяет вычислить значение целевой функции . Третий этап является самым трудоемким в вычислительном смысле.

Целочисленный вариант мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку

Рассмотрим частный случай задачи, когда потребности каждого пункта потребления в каждом виде груза целые, грузоподъемности каждого из ТС также целые. Покажем, что для любого допустимого способа перевозки грузов существует способ перевозки по тем же маршрутам, для которого все веса грузов ( ) ‑ целые.

Рассмотрим план перевозок. Среди всех весов грузов  выберем те, которые не являются целыми. Пусть Z ‑ множество таких троек ,  ( ) ‑ дробные части . Обозначим через  пару , через  значение p. Значения , определенные на , целые, поскольку отличаются на целые величины от целых величин - потребностей j-го пункта в i-м грузе.

Пусть . Эти величины определены на . Так как загрузка ТС может быть частичной, эти величины могут не быть целыми. Обозначим через  ‑ минимальное целое число, не меньшее qp.

Заметим, что поскольку грузоподъемность ТС целая, то p-е ТС можно догрузить до gp. Из равенства  следует, что . Отсюда, при  существуют целые числа  такие, что  и .

Покажем, что числа  можно заменить на  таким образом, что  при ,  при . При замене  на  получим нужный результат ‑ целые значения весов грузов . Обозначим через  множество ,  множество .

Заметим, что выполняются следующие условия:

 (13)

поскольку значения , расположенные в позициях из Z, меньше 1, а их сумма равна целому числу ;

,  (14)

поскольку , аналогично предыдущему  и числа ,  целые,

. (15)

Применим следующую процедуру.

При  выберем в множестве  число троек, равное , положим  для выбранных троек и  для остальных троек индексов из . Разобьем пары из  на четыре класса.

- Пары, которые не входят в множество , не влияют на дальнейшее построение.

- Для пар , у которых , положим .

- Для пар , у которых  и  также никаких изменений не производится.

- Для пар (i,j), у которых  и  полагаем  при , , из множества Z исключаем , полагаем  при .

Исключим из множества Z тройки вида .

По завершении процедуры получим множество Z, величины Vij и q´p такие, что условия (13)-(15) выполняются, и при этом значение pr2(Z) уменьшилось на 1. Повторяя эту процедуру, получим нужные значения .

Точный метод решения целочисленной оптимизационной мультиноменклатурной задачи с ограничениями на перевозку

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

При наличии двух ТС могут возникнуть следующие варианты перевозки грузов:

  1. все виды грузов могут перевозить оба ТС;
  2. есть грузы, допустимые к перевозке только первым ТС, и есть грузы, допустимые к перевозке только вторым ТС;
  3. есть грузы, которые может перевозить только первое ТС, есть грузы, допустимые к перевозке только вторым ТС, и есть грузы, которые могут перевозить оба транспортных средства.

Первые два случая тривиальны, остановимся подробнее на третьем. Грузы, допустимые к перевозке только первым ТС, будем рассматривать как грузы первого вида; грузы, которые может перевозить второе ТС, как грузы второго вида; грузы, которые могут перевозить оба транспортных средства - как грузы третьего вида.

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

Применим следующую последовательность шагов:

1) Рассмотрим загрузку обоих ТС грузами третьего вида. Пример загрузки ТС приведен на рисунке 2. Среди ПП, посещаемых обоими ТС, выберем груз с минимальным весом . Пусть .

ТС

ПП

 

1

2

...

n

1

...

2

...

 

 

 

 

 

Рисунок 2. Начальная загрузка двух ТС грузами третьего вида.

2) Объединим доставку в 1-й ПП обоих ТС, перенеся груз  из первого ТС во второе. Из загрузки второго ТС выберем груз веса α, такой, чтобы можно было объединить доставку, и переместим его в первое ТС.

ТС

ПП

 

1

2

...

n

1

0

...

2

...

 

 

 

 

 

Рисунок 3. Модернизированная загрузка двух ТС грузами третьего вида.

3) Повторим шаги 1-2 до тех пор, пока более одного ПП будут посещаться обоими ТС.

Применение трехэтапной эвристической процедуры в случае целочисленности потребностей каждого ПП в каждом виде груза и грузоподъемностей каждого ТС имеет свои особенности. Рассмотрим алгоритм подробнее.

Первый этап решения - определение загрузки ТС в случае совместности вспомогательной системы. Добавив в левую часть неравенств некоторую неотрицательную переменную γ (т.е. введя в загрузку ТС фиктивный груз), перейдем от системы уравнений и неравенств (5)-(8) к системе уравнений вида

 (16)

где  - целочисленная матрица;  - целочисленный вектор. Применение эрмитовой нормальной формы к решению системы уравнений  позволяет выявить существование целочисленных решений системы (16). С описанием преобразований можно ознакомиться [2; 3].

В случае существования целочисленных решений, найдем оптимальное решение вспомогательной системы (5)-(8) и перейдем к решению исходной системы (1)-(4) многономенклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку.

Имея загрузку ТС различными видами грузов ( ) и потребность ПП в данных грузах ( ), становится возможным определить значения . Как упоминалось выше, с этой целью для каждого вида груза производится построение, проиллюстрированное на рисунке 1. Данное построение позволяет однозначно присвоить ПП каждому из ТС в соответствии с произведенной загрузкой. Для улучшения решения для двух ТС может быть применена процедура, при помощи которой вычисляются значения целевой функции при всевозможных перестановках исходных данных ‑ потребностей пунктов потребления и загрузок транспортных средств.

Итак, имеем два транспортных средства с грузоподъемностями Sи S2 соответственно. Имеем также потребности ПП в грузе i-го вида: Li1,...,Lin. Как было показано выше, из любой загрузки двух ТС грузами, разрешенными к перевозке обоими ТС, можно получить загрузку, такую, в которой не более чем один пункт потребления будет посещен обоими ТС.

Шаг 1. Присвоим j=1. Li1 ‑ потребность 1-го ПП в грузе i-го вида, которую потенциально могут разделить между собой оба ТС.

Шаг 2. Удалим из рассмотрения Li1. Оставшиеся грузы  последовательно проверяются на загрузку в первое ТС. При каждом очередном добавлении груза выполняется проверка, не превосходит ли его вес величины оставшегося запаса грузоподъемности первого ТС, а общая загрузка удовлетворяет условию: . Грузы, не загруженные в первое ТС, автоматически подлежат загрузке во второе ТС.

В случае если общая загрузка первого ТС равна его грузоподъемности S1 или грузоподъемности за минусом потенциально разделяемого груза S1 - Li1, имеем загрузку транспортных средств без совместного посещения 1-го ПП обоими ТС.

В случае если общая загрузка первого ТС удовлетворяет условию , груз для 1-го ПП разбивается для загрузки в первое и второе ТС.

Шаг 3. Вычисляем значение целевой функции.

Шаг 4. Присвоим .

Окончание просмотра всех потенциально разд25 еляемых грузов и соответствующих им загрузок ТС завершает процедуру вычисления значений целевой функции при всевозможных перестановках исходных данных.

Задача коммивояжера в данном случае также должна быть решена точным методом.

Заключение

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

Рецензенты:

  • Юлмухаметов Р.С., д.ф.-м.н., профессор, главный научный сотрудник Института математики с вычислительным центром Уфимского научного центра Российской академии наук, г. Уфа.
  • Болотнов А.М., д.ф.-м.н., профессор, зав. кафедрой информационных технологий Башкирского государственного университета Минобрнауки, г. Уфа.

Работа получена 26.09.2011