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

Рассматривается задача двумерной прямоугольной упаковки в контейнеры с запрещёнными областями. Данная задача обобщает известную NP-трудную задачу упаковки в контейнеры. Разработаны кодирующие схемы для представления решений гильотинной и негильотинной задач, учитывающие специфику задачи с запрещёнными областями. На их основе разработан алгоритм имитации отжига для нахождения приближённого решения задачи. Начальное решение строится при помощи жадной эвристики, что позволяет начать поиск с низкой температуры. При каждой смене температуры осуществляется процедура уплотнения. Она позволяет концентрировать небольшие предметы на отдельных листах, что облегчает их разгрузку. Проведённые численные эксперименты свидетельствуют о высокой эффективности новых кодировок и о малой погрешности получаемых решений. Ил. 2, табл. 5, библиогр. 11.