Алгоритмы локального поиска для задач двумерной упаковки

• Автор: Руднев, Антон Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 104 с. : ил.

Оглавление
Введение
1 Алгоритмы локального поиска для задачи упаковки прямоугольников в прямоугольную область минимальной площади

1.1 Введение

1.2 Математическая постановка задачи

1 3 Решение задачи с помощью коммерческого пакета.

1 4 Кодирующая схема Ориентированное дерево.

I 5 Кодирование ориентированных деревьев

1.6 Окрестность.

1.7 Использование алгоритмов гюкального поиска для решения

задачи прямоугольной упаковки . .

1.7.1 Алгоритм локального спуска.
1.7.2 Алгоритм имитации отжига.
1.7.3 Диверсификация поиска
1.7.4 Гибридный алгоритм.
1 8 Численные эксперименты
1.8 1 Влияние диверсификации поиска
1.8.2 Гибридный алгоритм с диверсификацией поиска .
1.9 Выводы к главе 1
2 Алгоритм имитации отжига для задач прямоугольной упаковки в контейнеры с запрещенными областями
2.1 Введение
2.2 Математические постановки задач
2.3 Кодирующие схемы
2.4 Окрестность
2.5 Модифицированный алгоритм имитации отжига
2.6 Начальное решение
2.7 Алгоритм РАЗГРУЗКА.
2.8 Численные эксперименты.
2.8.1 Примеры прямоугольной упаковки с запрещенными областями
2.8.2 Примеры классической прямоугольной упаковки .
2.8.3 Использование пакета
2.9 Выводы к главе 2.
3 Алгоритм вероятностного поиска с запретами для задачи упаковки кругов и прямоугольников в полосу
3.1 Введение.
3.2 Математическая постановка задачи.
3.3 Двухконтактные кодировки.
3.4 Окрестность
3.5 Алгоритм вероятностного поиска с запретами
3.6 Численные эксперименты.
3.6.1 Влияние рандомизации и длины списка запретов . . .
3.6.2 Упаковка кругов и прямоугольников
3.6.3 Использование пакета
3.7 Выводы к главе 3.
Заключение
Список литературы


В ходе вычислительных экспериментов с помощью разработанного алгоритма были найдены новые рекордные значения целевой функции для семи примеров из электронных библиотек MCNC и GSRC с числом предметов от до 0. Исследован новый класс задач прямоугольной упаковки в контейнеры с запрещенными областями. Получены математические модели в терминах частично-целочисленного программирования. Для решения задач разработаны новые кодирующие схемы. На их основе разработан модифицированный алгоритм имитации отжига, позволяющий решать четыре типа задач с запрещенными областями. Экспериментально установлено, что алгоритм позволяет находить решения с малой погрешностью, в том числе и оптимальные решения на примерах с числом предметов до . Для задачи упаковки кругов и прямоугольников в полосу разработана оригинальная процедура декодирования, восстанавливающая по заданной перестановке двухконтактную упаковку предметов. Разработан алгоритм вероятностного поиска с запретами с адаптивно изменяемой рандомизацией окрестности. В результате численных экспериментов для четырех известных примеров упаковки кругов в полосу получены новые рекордные значения целевой функции. Практическая значимость работы. Предложенные в диссертационной работе алгоритмы могут быть использованы для эффективного решения следующих задач: упаковка прямоугольников в прямоугольную область минимальной площади, упаковка прямоугольников в контейнеры с запрещенными областями, упаковка кругов и прямоугольников в полосу минимальной длины. Разработанные алгоритмы можно использовать в практических расчетах и включать их в автоматизированные системы проектирования и управления. Апробация работы. Российская конференция «Дискретный анализ и исследование операций», г. Международный симпозиум по исследованию операций (СЖ), г. Времен, , г. Карлсруэ, и г. Всероссийская конференция «Проблемы оптимизации и экономические приложения», г. Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», г. Новосибирск, и п. Международная школа-семинар по раскрою и упаковке (ЕБЮиР), г. Российская конференция «Математика в современном мире», г. Байкальская международная школа-семинар «Методы оптимизации и их приложения», г. Научные семинары Института математики СО РАН. Публикации. По теме диссертации опубликовано работ, в том числе 1 статья в рецензируемом журнале из списка ВАК. Структура и объем работы. Диссертация состоит из введения, трех глав и заключения. Объем работы составляет 4 страницы машинописного текста, включая рисунка, таблиц и библиографический список, содержащий наименования. Краткое содержание работы. В первой главе рассматривается задача упаковки конечного множества прямоугольников в прямоугольную область минимальной площади. Исследуются возможности представления решений данной задачи с помощью ориентированных деревьев. Оценивается влияние процедур уплотнения и локального спуска на относительную погрешность и время работы алгоритма имитации отжига, разработанного для решения поставленной задачи. В разд. Приводится обзор уже полученных результатов. Рассматриваются основные характеристики кодирующих схем для задач прямоугольной упаковки. В разд. Разд. GAMS для решения сформулированной задачи. Указанный пакет использует методы глобальной и локальной оптимизации и позволяет находить оптимальные решения. Указываются границы применимости такого подхода. В разд. Такая кодировка обладает линейной трудоемкостью декодирования и относительно небольшим пространством решений, что делает ее эффективной при использовании в алгоритмах локального поиска. В разд. Определяется свойство достижимости. Доказывается, что используемая окрестность обладает данным свойством. В разд. Предлагается новая процедура уплотнения упаковки прямоугольников, аналогичная Г-поздним расписаниям в календарном планировании. Действие процедуры заключается в поочередном смещении всех прямоугольников к нижней, правой, верхней и левой границам упаковки. Смещение реализуется за счет смены типов кодирующих деревьев. Процедура уплотнения, встроенная в алгоритмы локального поиска, меняет код решения, не меняя структуру самой упаковки.