КОНСТРУКТИВНАЯ ЭВРИСТИКА В ДВУМЕРНОЙ ПРЯМОУГОЛЬНОЙ УПАКОВКЕ

​CONSTRUCTIVE HEURISTICS IN A TWO-DIMENSIONAL RECTANGULAR PACKAGE

Arina Danilova

student, Department of Commodity Expertise, technology of trade and restaurant business, Krasnodar branch of the Russian Economic University named after G.V. Plekhanov,

Russia, Krasnodar

Alisa Kirichenko

student, Department of Commodity Expertise, Technology of trade and restaurant business Krasnodar branch of the Russian Economic University named after G.V. Plekhanov,

Russia, Krasnodar

Olga Panteleeva

scientific supervisor, Candidate of Pedagogical Sciences, Assoc., Krasnodar branch of the Russian Economic University named after G.V. Plekhanov,

Russia, Krasnodar

АННОТАЦИЯ

В условиях современной политики оптимизации производственных процессов решение задачи ортогональной упаковки прямоугольных предметов в заданную ёмкость стоит наиболее актуально, так как нахождение алгоритмов вычисления позволит оптимизировать как транспортировочный процесс, так и процесс производства. На данный момент данный тип задач упаковки так и не был решен полностью, так как ставится вопрос о создании общего алгоритма расчетов, однако каждое изменеие параметра, начиная от ёмкости конкретного объекта, в который помещается определенный объект, заканчивая высотой данного объекта. Цель данного исследования - показать ранее открытые методы ортогональной упаковки и показать нынешние способы выборки оптимального общего решения данного типа задачи упаковки.

ABSTRACT

In the context of the modern policy of optimizing production processes, solving the problem of orthogonal packing of rectangular objects into a given container is most relevant, since finding calculation algorithms will optimize both the transportation process and the production process. At the moment, this type of packaging problem has not been completely solved, since the question is being raised about creating a general calculation algorithm, however, each parameter change, starting from the capacity of a specific object in which a certain object is placed, ending with the height of this object. The purpose of this study is to show previously discovered methods of orthogonal packaging and to show current ways of selecting the optimal general solution to this type of packaging problem.

Ключевые слова: высшая математика, упаковка ортогональных предметов, практическая полезность, эвристические подходы к решению задач упаковки, метаэвристика и её методы, оптимизация производственных процессов.

Keywords: higher mathematics, packaging of orthogonal objects, practical usefulness, heuristic approaches to solving packaging problems, metaheuristics and its methods, optimization of production processes.

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

Пусть необходимо упаковать прямоугольники, которые могут отличаться по типу, но с заданными для каждого типа i, i=1,…, m; количеством b_i и размерами (w_i, l_i) прямоугольников.

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

В Работе Гильмора и Гомори предложена следующая модель решения данного типа задач: пусть A_j – бинарный вектор-столбец с компонентами a_ij принимающими значение 1, если элемент i принадлежит j-му подмножеству элементов, которые попадают в один контейнер, и 0 в противном случае. Множество всех возможных образцов представляется тогда матрицей A из всех возможных столбцов A_i, j=1,…., M, а математически модель задачи имеет вид

при условиях

где x_j принимает значение 1, если образец j принадлежит решению, и 0 в противном случае.

Из-за огромного количества столбцов, которые могут находится в матрице A, эффективным путем взаимодействия с ней является генерирование столбцов по мере необходимости.

При условии упаковки многоуровнево, для решения задач упаковки прямоугольных предметов в контейнеры необходимо использовать иные методы решения. Смоделируем практическую задачу: необходимо упаковать n-ое количество предметов, имея n-ое число потенциальных уровней (i-й элемент инициализирует i-й уровень) и имеется некое число n-ных контейнеров (k-й контейнер инициализирует k-й потенциальный уровень). Вводятся двоичные переменные y_i и q_k принимающие значение 1, если элемент i инициализирует уровень i. Аналогично происходит и  с переменной k. В противном случае - значение 0. Тогда модель имеет вид

при условиях

где x_ij и z_ki принимают значение 1, если элемент j попадает в уровень i и соответственно уровень i попадает в контейнер k, в отличном случае принимает значение 0.

Методы, которые приводились раннее не являются обощенным алгоритмом решения проблем двумерной упаковки. Некоторые из этих методов позволяют решить задачи упаковки прямоугольных предметов ("плохие" задачи), некоторые же не позволяют этого сделать, вследствие чего не приводится единого правильного метода решения данного типа задач. Однако, в нынешнее время для решения данного типа задач используются метаэвристики. Метаэвристика — это процедура машинного обучения, которая позволяет находить наиболее эффективное решение задач оптимизации при неполной или неточной информации. Метаэвристика является наиболее оптимальным методом для изучения проблематики задачи двумерной упаковки, так как количество решений, которое может появится при грамотно обученной машине бесконечное множество, которое просто невозможно будет обработать.

В метаэвристике существует множество методов, однако в рамках данного исследования будет рассмотрен метод генетических алгоритмов. Он представляет из себя создание фреймов, которые включают в себя поля. Местоположение определенного поля в определенном фрейме называется локусом. Фреймы, как хромосомы (отсюда и пошло название "генетические алгоритмы") обладают свойством наследования, который, в процессе эволюции, приводит к увеличению вероятности появление выборки наиболее эффективных значений целевой функции. Работает это следующим образом: для выведения обобщённого решения задачи гильотинного разреза и двумерной упаковки в один фрейм вкладываются частные алгоритмы задач упаковки, к примеру, коротких прямоугольных предметов, а в другой фрейм вкладываются частные алгоритмы упаковки длинных прямоугольных предметов. Так как мы не имеем достаточных сведений о длине, ширине, высоте как предмета, так и самой ёмкости, мы рассматриваем это на примере полу бесконечной открытой ёмкости, вследствие чего мы не может объявлять решения, находящиеся в полях обобщенными алгоритмами решения проблематики. Как итог, ученые начинают анализировать эту проблему более глубинно путем скрещивания хромосом и создания новых фреймов, с новыми решениями и так, пока не будет найден единый эффективный алгоритм.

Заключение.

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

Список литературы:

1. Lody, A. Two-dimensional packing problems: a survey / A. Lody, S. Martello, M. Monaci // European Journal of Operational Research. – 2002 – Vol. 141 – P. 241–252.
2. Tarnowski, A.G. Advanced polynomial time algorithm for guillotine generalized pallet load-ing problem / A.G. Tarnowski // Decision Making under Conditions of Uncertainty (Cutting-Packing Problems); ed. E.A. Mukhacheva. – Ufa, 1997 – P. 93–124.
3. Tarnowski, A. A polynomial time algorithm for the guillotine pallet loading problem
4. A. Tarnowski, J. Tern, G. Scheithauer // INFOR. – 1994 – Vol. 32 – P. 275–286.
5. Гэри, М. Вычислительные машины и труднорешаемые задачи / M. Гэри, Д. Джонсон. – М: Мир, 1982 – 416 с.
6. Канторович, Л.В. Рациональный раскрой промышленных материалов / Л.В. Канторович, В.А. Залгаллер. – Новосибирск : Наука, 1971 – 299 с.
7. Автобиография Леонида Витальевича Канторовича // Оптимизация : сб. науч. тр. СОАН СССР. – Новосибирск, 1982 – Bып. 28 – C. 50–57.
8. Gilmore, P.C. A linear programming approach to the cutting stock problem / P.C. Gilmore, R.E. Gomory // Operations Research. – 1961 – Vol. 9 – P. 849–859.
9. Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning / D. Goldberg. – Boston : Adison-Wesley, 1989 – 372 p.
10. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач / Д.И. Батищев. – Воронеж : ВГТУ, 1995 – 69 с.
11. Aarts, E.H.L. Local search in combinatorial optimization / E.H.L. Aarts, J.K. Lenstra. Chichester : Wiley, 1997 – 528 p.
12. Норенков, И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации / И.П. Норенков // Информационные технологии. – 1999 – № 1 – С. 2–7.
13. Мухачева, Э.А. Генетический алгоритм блочной структуры в задачах двумерной упаковки / Э.А. Мухачева, А.С. Мухачева, А.В. Чиглинцев // Информационные технологии. – 1999 – № 11 – С. 13–18.
14. Linear one-dimensional cutting-packing problems: numerical experiments with sequencial value correction method (SVC) and a modified branch-and-bound method (MBB) / E.A. Mukhacheva [et al.] // Pescuisa Operational. – 2000 – Vol. 20 – P. 153–168.