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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Вестник Башкирского университета. 2006№ 3.
5
УДК 004. 031. 43
КОНСТРУКТИВНАЯ ЭВРИСТИКА ДЛЯ ЗАДАЧИ ПРЯМОУГОЛЬНОЙ УПАКОВКИ
Валеева А. Ф.
Рассматривается задача прямоугольной упаковки в полосу заданной ширины, являющейся МР-трудной. Для ее решения разработана конструктивная эвристика, основанная на методах решения задачи динамического программирования. Статья написана по материалам доклада на Международной уфимской зимней школе -конференции по математике и физике для студентов, аспирантов и молодых ученых, БашГУ-2005 г.
Введение
Задачи раскроя-упаковки (Cutting and Packing, C& amp-P) имеют большое практическое значение и являются типичными представителями NP-трудных проблем. Для их решения применяются точные и эвристические методы. Ввиду неполиномиальной сложности точных алгоритмов, авторами многих работ уделяется значительное внимание эвристическим методам.
Для решения задач прямоугольной упаковки разработана конструктивная эвристика — метод динамического перебора (Dynamic Sorting, DS), основанный на методах динамического программирования. Конструктивные эвристики строят решение из начального частично построенного решения путем добавления к нему новой компоненты решения до тех пор, пока решение не будет построено полностью.
В статье рассматривается задача прямоугольной упаковки в полубесконечную полосу (1. 5DBP).
1. Постановка задачи двухмерной упаковки 1. 5DBP
Задача 1. 5DBP. Исходная информация для задачи 1. 5DBP задается следующим набором данных
& lt-W, m, w, l>- ,
где W — ширина полубесконечной полосы- m — количество прямоугольников- w=(w1,w2,…, wi,… wm) — вектор
ширин прямоугольников- l=(l1,l2,., li,… lm) — вектор длин прямоугольников. Введем прямоугольную систему
координат XOY, у которой ось ОХ направлена по длине полосы, а ось ОУ — по ширине полосы. Решение 1. 5DBP представляются в виде набора элементов DP = & lt-X, Y& gt-, гдеХ=(х1, х2,…,. хъ…, хт), У=(уъ у2,…, у,…, ут) -векторы координат прямоугольников, (х. уi) — координаты нижнего угла прямоугольника соответственно по оси X и Y. Набор элементов DP = & lt-X, Y& gt- называется допустимой прямоугольной упаковкой, если выполнены следующие условия:
1. стороны прямоугольников параллельны сторонам полосы в упаковке-
2. прямоугольники взаимно не перекрывают друг друга: для i ф j: i, j = 1,…, m
((xj & gt- xj + lj) v (xj & gt- x + h)) v ((У- & gt- yj + wj) v (yj & gt- Уг + w))
3. прямоугольники не перекрывают стороны полосы: для всех -=1,…, m
(x i & gt- 0) А (У- & gt- 0) A ((y. + w-) & lt- W) A ((x +l-) & lt- L) —
При выполнении условий 1−3 требуется найти такой допустимый раскрой полосы DP = & lt-X, Y& gt-, для которого длина занятой части полосы L = max (x +1) достигала бы минимума.
-=-,…, m — -
2. Конструктивный метод динамического перебора для решения задачи 1. 5DBP
Рассмотрим произвольную двухмерную упаковку полубесконечной полосы (Rectangular Packing, RP) ширины W прямоугольниками заданных размеров (w--l-), i=l, 2,…, m. Каждому прямоугольнику, размещенному в полосе, присвоим порядковый номер i. Назовем кортежем список (1,2…, r), где 1,2…, r — номера прямоугольников. Пусть множество K — это множество всех кортежей. Тогда RP может быть представлена в виде набора кортежей (см. рис. 1).
W=5, т=7.
j 1 2 3 4 5 6 7
Wi 1 2 3 4 3 1 2
h 1 2 2 2 3 5 5
Множество кортежей К:
{(5,7), (2,6), (1,3), (4)} длина занятой части полосы 1=9.
Рис. 1. Пример RP Задача 1. 5DBP является частным случаем известной Problem, SSP):
задачи поиска сумм подмножеств (Subset Sum
6
раздел МАТЕМАТИКА и МЕХАНИКА
Задача SSP. Имеется натуральное число W и множество натуральных чисел w, i=1,2,…, m. Требуется определить, существует ли такое подмножество I множества {1,2,…, m}, что ^ wi = W.
ieI
В [1] описан алгоритм ASSP решения задачи SSP, трудоемкость которого зависит от двух параметров: m и W. Он строит подмножества M, i=1,2,…, m, содержащие числа wi, i=1,2,…, m и их всевозможные суммы, не превышающие W. В качестве wi, i=1,2,…, m, в SSP рассматриваются ширины заданных прямоугольников, W -ширина полосы. Рассмотрим модифицированную задачу SSP (Modified SSP, MSSP):
Имеется натуральное число W и множество натуральных чисел wi, i=1,2,…, m. Требуется сформировать такое множество К допустимых кортежей, чтобы выполнялось условие:wi & lt- W, где I — подмножество
ieI
множества {1,2,…, m}. Причем добавление любого элемента из I, не входящего в кортеж, нарушает это условие.
Для решения MSSP применим алгоритм АSSP с некоторой модификацией, которая заключается в том, что для каждой суммы w+wt& lt- W, i=1,2,…, m, weMi. 1, находится кортеж из номеров прямоугольников, ширины которых вошли в сумму w+w,. При этом кортеж находится даже в том случае, если число w+wi& lt- W уже есть в множестве M. Это позволяет находить не одну, а несколько комбинаций чисел wi, i=1,2,…, m, которые в сумме будут давать число we M, i=1,2,…, m. Совокупность найденных кортежей образует множество K. Рассмотрим пример решения MSSP. Пусть дано: w=(3,1,2) — W=3. Тогда ширине прямоугольника w1=3 соответствует кортеж (1) — ширине w2=1- кортеж (2) — ширине w3=2 — кортеж (3) — сумме ширин w2+w3=1+2=3 — кортеж (2,3). При этом множество K содержит следующие кортежи: K={(1), (2), (3), (2,3), (3,2)}.
Модифицированный алгоритм ASSP (MASSP).
1. M0= {0}, K=0
2. Для i=1,2,…, m выполнить:
2.1. Построение множеств m:
MrMi
для каждого целого числа w из Mi-1 выполнить: добавить к Mi целое число w+wi, если w+w& lt- W и w+w,? M-
2.2. Формирование множества кортежей K:
для каждого целого числа w из Mi-1 выполнить: найти кортежи, состоящие из порядковых номеров от 1 до i и равные w+wi, если w+w,& lt- W-
3. Найти wmax= max w и соответствующие wmax кортежи из K.
weMn
Метод динамического перебора DS для задачи 1. 5DBP состоит из следующих основных процедур: процедуры создания множества компонент-кортежей K на базе алгоритма MASSP- процедуры формирования дерева вариантов упаковок, в котором вершины — ширины w+w, (корневая вершина — ширина полосы), а ветви — кортежи, причем пути от корня дерева до листьев позволит построить упаковки- процедуры, осуществляющей обход дерева вариантов упаковок, из которого случайным образом выбираются ветви для формирования RP. Среди полученных RP ищется упаковка с минимальным значением целевой функции. Кроме того, может быть найдено множество различных вариантов упаковок с одной и той же длиной занятой части полосы.
Заключение
Для исследования разработанного алгоритма для решения задачи 1. 5DBP-упаковка проводились численные эксперименты по известной методике P. Schwerin и G. Wascher [2]. Целью эксперимента являлось выяснение качества работы метода DS на тестовых наборах большой размерности (до m=1000). Параметрами задачи 1. 5DBP являются: m — количество прямоугольников- W — ширина полосы- w1, w2 — нижняя и верхняя граница для ширины прямоугольников в отношении к ширине полосы, соответственно- l1? l2- нижняя и верхняя граница для длины прямоугольников в отношении к ширине полосы, соответственно. Использовались наборы «малые предметы» (w1=0. 05- w2=0. 1- l1=0. 1- l2=0. 15), «средние предметы» (w1=0. 25- w2=0. 35- l1=0. 35- l2=0. 45) и «малые и большие предметы» (w1=0. 25-w2=0. 05- l1=0. 05-l2=0. 95) при W=1000 и m=100, 250, 500, 750, 1000. Для каждого класса было просчитано 50 примеров, количество запусков ?=10. Как показали результаты эксперимента, коэффициент раскроя метода DS на трудных задачах («средние предметы») большой размерности (при m=1000) — кРа=99. 58−95. 58%, на остальных задачах — КРА=95. 58−92. 58%.
Работа поддержана Российским фондом фундаментальных исследований, проект 03−01−7 002
ЛИТЕРАТУРА
1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.- М.: Мир, 1985, 512с.
2. Schwerin P., Wascher G. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP // International Transactions in Operational Research. 1997. № 4. P. 337−389.

ПоказатьСвернуть
Заполнить форму текущей работой