научная статья по теме АЛГОРИТМЫ ЭФФЕКТИВНОГО РЕШЕНИЯ ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ОБЪЕКТОВ Математика

Текст научной статьи на тему «АЛГОРИТМЫ ЭФФЕКТИВНОГО РЕШЕНИЯ ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ОБЪЕКТОВ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2013, том 53, № 10, с. 1639-1648

УДК 519.247

АЛГОРИТМЫ ЭФФЕКТИВНОГО РЕШЕНИЯ ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ОБЪЕКТОВ

© 2013 г. А. В. Чеканин, В. А. Чеканин

(127994Москва, Вадковский пер., 1, ФГБОУВПО МГТУ "Станкин") e-mail: avchekanin@rambler.ru; vladchekanin@rambler.ru Поступила в редакцию 21.06.2012 г. Переработанный вариант 26.03.2013 г.

Рассматривается NP-полная задача ортогональной упаковки объектов произвольной размерности в общем виде. Предложена новая модель представления объектов в контейнерах, обеспечивающая быстрое конструирование ортогональной упаковки. Предложены новые эвристики размещения ортогональных объектов. Разработаны однопроходной эвристический и мультиметодный генетический алгоритмы оптимизации решения задачи ортогональной упаковки, повышающие плотность размещения объектов. Проведены вычислительные эксперименты на тестовых задачах двухмерной и трехмерной ортогональной упаковки объектов. Библ. 20. Фиг. 7. Табл. 4.

Ключевые слова: задача упаковки, задача ортогональной упаковки, распределение ресурсов, модель представления объектов, декодер, эвристики, генетический алгоритм, эволюционный алгоритм, мультиметодный генетический алгоритм, вычислительный эксперимент.

DOI: 10.7868/S0044466913100049

ВВЕДЕНИЕ

Решение задачи ортогональной упаковки имеет широкий спектр применения в различных сферах экономической деятельности, что объясняет повышенный интерес исследователей к совершенствованию методов оптимального распределения ортогональных ресурсов.

Сложность решения задачи упаковки обусловлена ее принадлежностью к классу МР-полных задач (см. [1]). Практическое применение методов решения задач упаковки, использующих полный перебор вариантов, оказывается неэффективным из-за больших затрат временных ресурсов. В связи с этим одним из наиболее перспективных направлений исследований является разработка и совершенствование различных приближенных, а также эвристических методов решения задач упаковки, в том числе эволюционных алгоритмов (см. [2]—[7]). Большую роль при решении задач ортогональной упаковки различной размерности играет выбор эффективного способа конструирования упаковки.

1. ПОСТАНОВКА ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ОБЪЕКТОВ

В общем виде задача ортогональной упаковки объектов размерности Б описывается следующим образом: имеются набор N ортогональных контейнеров (Б-мерных параллелепипедов) с габаритными размерами {ж], Ж2,..., Ж^},] е {1, ..., N1, и набор п ортогональных объектов (Б-мер-

12 В

ных параллелепипедов) с габаритными размерами {, , ..., }, I е {1, ..., п}. Обозначим по-

12 В

ложение объекта I в]-м контейнере в виде (Ху ; Ху ; ...; Ху ). Необходимо разместить все объекты в минимальном числе контейнеров при выполнении следующих условий (см. [8]).

1) ребра размещенных в контейнере ортогональных объектов параллельны ребрам этого контейнера;

1639

Фиг. 1. Процесс решения задачи упаковки.

2) размещенные объекты не перекрывают друг друга, т.е.

* й ^ й * й ^ й (Хц > Хк] + ) V (Хк] > Хц + М/)

V/ е{ 1, ..., Л), У^ е{ 1.....В}, V/, к е{ 1.....л}, /ф к;

3) размещенные объекты не выходят за границы контейнеров, т.е.

(х// > 0)л(х// + ^ < V/ е{ 1, ..., , У^ е{ 1, ..., В}, V/ е{ 1.....л}.

Процесс решения задачи упаковки можно представить в виде схемы, приведенной на фиг. 1.

Решение задачи ортогональной упаковки объектов произвольной размерности может быть закодировано строкой размещения, содержащей последовательность выбора объектов для их размещения в контейнерах. Наибольшее распространение получило формирование решений с использованием алгоритмов многокритериальной оптимизации, преимущественно эволюционных алгоритмов (см. [2], [7], [9]). Конструирование упаковки по заданной в строке размещения последовательности объектов выполняется блоком декодирования.

2. МОДЕЛЬ ВИРТУАЛЬНЫХ ОБЪЕКТОВ

При конструировании упаковки используются различные модели представления объектов в контейнерах, среди которых наибольшее распространение получили блочная (см. [10]), узловая (см. [11]) и графовая (см. [8], [12]) модели. В узловой модели присоединение объектов выполняется к особым точкам пространства контейнера, называемыми узлами. Каждый узел описывается кортежем

ик = <Хк, а, Ь),

12 В

