Формализации задач погрузки и доставки

Впервые задача маршрутизации транспортных средств (VRP – Vehicle Routing Problem) была поставлена в [1]. За истекшие десятилетия рассматривалось множество модификаций VRP. Информация по этой тематике аккумулируется на сайте [2]. Один из подходов к классификации подобных задач приведен в [3].

Предполагается, что граф, вершинами которого являются пункты производства и потребления, а дугами – соответствующие пути, является полным. При формализации этой задачи в качестве неизвестных используются булевы величины – элементы матрицы перестановки или индикаторы непосредственных переходов между пунктами. В первом случае целевая функция оказывается квадратичной, но при этом не может возникнуть подциклов. Во втором задача априори является линейной. Исследовались в основном формализации второго типа, причем число ограничений часто принималось экспоненциально зависящим от числа пунктов, непосредственное применение оптимизационных пакетов при этом затруднительно. Задача успешно решалась методами ветвей и границ или ветвей и отсечений (генерации столбцов). В недавней работе [4] развивается аналогичный подход для задачи с временными окнами и несколькими транспортными

Математика

средствами, приводится оригинальная модификация второго подхода. Модели с полиномиально растущим числом ограничений там названы компактными.

В статье приводятся формализации, основанные как на первом, так и втором подходах, с числом ограничений, полиномиально зависящим от числа пунктов. В частности, применяются различные методы линеаризации задачи, которые являются адаптацией описанных в обзорах [5, 6] приемов, применявшихся к квадратичной задаче о назначениях [7].

При реализации некоторых из предложенных подходов в каких-либо программных средах понадобится переход от логических переменных b к их числовым значениям [ b ]. Заметим, что для популярного пакета CPLEX подобного преобразования не требуется.

Постановка задачи. Квадратичная формулировка

Пусть P = {1, ..., n } - пункты вывоза грузов веса q i - для i -го пункта, D = { n +1, ... , 2 n } -пункты доставки грузов. Полагаем, что в ( n+i )-м пункте вес груза отрицательный (- q i ). Множество пунктов есть V = P и D и {0}, где нулевой пункт является базой. Транспортное средство (ТС) вместимости S должно объехать все пункты по циклу таким образом, чтобы доставить грузы из i -го пункта в ( n+i )-й при всех i . Маршрут должен начинаться и заканчиваться в базовом пункте. Известны расстояния между всеми парами пунктов с_у . Требуется найти допустимый цикл минимальной длины. Разумеется, задача относится к классу NP-трудных, поскольку в случае, когда пункты каждой пары совпадают и вместимость ТС большая, получим классическую задачу коммивояжера.

Сформулируем несколько свойств данной задачи.

Минимально допустимая вместимость ТС равна max{ q i }. Действительно, очевидно, что при S < max{ q i } организовать перевозку невозможно. При S = max{ q i } допустимым, например, является маршрут 0-1-( n +1)-2-( n +2)-...- n -2 n -0. Тем самым, эта задача существенно отличается от более общей задачи транспортировки однородного груза, для которой задача вычисления минимально допустимой вместимости ТС является NP-трудной.

При неограниченной вместимости ТС число допустимых маршрутов равно (2 n )!/2 ” . Действительно, всего перестановок пунктов (2 n )!, при этом, каждая из допустимых перестановок порождает 2 ” перестановок, полученных всевозможными перестановками пар пунктов с номерами i , ( n+i ) при i = 1, 2,..., n . Этот результат получен в [8] более сложным рассуждением.

При S >  max{ q i } любой допустимый отрезок маршрута можно продолжить. Действительно, если после прохождения отрезка ТС не содержит груза и при этом есть необслуженные пункты, то в качестве следующего можно принять любой пункт, в котором есть груз. Если в ТС груз есть, то при некотором i груз в i -м пункте забрали, но в ( n+i )-й не доставили. Следующим пунктом маршрута можно принять ( n+i )-й.

В качестве переменных примем булевы величины x ip ( i, p = 0, 1,..., 2 n ), равные 1, если i -м в цикле проходится p -й пункт (величины x_ip образуют матрицу перестановки). Ограничения имеют вид:

Z £, xip = 1( p = 0,...,2 n),(1)

Z pn=0 хф = 1( i = 0,...,2 n),(2)

x00 = 1,(3)

Z 2 i ( xi (p+n) - xip )> 1 (p = 1»-»2 n )•

Условие (4) задает правильность последовательности прохождения пунктов.

