Задача упаковки кругов и прямоугольников в полосу

Версия для печати

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

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

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

W —  ширина полосы

n_c — число кругов

n_r – число прямоугольников

I = {1, 2, …, n_c} – множество кругов

J = {1, 2, …, n_r} – множество прямоугольников

r_i, iÎI, – радиус i-го круга

l_j и w_j, jÎJ, – длина и ширина j-го прямоугольника

 

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

Будем говорить, что j-й прямоугольник находится левее m-го прямоугольника, если можно провести вертикальную прямую так, что j-й прямоугольник будет слева от нее, а  m-й — справа.

Будем говорить, что j-й прямоугольник находится ниже m-го прямоугольника, если можно провести горизонтальную прямую так, что j-й прямоугольник будет снизу от нее, а  m-й — сверху.

x_i^c и y_i^c —  координаты центра i-го круга

x_j^r и y_j^r—  координаты левого нижнего угла j-го прямоугольника

zj = {	1, если j-й прямоугольник повернут на 90о
	0, в противном случае

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

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

L – длина занятой части полосы

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

min L

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

 x_i^c – r_i ³ 0,                        iÎI,

y_i^c – r_i ³ 0,                        iÎI,

x_i^c + r_i £ L,                       iÎI,

y_i^c + r_i £ W,                      iÎI,

x_j^r ³ 0,                               jÎJ,

y_j^r ³ 0,                               jÎJ,

x_j^r + l_j(1– z_j) + w_jz_j £  L,    jÎJ,

y_j^r + w_j(1– z_j) + l_jz_j £  W,    jÎJ.

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

(x_i^c – x_k^c)² + (y_i^c – y_k^c) ² ³ (r_i + r_k )² ,    i,kÎI.

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

x_j^r + l_j(1 – z_j) + w_jz_j £  x_m^r + (1– a_jm^L)L^*,    j, m ÎJ,

y_j^r + w_j(1 – z_j) + l_jz_j £  y_m^r + (1– a_jm^B)W,     j, m ÎJ,

a_jm^L + a_mj^L + a_jm^B + a_mj^B = 1,    j, m ÎJ.

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

(x_i^c – x_j^r)² + (y_i^c – y_j^r) ² ³ r_i² ,                                                                 iÎI,  jÎJ,

(x_i^c –( x_j^r + l_j(1 – z_j) + w_jz_j))² +  (y_i^c – y_j^r) ² ³ r_i²,                                  iÎI,  jÎJ,

(x_i^c – x_j^r)²  + (y_i^c – (y_j^r + w_j(1– z_j) + l_jz_j))² ³ r_i²,                                    iÎI,  jÎJ,

(x_i^c –( x_j^r + l_j(1 – z_j) + w_jz_j))² + (y_i^c – (y_j^r + w_j(1– z_j) + l_jz_j))² ³ r_i²,      iÎI,  jÎJ,

x_i^c + r_i £ x_j^r + (1– b_ij^L)L^*,                                                                      iÎI,  jÎJ,

x_j^r + l_j(1 – z_j) + w_jz_j £ x_i^c – r_i + (1– b_ij^R)L^*,                                          iÎI,  jÎJ,

y_i^c £ y_j^r + (1– b_ij^B)W,                                                                            iÎI,  jÎJ,

y_j^r + w_j(1– z_j) + l_jz_j £ y_i^c+ (1– b_ij^A)W,                                                   iÎI,  jÎJ,

b_ij^L + b_ij^R + b_ij^B + b_ij^A = 1,                                                                   iÎI,  jÎJ,

x_i^c £ x_j^r + (1– c_ij^L)L^*,                                                                            iÎI,  jÎJ,

x_j^r + l_j(1 – z_j) + w_jz_j £ x_i^c + (1– c_ij^R)L^*,                                                iÎI,  jÎJ,

y_i^c + r_i £ y_j^r + (1– c_ij^B)W,                                                                      iÎI,  jÎJ,

y_j^r + w_j(1– z_j) + l_jz_j £ y_i^c – r_i + (1– c_ij^A)W,                                            iÎI,  jÎJ,

c_ij^L + c_ij^R + c_ij^B + c_ij^A = 1,                                                                    iÎI,  jÎJ,

 

ЛИТЕРАТУРА 

1. Hifi M., M'Hallah R. A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes // Internat. Transaction in Oper. Res. – 2003. – Vol. 10. – P. 195–216.

2. Kallrath J., Kochetov Y., Rudnev A. Strip packing problem for circles and rectangles // 4th ESICUP Meeting. – Tokyo: University of Tokyo, 2007. – P. 20.

---

Главная страница библиотеки