Том 17, номер 4, 2010 г., Стр. 43-66

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

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

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

Руднев Антон Сергеевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: anton.rudnev@gmail.com

Статья поступила 1 сентября 2009 г.
Исправленный вариант — 14 апреля 2010 г.