где к - номер узла; Хк = {хк , хк , ..., хк } — вектор, описывающий положение этого узла в ^-мерном ортогональном контейнере; а - присоединенный к узлу к ортогональный объект; Ь - вариант ориентации этого объекта в контейнере. Присоединение объектов возможно только к так называемым свободным узлам (не содержащим присоединенные объекты).

Разработанная авторами модель виртуальных объектов является производной от узловой модели. В новой модели все узлы содержат дополнительную информацию о наибольших габаритных размерах ортогональных объектов (так называемых виртуальных объектов), которые могут быть присоединены к узлам контейнера. Каждый узел описывается кортежем

и* = <Хк, Рк, а, Ь),

12 В

где Рк = {рк , рк , ..., рк } — вектор, описывающий виртуальный объект, содержащий габаритные размеры ортогонального объекта наибольшего объема, который может быть присоединен к узлу к без перекрытий с упакованными объектами и размещен целиком внутри контейнера. Например, при размещении в точке {0, 0} пустого двухмерного прямоугольного контейнера с габаритными размерами Ь х Ж прямоугольника с габаритными размерами I х w, в углах размещенного объекта формируются новые узлы, содержащие виртуальные объекты, описываемые векторами Р = {Ь - I; Ж}, Р = {Ь - I; Ж - И и Р = {Ь; Ж - *}.

В модели виртуальных объектов при добавлении в контейнер нового объекта вместо проверки на перекрытие со всеми размещенными в контейнере объектами необходимо выполнить единственную проверку нахождения размещаемого объекта целиком внутри виртуального объекта

узла к, к которому он присоединяется: (мЛк < рк) Уй е {1, ..., Б}, за счет чего повышается скорость размещения.

1

1

Фиг. 2. Виртуальные объекты узла в трехмерном контейнере.

3. ДЕКОДЕР СТРОКИ РАЗМЕЩЕНИЯ Packer

Декодирование строки размещения и конструирование упаковки выполняет декодер. Разработанный унифицированный декодер размещения Packer может быть применен при использовании узловой и производных от нее моделей представления объектов в контейнерах для декодирования строк решений, содержащих последовательности размещаемых ортогональных объектов произвольной размерности.

Алгоритм работы декодера размещения Packer для модели "виртуальные объекты"

Шаг 1. Выбрать очередной объект i из строки размещения. Выбрать первый контейнер j, содержащий, как минимум, один свободный узел. Если выбраны все объекты, выполнить переход к шагу 4.

Шаг 2. Произвести последовательный поиск свободного узла k текущего контейнера j, к которому возможно присоединить текущий объект i (проверка выполнения условия wd < pdk Vd е е {1, ..., D}). Если искомый узел не найден, выполнить переход к следующему контейнеру j :=j + 1 и повторить шаг 2. Если среди всех контейнеров не найден искомый узел, то выполнить переход к шагу 1.

Шаг 3. Присоединить объект i к найденному узлу k контейнера j. Образовать в углах размещенного объекта новые узлы контейнера и определить векторы их виртуальных объектов. Выполнить сортировку узлов контейнера в порядке убывания приоритета присоединения к ним объектов, т.е. для любого узла k контейнера j должно выполняться следующее неравенство:

Выполнить переход к шагу 1.

Шаг 4. Завершить работу декодера.

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

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

4. МУЛЬТИМЕТОДНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ОПТИМИЗАЦИИ РЕШЕНИЯ ЗАДАЧИ ДВУХМЕРНОЙ ОРТОГОНАЛЬНОЙ УПАКОВКИ

Оптимизация решения задачи ортогональной упаковки может быть выполнена с помощью эвристических и эволюционных алгоритмов (см. [2]—[7], [9]). Проведенные в [6], [13] исследования показали высокую эффективность применения генетических алгоритмов (ГА) при решении задачи ортогональной упаковки объектов. Альтернативой классическому ГА является мультиме-тодный генетический алгоритм (МГА), в основу которого положена мультиметодная технология, приведенная в [5]. При решении задачи упаковки с помощью МГА решение задачи кодируется в виде последовательности эвристик, представляющих собой алгоритмы размещения объектов.

Для оптимизации решения задачи ортогональной упаковки применительно к модели виртуальные объекты разработаны новые эвристики размещения, оптимизирующие как последовательность размещения объектов, так и порядок использования свободного пространства контейнеров:

1) WF (Width Fit): присоединение к узлу k текущего контейнера наиболее подходящего объекта i вдоль выбранного направления упаковки l:

(Рк - w) —- min, wi < pdk, Ук e{ 1, ..., D};

2) SF (Square Fit): присоединение к узлу k текущего контейнера первого подходящего объекта i с максимальным объемом:

л

d Wi

vd = 1 d = 1 '

пp - п

min, wd < pk,, yd e{ 1, ..., D};

3) NWF (Next Width Fit): присоединение первого объекта (i = 1) из списка упорядоченных по одному из габаритных размеров неразмещенных объектов к ближайшему свободному узлу k текущего контейнера:

УН < k3d : pi < wd, wd <pdk, yd e{ 1,..., D}; (1)

4) NSF (Next Square

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком