Задача упаковки прямоугольников в контейнеры
с запрещенными областями

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

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

Обозначим исходные данные задачи следующими параметрами:

n — количество предметов

l – количество контейнеров с запрещенными областями

I = {1, 2, …, n} — множество предметов

w_i и h_i, iÎI, — ширина и высота i-го предмета

di ={	1, если i-й предмет может пересекаться с запрещенными областями
	0, в противном случае

M = M₁ È M₂ — множество контейнеров

M₁ = {1, 2,…, l} — контейнеры с запрещенными областями

M₂ = {1, 2, …, n} — дополнительные контейнеры одинакового размера без запрещенных областей

W_m и H_m, mÎM — ширина и высота m-го контейнера (ширина и высота дополнительных контейнеров берутся не меньше максимальной ширины и высоты предметов, поэтому достаточное количество дополнительных контейнеров равняется n)

I⁰={1, 2, …, K} — множество запрещенных областей

qkm ={	1, если k-я запрещенная область находится в m-м контейнере
	0  в противном случае

x_k⁰,  y_k⁰, w_k⁰, и h_k⁰, kÎK — координаты и размеры запрещенных областей (будем считать, что левый нижний угол каждого контейнера находится в начале координат)

Переменные задачи:

x_i и y_i — координаты левого нижнего угла i-го предмета

pim ={ 1, если i-й предмет лежит в m-м контейнере 0  в противном случае

aijL ={ 1, если i-й предмет находится левее j-го 0  в противном случае

aijB ={ 1, если i-й предмет находится ниже j-го 0  в противном случае

bikL ={ 1, если i-й предмет находится левее k-й запрещенной области 0  в противном случае

bikR ={ 1, если i-й предмет находится правее k-й запрещенной области 0  в противном случае

bikB ={ 1, если i-й предмет находится ниже k-й запрещенной области 0  в противном случае

bikA ={ 1, если i-й предмет находится выше k-й запрещенной области 0  в противном случае

um ={ 1, если m-й контейнер используется 0  в противном случае

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

min

l+n å m=1

um

Зададим порядок использования контейнеров от первого к последнему:

u_m ³ u_m+1, mÎM.

Использование контейнеров определяется с помощью следующего неравенства:

umn ³

n å i=1

pim,  mÎM.

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

l+n å m=1

pim = 1, iÎI.

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

xi ³ 0,     iÎI,
yi ³ 0,     iÎI,
xi + wi(1 – zi) + hizi £	l+n å m=1	pimWm,    iÎI.

yi + hi(1 – zi) + wizi £

l+n å m=1

pimHm,    iÎI.

Следующие три ограничения исключают пересечения предметов между собой, если они находятся в одном контейнере. Здесь W_max и H_max — максимальные ширина и высота контейнеров:

x_i + w_i(1 – z_i) + h_iz_i £  x_j + (1– a_ij^L)W_max,    i, j ÎI,

y_i + h_i(1 – z_i) + w_iz_i £  y_j + (1– a_ij^B)H_max,    i, j ÎI,

a_ij^L + a_ji^L + a_ij^B + a_ji^B ³ p_im + p_jm – 1,       i, j ÎI.

Аналогично последняя группа неравенств исключает пересечения предметов и запрещенных областей, находящихся в одном контейнере в случаях, когда это недопустимо:

 

ЛИТЕРАТУРА

1. А. Руднев А. С. Задачи двумерной прямоугольной упаковки с запрещенными областями // Труды ИВМиМГ СО РАН. Сер. Информатика. – Новосибирск: Изд-во ИВМиМГ СО РАН, 2006. – Вып. 6. – С. 156-162.

2. Beisiegel B., Kallrath J., Kochetov Y., Rudnev A. Simulated annealing based algorithm for the 2D bin packing problem with impurities // Operations research proceedings, 2005. – Heidelberg: Springer, 2006. – Р. 109-113.

3. Lodi A., Martello S., Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems // INFORMS J. Computing. – 1999. – Vol. 11. – P. 345–357.

4. Pisinger D., Sigurd M. The two-dimensional bin packing problem with variable bin sizes and costs // Discrete Optimization – 2005. – Vol. 2, N 2 – P. 154–167.

---

Тестовые примеры