Действительно, из условия (2) следует, что при некоторых однозначно определенных i ', i " справедливы равенства x i -( _{n + p} ) = x i ‘ _p = 1. Тогда из условия (4) следует, что i " - i ' > 1. Поскольку i ', i " это номера пунктов p , ( n+p ) в порядке прохождения в цикле, то нужное свойство выполняется.

Z м Z p L q p x ip ^ s ( r = 1,...,2 n - 1).                         (5)

Условие (5) отражает ограничение на вместимость ТС.

Целевая функция:

Z 2 n x"'2 n X"'2 n -1                V’2 n

p = 1 ^L r = 0 ^L i = 1 x ip x ( i + 1) r c pr ^{+ L} i = n + 1 x (2 n ) i c i 0 ^ min ^.

В задаче (1)–(6) O( n ²) булевых переменных и O( n ) ограничений.

Линейная задача 1

Введением дополнительных булевых переменных в целевой функции (6) можно избавиться от нелинейности.

Пусть yipr = xipx(i+1)r (i = 0,1,...,2n-1, p,r = 0,1,...,2n). Легко проверить, что эти величины можно задать линейными условиями yzpr ^ xip + x(i+1) r - 1, x.p + x(i+1)r - 2ypr ^ 0.(8)

Целевая функция примет вид

Z2 n    2 n    2 n-12 p=1Lr=0L i=1 yiprcpr + Li=n+1 x(2n)ici0 ^ min.

В линейной булевой задаче (1)–(5), (7)–(9) число переменных и число ограничений имеют порядок O( n ³).

Линейная задача 2

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

Введем вещественные переменные z_ip = x_ip L 2 = 01 x ( i _{+ 1} ) _rc_pr . Целевая функция (6) примет линейную форму

Е2 n х-' 2 n-1          2 n                   .                                   /1/xx p=1L.=1 zip + 1 i=n+1 x(2 n) ic.0 ^ min.                           (10)

Пусть Q = min { 1 ^2=0 max i ( c ij ) , L J^ max j ( c ij ) } • Величина Q определяется только матрицей расстояний, причем при любых допустимых значениях переменных x и любых i,p справедливы оценки 0 <  L ² = _ox ( i + 1) r c pr <  Q •

Легко проверить, что связь переменных x и z задается неравенствами

0 <  Z ip <  QX ip ,                                           (11)

Ir _r = 0 x ( i + 1) r c pr ^{Q ( 1} xip ) < z ip <  Ir _r = 0 x ( i + 1) r c pr •                         ⁽¹²⁾

В задаче (1)–(5), (9)–(12) число булевых переменных, вещественных переменных, ограничений имеют порядок O( n ²).

Линейная задача 3

Здесь описано преобразование, которое позволяет снять условие целочисленности с основ- ных переменных xip за счет введения существенно меньшего числа булевых переменных. Пусть

P log 2 ( 2 n + 1 ) ] ) .

As = | i e { 0,1,...,2 n } :mod 2 ;^ ^ = 0 ( s = 0,1,

Иными словами, A s состоит из тех чисел, в двоичном разложении которых на s -м месте расположен 0.

Введем переменные u = L. x„ ( s = 0,1,...,log₂(2 n + 1).

sp        i G A_s^{ip x                     2 x 7}

Полагаем

X ip G [0,1].

Проверим, что при выполнении условий (1), (13) и булевости переменных u_sp , переменные x ip – булевые.

Пусть напротив x _ip g (0, 1) при некоторых i, p. В силу условия (1) существует еще один индекс j * i , при котором x jp g (0, 1). Существует такое значение s , для которого на s -й позиции в разло-

Математика

жениях чисел i и j расположены разные символы. Пусть для определенности i е A s , j с A s . Но

¹ = Е   x p = Е i е X ⁺ E i c A s x ip = u sp ⁺ Е i с A s x ip *

В силу выбора s оба слагаемых в правой части положительные, т.е. значение u_sp не может быть булевым. Противоречие.

Применяя конструкцию из предыдущего пункта, получим смешанную задачу, в которой число булевых переменных равно O( n log(2 n )), непрерывных переменных и ограничений O( n ²).

Линейная задача 4

К квадратичной модели можно применить линеаризацию иного типа. Пусть A i - порядковый номер i -го пункта в порядке прохождения от базы, т.е. решение уравнения x _ki = 1 относительно k . Справедливо равенство Е 2 = 0 Е k = ₁ x ki = 2^п — A ⁺ 1, поскольку Е k = ₁ x_ki = 0 при s <  A i и е k = 1 x ki = ¹ при s ^- A i .

Через величины A _i ограничения записываются следующим образом:

правильность порядка прохождения пунктов A _i < A _n+i ( i = 1,..., n );

ограничения на вместимость: Е 2 = 1 % [ A - k ] - S ( k = 1,...,2 n - 1).

Целевая функция: Е ^x Е 2 = ^c ij [ A i ^{+ 1} = A j ] ⁺ Е 2"_{n + 1} ^c io [ A i = ^{2 n} ] . ^ min.

Линейная задача 5

Двухиндексная формализация является наиболее распространенной. Пусть t ij – булевы переменные, равные 1, если в цикле дуга из i -го пункта ведет в j -й.

Ограничения:

Е 2=0 tj = 1( j = °,1,-,2 n),(14)

Е2=0 tj = 1( i = 0,1,...,2 n),(15)

tii = 0 (i = 0, ..., 2n).(16)

Эти условия означают, что ТС из каждого пункта выезжает, в каждый пункт въезжает. При выполнении условий (14)–(16) цикл может разбиваться на подциклы, состоящие более, чем из одного пункта. Для того, чтобы этого избежать, следуя [10], введем вещественные переменные A _i , удовлетворяющие ограничениям:

0 - A , - 2 n ( i = 0,..., 2 n ), A ₀ = 0,                               (17)

A i - A j + (2 n +1) t ij - 2 n ( iJ = 0, ..., 2 n ).                            (18)

Из условий (14)–(18) следует, что величины A _i автоматически целые, равные, как и в предыдущей модели, номерам пунктов в порядке прохождения в цикле. Правильность последовательности прохождения пунктов приобретает простую форму и ограничения на вместимость имеют тот же вид, что и в выше.

2 n    2 n

Целевая функция: е, = ₀ Е j = ₀ c y t ij ^ min.

В этой модели число булевых переменных и ограничений имеет порядок O( n ²), вещественных O( n ).

Линейная задача 6

Введение иных вспомогательных переменных позволяет модифицировать линейную модель 5.

Пусть t _ij – те же переменные, что и в предыдущей модели, удовлетворяющие условиям (14)– (16). Введем двумерный аналог ( a i , в потенциалов пунктов, исследованных, в частности, в [11]. Смысл вспомогательных вещественных переменных – вес груза, который погрузили (соответственно разгрузили) до посещения i -го пункта, включая i -й. Как обычно, a ⁺ = (| a |+ a )/2, a ^- = (| a | - а )/2 - соответственно положительная и отрицательная части числа. Пусть числа a i , P i удовлетворяют следующим условиям:

Бронштейн Е.М., Гиндуллина Э.В.,                    Формализации задач погрузки и доставки

Гиндуллин Р.В.

Ц> tj(a + q/) (i = 0,..., 2n;j = 1,..., 2n),(19)

• a, < R (j' = 0,..., 2n),(20)

в > tij(Pi + qj-) (i = 0,..., 2n; j = 1,..., 2n),(21)

в < R (j' = 0,..., 2n),(22)

a = в = 0.(23)

Здесь R = X 2 n 0 <  = X 2= ¹0 q i . Из условий (19), (21) следует, что в построенном маршруте нет циклов. Действительно, q + + q ^- = | q i | >  0, т.е. при t j = 1 выполняется неравенство a + в >  a i + P i , что и требовалось. Отсюда и из условий (14), (15) маршрут является цепью, содержащей все пункты; поскольку a j + в >  0 в силу условий (19), (21), то из (23) следует, что начальный пункт цепи является базой (это следует также из того, что в неравенствах (19), (21) нет ограничений на дугу, конечным пунктом которого является база). Пусть маршрут (незамкнутый) имеет вид 0– i ₁– i 2 ...– i 2 _n .

Докажем, что ° = X ^k = 1 q i + , ^p i k = X ^k = 1 q ^- ( ^k = i™,^{2 n} ) .

Для этого просуммируем неравенства (19). Получим a i 2 >  a ₀ + X 2 ^ = 1 q_z⁺ = R , тем самым, с учетом (20) и (23) неравенства (19) при t ij = 1 фактически являются равенствами, что и требовалось. Утверждение для в аналогично вытекает из (21)-(23).

Нелинейные условия (19), (21) можно привести к линейной форме с помощью приема, аналогичного (11), (12).

Условие правильности прохождения пунктов и ограничения на вместимость имеют простой вид: a + в _i <  a _i+n ) + в ( _i+n ) ( i = 1, ..., n ); a - в _i <  S ( i = 1, —, 2 n ). Целевая функция та же, что и в модели 5.

Линейная задача 7

Применим трехиндексные переменные, использование которых позволяет получить линейную булеву задачу, причем в этом случае для исключения «коротких» циклов не требуется введения дополнительных переменных. Эта формализация оказалась наиболее эффективной среди нескольких альтернативных при решении задачи доставки однородного груза типа «many-to-many».

Пусть vij (i, j = 0,...,2n; k = 1,...,2n +1) - булевы переменные, равные 1, если k-я по порядку дуга в маршруте ведет из i-го пункта в j-й. Эта модель является детализацией линейных моделей 2n2

• ¹    и 6. Действительно, x i = ₀ ^v j = x kj , X _k = 1 v j = t j .

Ограничения

X 2=0 X k =+1 vk = 1 (j = 0,...,2 n);(24)

X 2=0 X k =+1 vk = 1 (i = 0,...,2 n);(25)

X 2no XJ1 vk = 1 (k = 1,...,2 n +1)

означают, что ТС из каждого пункта выезжает и в каждый въезжает по одному разу, а также, что каждая дуга инцидентна единственной паре пунктов.

Условия

Xn nv1, = 1, X2n ,v2n+1 = 1(27)

j=0 0j i-nx=n+1 i0v 7

означают, что первая дуга ведет из базы в какой-нибудь пункт производства, а последняя по порядку – из какого-нибудь пункта потребления в базу.

Условие последовательного прохождения дуг (конец k -й дуги совпадает с началом ( k +1)-й) имеет вид:

X 2 n ₀ v k = X 2 = 0 v k + ( j = 1,...,2 n ; k = 1,...,2 n ).                         (28)

Условия (24)–(28) определяют гамильтонов цикл, в котором последовательные дуги имеют соответствующие номера [12].

Математика

Докажем, что условия правильности последовательности прохождения пунктов в рассматриваемых переменных можно записать в следующей форме:

• — 2 = 1 — k < , — X — 2 = . ( v к. *т - - "° ( i = ^1,-^{, л} ) •                 (^

Действительно, если из i -го пункта ТС выезжает по дуге с номером к ₁, а из ( n + i )-го - по дуге с номером к ₂, то — p '= ₁ — 2 = , ( v ( ^к ₊ i ) _p - v ^ ) = 0 при к <  min{ к ₁, к ₂}, поскольку в этом случае v (n + i ) p = ^v y = ⁰ при любых p , ^j , T.e. — _к < s — p = , — ^ ( v („ + i ) j ^— v p ) = О, если s <  ^{min{ к} 1 , ^к 2 ^} • Это же равенство справедливо при s >  max{ к ₁, к ₂}, поскольку в этом случае v^i ) _p = v ^{k 2} = 1 при некоторых однозначно определенных p , j , к ₁, к ₂ и v^i ) _p = v ^{k 2} = 0 при всех остальных p , j , к . Если к , <  к ₂, то v ip¹ = 1 при некотором p и v ip = 0 при остальных p , v^ ₊ i ) _p = 0 для всех p , т.е. неравенство (29) выполняется. Аналогично проверяется, что при к ₂<  к , неравенство (29) не выполняется.

Ограничение на вместимость:

• — к < ■ — 21 — ^. (s = Wn).                 (30)

Целевая функция:

Е 2 n +1^-> 2 n ^->2 n k .

к = 1 — i = 1 — j = 1 vC ^ ^min.                          ⁽³¹⁾

Число булевых переменных и ограничений задачи (24) - (31) имеют порядок O( n ³).

Линейная задача 8

В предыдущих моделях используются разреженные структуры данных. Данные можно уплотнить, используя в качестве основных целочисленные переменные A i , введенные в модели 4. Ограничения:

0 <  A i <  2 n ( i = 0,..., 2 n ); A ₀ = 0.

Отсутствие подциклов равносильно биективности отображения A . Поскольку число элементов в обоих множествах равно 2 n + 1, то биективность равносильна инъективности, которую можно задать условиями [ A i = A j ] = 0 ( i , j = 0,..., 2 n, i <  j ). Ограничения на правильность последовательности прохождения пунктов и на вместимость, а также целевая функция, имеют тот же вид, что и в модели 4.

Дополнительные ограничения

Избыточные ограничения могут ускорять решение задачи. В [13] сформулирован ряд дополнительных ограничений для случая неориентированного графа и неограниченной вместимости ТС, число которых экспоненциально зависит от числа пунктов. Для рассматриваемого случая целесообразно использовать следующие ограничения.

Для линейных моделей 1-3

X pi + x ( p + 1) j < [ Q i + q j <  S ] + 1 ( i , j = 1,..., n , p = 1,...,2 n - 2 ) ;

x p ( n + i ) ⁺ x ( p + 1)( n + j ) < [ q i ⁺ q j <  ^S ] ^{+ 1 (} i , ^j = ^1,...^{, n} , ^p = ^1,...^,2 n ^— 2 ) .

Обозначение [ a ] то же, что и во введении. Эти условия означают, что в двух последовательных пунктах производства (потребления) суммарная загрузка (потребность) не превышает вместимости ТС.

Для линейных моделей 4, 5 соответствующие ограничения формулируются проще:

t j < [ q i ⁺ q j <  ^S ] ^; t ( n + i )( n + j ) < [ q i ⁺ q j <  ^S ] ⁽ i , ^j = ^1,...^{, n ) .}

Для линейной модели 6:

v j < [ qi ⁺ q j <  ^S ] ^; v ( n + i )( n + j ) < ^[ q i ⁺ q j <  ^S ] ⁽ i , ^j = ^1,...^{, n ; к} = ^1,...^{, 2 n + 1 ) .}

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

Бронштейн Е.М., Гиндуллина Э.В.,                    Формализации задач погрузки и доставки

Гиндуллин Р.В.

Сформулируем некоторые дополнительные ограничения, которые являются адаптацией ограничений для близких задач из [12] и являются следствиями правильности последовательности прохождения пунктов.

Дуги, соединяющие пункты i – ( n + j ) и j – ( n + i ) при различных направлениях движения одновременно, в маршрут перевозок входить не могут, поэтому для линейных моделей 1–3 x pi + x ( p +1)( n+j ) + x sj + x ( s +1)( n+i ) ≤ 3; x pi + x ( p +1)( n+j ) + x s ( n+i ) + x ( s +1) i ≤ 3;

x _p ( _n+i ) + x ( _{p +1} ) j + x _s ( _n+j ) + x ( _{s +1} ) _i ≤ 3, ( i , j = 1, ..., n ; p , s = 1, ..., 2 n –1).

Для моделей 4, 5:

t i ( n+j ) + t j ( n+i ) ≤ 1; t i ( n+j ) + t ( n+i ) j ≤ 1; t ( n+i ) j + t ( n+j ) i ≤ 1 ( i, j =1,..., n ).

Аналогично формулируются условия для моделей 6.

Аналог этих условий можно сформулировать для большего числа дуг. Например, одновременно не могут входить в маршрут дуги, соединяющие пункты i – ( n + j ), j – ( n + p ), p – ( n + i ) при различных направлениях движения.

Другой класс условий такого типа. Не существует цепи, соединяющей ( n + i )-й и i -й пункты. Например, для цепи длины 2 для моделей 4, 5 получаем условие t ( n+i ) j + t ji ≤ 1 ( i = 1, ..., n ; j = 1, ..., 2 n ).

Заключение

В работе построен ряд моделей, относящихся к задачам транспортной маршрутизации типа «one-to-one», основанных на различных подходах. Большая часть рассмотренных моделей – линейные булевы или смешанные. Для сравнения вычислительной эффективности моделей был проведен эксперимент с использованием оптимизационного пакета CPLEX 12.6. Рекордной по производительности на случайно сгенерированных данных оказалась линейная смешанная трех-индексная модель.

Установлено, что добавление некоторых дополнительных неравенств существенно повышает эффективность работы метода, в то время, как иные добавленные неравенства снижают эффективность.

В ряде случаев фактором, препятствующим решению задачи большей размерности, явилась ограниченность оперативной памяти.

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

Перспективы применения моделей, предложенных в статье, заключаются в расширении оперативной памяти компьютера и совершенствовании оптимизационного пакета CPLEX. Как отметила K. Archetti (Брешиа, Италия) в докладе на 3 совещании Европейской рабочей группы VeRoLog (Осло, 2014 г) [15], CPLEX 11 (2007) работает почти в 30 000 раз быстрее, чем CPLEX 1 (1991).