Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

В работе рассматривается обобщение известной NP-трудной задачи прямоугольной упаковки в контейнеры. Имеется конечное множество предметов прямоугольной формы. Каждый предмет имеет ширину и высоту. Заданы прямоугольные контейнеры. Каждый контейнер имеет свои размеры и конечный список запрещенных областей прямоугольной формы. Часть предметов может пересекаться с запрещенными областями. Стороны предметов и запрещенных областей параллельны сторонам контейнеров. Требуется уложить все предметы в минимальное число контейнеров с учетом запрещенных областей. Рассматриваются четыре варианта задачи упаковки в контейнеры: гильотинная, негильотинная, с поворотами предметов на девяносто градусов и без них.

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

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

Алгоритм тестировался на случайно сгенерированных примерах. Сравнение с нижними оценками свидетельствует о высокой эффективности новых кодировок и о малой погрешности получаемых решений. Также были рассмотрены тестовые примеры С. Мартелло, А. Лоди и Д. Виго, предложенные для классической задачи упаковки в контейнеры без запрещенных областей. Разработанный алгоритм нашел лучшие решения для большинства примеров.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2006, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2006, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:51)