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

Р.Т.Мурзакаев; В.С.Шилов; А.В.Буркова

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

Аннотация

Р.Т.Мурзакаев , В.С.Шилов , А.В.Буркова

Дата поступления статьи: 15.12.2013

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

Ключевые слова: раскрой-упаковка, фигурный нерегулярный раскрой, классификация, методы, подходы, сложная форма

05.02.08 - Технология машиностроения

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

Проблема экономии ресурсов является актуальной и современной для всех сфер человеческой деятельности как в прошлом, так и в обозримом будущем. При решении задачи промышленного раскроя [1] (компоновки) важным является создание карт раскроя, при которых получается максимальный комплект заготовок деталей и, следовательно, достигается минимизация отходов материалов.
Задачи такого рода объединены под термином «задача раскроя-упаковки» (далее Р-У) и относятся к классу NP-трудных (Nondeterministic polynomial), т.е. переборная вычислительная сложность задачи не позволяет находить точное решение для достаточного количества геометрических объектов за приемлемое время [2,3].
В общем случае выделяют одномерные, двумерные и трехмерные задачи Р-У. Общая классификация задач раскроя-упаковки представлена в работе [2] и на рис.1.

Рис.1. – Общая классификация задач раскроя-упаковки (Р-У)

Для фигурных задач Р-У характерны геометрические объекты (далее ГО) сложной выпуклой, вогнутой и выпукло-вогнутой форм.
Задачи фигурной укладки подразделяются на регулярную и нерегулярную раскрой-упаковку. Регулярные укладки в пространстве образованы параллельными переносами группы ГО той же размерности на некоторую константу [4], при чем все группы объектов одинаково ориентированы к краю листа. На рис.2 представлен пример регулярного размещения.

Рис. 2. – Регулярное размещение ГО в полосе

Остальные укладки считают нерегулярными.
Задача регулярного размещения ГО достаточно хорошо изучена. Для ее решения используется метод аппроксимации и декомпозиции, относящийся к точным методам [5]. Данный метод считают универсальным в решении фигурных задач. Однако применение его к классу нерегулярного раскроя затруднено, ввиду его эффективности только при сравнительно небольшом числе ГО, близких по своей форме к элементарным ГО. При увеличении количества ГО такой метод не позволяет формировать рациональную карту раскроя и перестает отвечать требованиям скорости и надежности работы.
Решение задачи фигурного нерегулярного раскроя точными методами практически невозможно как ввиду сложности самих ГО, так и в сложности достижения точного результата. При попытке получения точного решения таких задач приходится использовать достаточно сложный математический аппарат, как например, в работах [6] или [7], однако, требуемая точность решения может быть не достигнута.
В настоящее время ведется активный поиск новых эффективных алгоритмов и подходов к решению задачи нерегулярного размещения ГО.
Для решения проблемы нерегулярного фигурного раскроя достаточно часто используют эвристические методы [8]. В случае применения эвристического метода на единице операции, решения оперируют геометрическими преобразованиями каждого отдельно взятого ГО. Среди таких методов наибольшей популярностью пользуются имитация отжига, генетический алгоритм, поиск с запретами [9]. Имитация отжига и поиск с запретами характеризуются «прокладыванием» маршрута в пространстве поиска, который является последовательностью решений, где каждое решение является соседним для предыдущего относительно некоторой окрестности. В генетическом алгоритме для нахождения очередного нового решения используются процедуры скрещивания и целенаправленных мутаций (изменений, происходящих случайным образом).
В работе [10] предложено к решению задачи нерегулярного раскроя плоских геометрических объектов использовать метод последовательного уточнения оценок (SVC). Применение SVC к задаче нерегулярной упаковки предполагает использование процедуры формирования приоритетного списка ГО по «жадному» принципу вместо жестко зафиксированного списка.
В работе [11] для решения задачи нерегулярного размещения предложен алгоритм метода комбинаторной оптимизации (GRASP). GRASP представляет собой итерационный процесс, в котором каждая итерация состоит из стадии конструирования возможного решения и стадии локального поиска в окрестностях построенного решения. Более подробно данный алгоритм описан в [12]. Идея алгоритма локального поиска заключается в следующем: схожие решения часто ведут себя подобным образом, поэтому даже незначительные модификации решений обычно влекут небольшие и объяснимые изменения в их качестве, что позволяет получить лучшие решения.
Авторами [13] предложен гибридный алгоритм оптимального размещения лекал, совмещающий в себе идеи муравьиных колоний и «жадной» стратегии. Основной идеей алгоритма является совмещение фигур по прямым линиям. Идеи метода муравьиной колонии основаны на сборе статической информации о наиболее удачных найденных решениях.
В работе [14] при решении задач нерегулярного фигурного раскроя наряду с общеизвестной аппроксимацией прямоугольниками предлагается объединение фигурных объектов в блоки или куски (bit), где под блоком понимается набор деталей, положения которых зафиксированы относительно друг друга.
В работах авторов [15] и [16] сформулирован алгоритм анализа локальных характеристик формы геометрических объектов. Данный метод относится к сложным многопроходным эвристикам. Идея данного алгоритма заключается в стыковке двух деталей (выпуклой и вогнутой) только по трем последовательным ребрам, при этом деталь аппроксимируется многоугольником. Далее методом перебора выбираются три «лучших» ребра, если произошло пересечение деталей, то выполняется процедура сдвига по направлению биссектрисы одного из углов. Алгоритм решает проблему фиксированного количества положений и ориентаций ГО на заданной плоскости.
Наиболее перспективным для решения задачи нерегулярного размещения геометрических объектов является адаптация метаэвристических методов локального поиска в комбинации с методами моделирования геометрических преобразований, основанных на выполнении условий взаимного непересечения [10], [17]. Малоизученным метаэвристическим методом плотного размещения ГО в односвязной и многосвязной областях является использование сплайнов и примитивов для анализа локальных характеристик формы.
В итоге представим следующую классификацию подходов к решению задачи нерегулярного раскроя-упаковки сложных ГО в виде схемы (рис.3).

Рис. 3. – Классификация основных подходов к задаче нерегулярного раскроя-упаковки ГО

Стоит отметить, что задача трехмерного нерегулярного раскроя слабо изучена. Но тем не менее были предприняты попытки ее решить. Например, в [18] предложен метод на основе годографов.
Наиболее приемлемым подходом к решению задачи Р-У является группировка гетерогенных геометрических объектов с учетом локальных форм границ и накопление сформированных таким образом блоков для последующего размещения на заданной плоскости. Такой подход является малоизученным и новым в разработке алгоритмов для задачи раскроя-упаковки и гарантирует максимально возможное плотное размещение гетерогенных деталей. Тем не менее разработка новых методов решения задачи нерегулярного раскроя по прежнему остается важным направлением оптимизации производства и решения задач экономии ресурсов [18,19,20].

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

Литература: