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

Аннотация

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