|
Дискретный анализ и исследование операций, 2010, том 17, выпуск 4, страницы 43–66
(Mi da617)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Алгоритм имитации отжига для решения задач двумерной прямоугольной упаковки в контейнеры с запрещёнными областями
А. С. Рудневab a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
b Новосибирский гос. университет, Новосибирск, Россия
Аннотация:
Рассматривается задача двумерной прямоугольной упаковки в контейнеры с запрещёнными областями. Данная задача обобщает известную NP-трудную задачу упаковки в контейнеры. Разработаны кодирующие схемы для представления решений гильотинной и негильотинной задач, учитывающие специфику задачи с запрещёнными областями. На их основе разработан алгоритм имитации отжига для нахождения приближённого решения задачи. Начальное решение строится при помощи жадной эвристики, что позволяет начать поиск с низкой температуры. При каждой смене температуры осуществляется процедура уплотнения. Она позволяет концентрировать небольшие предметы на отдельных листах, что облегчает их разгрузку. Проведённые численные эксперименты свидетельствуют о высокой эффективности новых кодировок и о малой погрешности получаемых решений. Ил. 2, табл. 5, библиогр. 11.
Ключевые слова:
упаковка в контейнеры, кодирующая схема, имитация отжига.
Статья поступила: 01.09.2009 Переработанный вариант: 14.04.2010
Образец цитирования:
А. С. Руднев, “Алгоритм имитации отжига для решения задач двумерной прямоугольной упаковки в контейнеры с запрещёнными областями”, Дискретн. анализ и исслед. опер., 17:4 (2010), 43–66
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da617 https://www.mathnet.ru/rus/da/v17/i4/p43
|
Статистика просмотров: |
Страница аннотации: | 1493 | PDF полного текста: | 458 | Список литературы: | 55 | Первая страница: | 28 |
|