Оптимизация компоновки трехмерных геометрических объектов на основе годографа вектор-функции плотного размещения

Аннотация

Р.Р. Ягудин

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

Ключевые слова: упаковка, ГФПР, непересечение, оптимизация, компоновка, невыпуклые многогранники

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

Введение

Обзор работ по проблеме упаковки/размещения трехмерных геометрических объектов (ГО), которая востребована во многих областях человеческой деятельности (компоновка [4], упаковка грузов, раскрой кристаллов и т.д.), позволяет сделать вывод, что сложность решения рассматриваемой задачи обуславливает отсутствие эффективных алгоритмов её решения. Большинство работ сводится к размещению простых геометрических фигур (параллелепипедов, цилиндров, сфер и т.д.). Поэтому поиск новых подходов и алгоритмов для решения задачи размещения трехмерных ГО остается актуальным.
Вычислительная сложность решения задачи трехмерной упаковки в общей постановке вынуждает вводить ряд упрощений, порой достаточно сильно сужающих область допустимых решений, однако позволяющих находить рациональные упаковки с приемлемыми затратами вычислительных ресурсов.
Одно из самых распространенных упрощений - фиксация ориентации ГО в пространстве или использование набора фиксированных ориентаций каждого из них.
В данной статье обсуждается задача размещения ориентированных произвольных невыпуклых многогранников сложных форм.

Постановка задачи

Задачу  плотной  упаковки  ориентированных ГО  в  трехмерном  пространстве  можно  свести  к  решению  следующей  математической  задачи.
Имеется  набор  ориентированных трёхмерных ГО, каждый из которых имеет свою собственную систему координат.
Область упаковки , представляет собой прямоугольный параллелепипед
,
у которого  - длина,  - ширина объекта  рассматриваются как константы, а  - высота объекта , как переменная величина.
Введем следующие обозначения:
 - смещение объекта  на вектор ,
 - граничные точки объекта ,
 - внутренние точки объекта ,
 - минимальная высота объекта  для параметров размещения  объектов множества .
Упаковкой назовем такой набор параметров размещения  объектов , при котором выполняются следующие условия:
,          
т. е. никакие два объекта не пересекаются между собой, и все объекты находятся внутри  области размещения.
Требуется для ГО  найти такую упаковку , чтобы  высота области размещения была минимальной:
                                                                   

Подходы к решению

Эту  проблему  можно  рассматривать  как  задачу  математического программирования [1], определенную  на  множестве  допустимых  размещений  объектов в заданной  области (т.е.   размещений, удовлетворяющих  ограничениям).
Одним из применяемых способов для решения таких задач является метод покоординатного спуска (метод Гаусса-Зайделя), который приводит к разбиению процесса решения на две части:
1. Моделирование плотного движения объектов в области размещения - внутренняя часть.
2. Формирование и изменение последовательности упаковываемых объектов - внешняя (комбинаторная часть).
Основной целью внутренней процедуры является обеспечение условий взаимного непересечения объектов. Для решения этой подзадачи рассмотрим подход, который базируется на понятии годографа функции плотного размещения ГФПР, разработанного и развитого до Ф-функций в харьковской школе академика Ю.Г.Стояна [5], являющейся мировым научным лидером в этой области уже на протяжении многих десятилетий.
Под функцией плотного размещения двух соприкасающихся ГО понимается зависимость расстояния между некоторыми точками (полюсами) этих объектов от их взаимного плотного размещения (). Годограф вектора, направленного от одного полюса к другому, при плотном перемещении одного (подвижного) объекта вокруг другого (неподвижного) называется годографом функции плотного размещения (ГФПР). Таким образом, для упаковываемого объекта ГФПР представляет собой границу области, запрещенной для размещения этого объекта.

Описание особенностей применяемого метода решения

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

1. Моделирование плотного движения объектов в области размещения.

Для обеспечения условий взаимного непересечения объектов между собой и с границей области размещения, требуется построить ГФПР Gij всех пар многогранников и для каждого многогранника построить ГФПР  GQi к внешности области зоны размещения  (хотя в этом случае эта область является невыпуклой, но ГФПР для нее строится тривиально).
Если рассматривать множество допустимых для размещения объекта точек, то оно представляет собой объединение областей, ограниченных различными ГФПР (в общем случае оно может быть несвязным). Точки локальных экстремумов будут являться вершинами вогнутостей, лежащими на границах этого объединения. Если один из пары объектов невыпуклый, то ГФПР будет также невыпуклым. Значит вершины невыпуклых ГФПР, образующие вогнутости, также являются точками локальных экстремумов. Следовательно, точка занесения при упаковке трехмерных невыпуклых многогранников может быть найдена в результате рассмотрения следующих случаев (для простоты описания будем считать, что номера объектов соответствуют позициям в приоритетном списке):

1. Вершина с минимальными координатами по Oz, Oy и Ox ГФПР размещаемого многогранника к области размещения  - GQ_i. (Это соответствует следующему расположению: размещаемый многогранник касается трех граней области размещения.)
2. Вершина, являющаяся точкой пересечения ребер ГФПР размещаемого многогранника  к области размещения  - GQ_i и любых ГФПР размещаемого многогранника  к уже размещенным многогранникам  - . (Размещаемый многогранник касается одного из уже размещенных многогранников и двух смежных граней области размещения.)
3. Вершина, являющаяся точкой пересечения граней двух различных ГФПР размещаемого многогранника  к размещенным многогранникам  -  и грани ГФПР размещаемого многогранника  к области размещения  - GQ_i. (Размещаемый многогранник касается двух других уже размещенных многогранников и грани области размещения.)
4. Вершина, являющаяся точкой пересечения граней трех различных ГФПР размещаемого многогранника  к размещенным многогранникам  - . (Размещаемый многогранник касается трех других уже размещенных многогранников.)
5. Вершина вогнутости ГФПР размещаемого многогранника  к любому размещенному многограннику  - . (Размещаемый многогранник касается трех граней уже размещенного многогранника.)

В процессе размещения очередного многогранника, проанализировав все 5 случаев соприкосновений, получаем набор точек, каждая из которых является точкой локального экстремума. В целях минимизации высоты контейнера  из всего полученного множества выбирается точка с минимальной координатой по z, в случае совпадения z – с минимальной суммой координат x и y.
Для большей наглядности на рис.1 представлены примеры двумерных аналогов описанных случаев.
На рисунке тонкими линиями показаны границы объектов, жирными – ГФПР, тонкими пунктирными – границы размещаемого объекта при размещении в точке локального минимума, жирными пунктирными – границы объекта при его размещении в соответствии с глобальным минимумом. Жирными точками показаны полюса объектов. Квадратами помечены точки локального минимума не имеющие минимальной координаты по Oz.
Рассмотрим размещение четырех объектов по шагам, при этом на каждом шаге будем размещать объект с соответствующим номером:
Шаг 1: Точка локального минимума принадлежит вершине ГФПР объекта T₁ к зоне размещения Q - GQ₁. Зафиксируем полюс объекта T₁ в этой точке (Рис.1а).
Шаг 2: Найдено 2 точки локального минимума:
- одна из которых принадлежит вершине ГФПР объекта T₂ к упакованному объекту T₁ – G₁₂;
- одна - точка пересечения ГФПР объекта T₂ к области размещения Q - GQ₂ и ГФПР объекта T₂ к упакованному объекту T₁ - G₁₂.
Зафиксируем многоугольник T₂ в точке с минимальной координатой по Oz и затем по Ox – это нижняя точка пересечения G_Q2 и G₁₂ (Рис.1б).
Шаг 3: Найдено 2 точки локального минимума:
- одна из которых является точкой пересечения ГФПР объекта T₃ к упакованным объектам T₁ и T₂ - G₁₃ и G₂₃;
- одна - точка пересечения ГФПР объекта T₃ к области размещения Q - GQ₃ и ГФПР объекта T₃ к упакованному объекту T₂ - G₂₃.
Зафиксируем многоугольник T₃ в точке с минимальной координатой по Oz и затем по Ox – это точка пересечения G₁₃ и G₂₃ (Рис.1в).
Шаг 4: Точка локального минимума принадлежит вершине ГФПР объекта T₄ к упакованному объекту T₁ – G₁₄. Зафиксируем полюс объекта T4 в этой точке (Рис.1г).

При реализации данного подхода возникают задачи нахождения точки пересечения отрезка и многогранника, отрезка и грани, двух многогранников. Все они подробно рассмотрены в работе [2]. Для поиска ГФПР двух многогранников используется алгоритм, описанный в статье [3].

Рис.1. Размещение четырех объектов T₁, T₂, T₃ и T₄ в области Q:
а) годограф G_Q1 объекта T₁ и области размещения Q, точка занесения, соответствующая точке локального минимума (размещение первого объекта T₁ в пустой области Q);
б) годограф G_Q2объекта T₂ и области размещения Q, годограф G₁₂ объекта T₂ и объекта T₁, точка занесения (размещение второго объекта T₂  в области Q с размещенным объектом T₁);
в) годограф G_Q3 объекта T₃ и области размещения Q, годографы G₁₃ и G₂₃  объекта T₃ и объектов T₁ и T₂, точка занесения (размещение третьего объекта T₃  в области Q с размещенными объектами T₁ и T₂).
г) годограф G_Q4 объекта T₄ и области размещения Q, годографы G₁₄, G₂₄ и G₃₄ объекта T₄ и объектов T₁, T₂ и T₃, точка занесения (размещение четвертого объекта T₄  в области Q с размещенными объектами T₁, T₂ и T₃).
д) результат размещения объектов T₁, T₂, T₃ и T₄ в области Q

• 2.Формирование и изменение последовательности упаковываемых объектов

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

• 1.первый подходящий с упорядочиванием ППсУ (Рис.2.) объектов в порядке убывания объемов (простая схема), а также его улучшение – локальный поиск (циклическая схема);

Рис.2. Блок-схема, описывающая алгоритм ППсУ.

• 2.«жадный» метод с выбором на каждом шаге того объекта, который укладывается лучше других (совмещенная схема);
  3.GRASP (Greedy Randomized Adaptive Search Procedures – Жадные Рандомизированные Адаптивные Процедуры Поиска) является итеративным методом, при каждом запуске которого выполняются две процедуры:

- генерация начального решения;
- локальный поиск.
При каждой генерации могут быть использованы различные значения параметра случайности α. Этот параметр используется в критерии проверки возможности выбора объекта для размещения:
.         (1)
 – высота размещения объекта .
 – минимальная высота размещения по всем объектам.
 – максимальная высота размещения по всем объектам.
При α = 0 неравенство (1) преобразуется к виду , тогда любой объект  может быть выбран для размещения – «случайная» конструкция. При α = 1 неравенство (1) преобразуется к виду , тогда может быть выбран объект , у которого  – «жадная» конструкция. При любом значении α выбирается случайный объект из множества объектов удовлетворяющих неравенству (1).
Очевидно, что функция зависимости качества размещения от значения параметра α нелинейная. Поэтому генерацию начального решения следует производить со значениями α из диапазона [0, 1] с некоторым шагом Δα, начиная с 0.
Локальный поиск используется для поиска локального оптимума в окрестности каждого из сгенерированных решений, а затем дополнительно применяется к лучшему найденному.
GRASP является комбинацией совмещенной и циклической схем.

Рис.3. Блок-схема, описывающая алгоритм GRASP.

Рис.4. Блок-схема, описывающая процедуру генерации начального решения GRASP.

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

Описание алгоритмов

1. Определение точки размещения многогранника

Входные данные:
L, W – длина и ширина основания зоны размещения;
T – список всех многогранников;
j – индекс размещаемого объекта;
step – количество размещенных многогранников;
 – точки занесения размещенных многогранников.

Выходные данные:
u – координатыточки занесения.
НАЧАЛО РасчетПараметраРазмещения(T, j, step)
u = НоваяТочка(0, 0, +∞)

• Проверка на касание трех граней зоны размещения.

utest = НоваяТочка(0, 0, 0)
u = ПроверкаТочки(T, j, step, u, utest)

• Проверка на касание трех граней одного из уже упакованных многогранников.

ДЛЯ i ОТ 1 ДО step ДЕЛАТЬ
В процессе последовательного нахождения каждой точки utest вогнутости ГФПР GPP(T_i, T_j):
u = ПроверкаТочки(T, j, step, u, utest)

• Проверка на касание двух граней зоны размещения и одной грани уже упакованного многогранника.

В процессе последовательного нахождения каждой точки utest пересечения граней ГФПР GPP(T_i, T_j) и ребер GQP(T_j):
u = ПроверкаТочки(T, j, step, u, utest)

• Проверка на касание грани зоны размещения и двух граней уже упакованных многогранников.

ДЛЯ k ОТ (i + 1) ДО step ДЕЛАТЬ
E = (GPP(T_i, T_j) ∩ GPP(T_k, T_j)) – Массив отрезков пересечения.
В процессе последовательного нахождения каждой точки utest  пересечения граней ГФПР GQP(T_j) и отрезков E:
u = ПроверкаТочки(T, j, step, u, utest)

• Проверка на касание трех граней различных уже упакованных многогранников.

            ДЛЯ l ОТ (k + 1) ДО step ДЕЛАТЬ
В процессе последовательного нахождения каждой точки utest пересечения граней ГФПР GPP(T_l, T_j) и отрезков E:
u = ПроверкаТочки(T, j, step, u, utest)
КОНЕЦ ЦИКЛА
КОНЕЦ ЦИКЛА
КОНЕЦ ЦИКЛА
ВОЗВРАТ ucur
КОНЕЦ  РасчетПараметраРазмещения

u – лучший найденный параметр размещения;
utest – проверяемый параметр размещения.
НАЧАЛО ПроверкаТочки(T, j, step, u, utest)
ЕСЛИ utest ≥ u ТОВОЗВРАТ u КОНЕЦ ЕСЛИ
ДЛЯ i ОТ 0 ДО step ДЕЛАТЬ
ЕСЛИ ТочкаВнутриМногогранника(utest, GPP(T_i, T_j)) ТО
ВОЗВРАТ u
КОНЕЦ ЕСЛИ
КОНЕЦ ЦИКЛА
ЕСЛИ ТочкаВнутриМногогранника(utest, GPQ(T_j)) ТО
ВОЗВРАТ u
ИНАЧЕ
ВОЗВРАТ utest
КОНЕЦ ЕСЛИ
КОНЕЦ  ПроверкаТочки

• 2.Формирование и изменение последовательности упаковываемых объектов

Алгоритм ППсУ.
Входные данные:
 – многогранники.
L, W – длина и ширина основания зоны размещения.
l – количество запусков локального поиска.
Выходные данные:
 – параметры размещения многогранников.

НАЧАЛО
Найдем объемы  многогранников
Выполним сортировку массива T в порядке уменьшения объемов {Vi}

ДЛЯ i ОТ 1 ДО n ДЕЛАТЬ
ui = РасчетПараметраРазмещения(T, i, i – 1)

КОНЕЦ ЦИКЛА
U = ЛокальныйПоиск(T, U, l)
ВОЗВРАТ U
КОНЕЦ

Алгоритм GRASP.
Входные данные:
 – многогранники.
L, W – длина и ширина основания зоны размещения.
l – количество запусков локального поиска.
Δα – шаг изменения параметра случайности α.
Выходные данные:
 – параметры размещения многогранников.
НАЧАЛО

ДЛЯ α ОТ 0 ДО 1 С ШАГОМ Δα ДЕЛАТЬ
Uα = ГенерацияGRASP(T, α)
Uα = ЛокальныйПоиск(T, Uα, Δα*(l/2))
ЕСЛИ  ИЛИ un(z) > uαn(z) ТО
U = Uα
КОНЕЦ ЕСЛИ
КОНЕЦ ЦИКЛА
U = ЛокальныйПоиск(T, U, l/2)
ВОЗВРАТ U
КОНЕЦ

НАЧАЛО  ГенерацияGRASP(T, α)
ДЛЯ i ОТ 1 ДО n ДЕЛАТЬ
 – массив параметров размещения на i-том шаге
ДЛЯ j ОТ 1 ДО n ДЕЛАТЬ
u_ij = РасчетПараметраРазмещения(T, j, i – 1)

КОНЕЦ ЦИКЛА
Отсортируем точки массива U_i в порядке возрастания координаты (z).
U_i = U_i \ u_bad: u_bad(z) > ui1 + α(u_in – u_i1)
ПроизвольныйЭлементИз()
КОНЕЦ ЦИКЛА
ВОЗВРАТ U
КОНЕЦ  ГенерацияGRASP

НАЧАЛО ЛокальныйПоиск(T, U, l)
U_cur = U, T_cur = T
ДЛЯ i ОТ 1 ДО l ДЕЛАТЬ
Найти
Сгенерировать случайное число
Создать последовательность T_local, которая отличается от T_cur перестановкой элементов с номерами max и any
Если размещение в соответствии с порядком T_local было рассмотрено ранее, то повторим генерацию any, иначе продолжим
Разместим многогранники T_local в соответствии с найденным порядком
Если u_curn(z) < u_localn(z), то U_cur = U_local, T_cur = T_local
КОНЕЦ ЦИКЛА
ВОЗВРАТ U_cur
КОНЕЦ  ЛокальныйПоиск

Результаты вычислительного эксперимента

Для оценки эффективности алгоритмов были использованы тестовые данные из общедоступных источников [6].
В статье Ю.Г. Стояна [6] приведены 4 примера, составленные из невыпуклых многогранников 10-ти типов.
Пример №1. Задан набор из 20 многогранников, по 2 каждого типа. Основание зоны упаковки имеет ширину 30 и длину 35. Результат – Таблица №1.

Таблица №1 –  Сравнение эффективности алгоритмов для примера №1.

Лучшее решение для примера №1 найдено алгоритмом «GRASP с ЛП», предложенным в данной статье (Рис.5, а).
Пример №2. Задан набор из 30 многогранников, по 3 каждого типа. Основание зоны упаковки имеет ширину 30 и длину 35. Результат – Таблица №2.

Таблица №2 –  Сравнение эффективности алгоритмов для примера №2.

Лучшее решение для примера №2 найдено алгоритмом «GRASP с ЛП»,  предложенным в данной статье (Рис.5, б).
Пример №3. Задан набор из 40 многогранников, по 4 каждого типа. Основание зоны упаковки имеет ширину 30 и длину 35. Результат – Таблица №3.
Таблица №3 –  Сравнение эффективности алгоритмов для примера №3.

Лучшее решение для примера №3 найдено алгоритмом «Первый подходящий с упорядочиванием + ЛП», предложенным в данной статье (Рис.5, в).
Пример №4. Задан набор из 50 многогранников, по 5 каждого типа. Основание зоны упаковки имеет ширину 30 и длину 35. Результат – Таблица №4.

Таблица №4 –  Сравнение эффективности алгоритмов для примера №4.

Лучшее решение для примера №4 найдено алгоритмом «Первый подходящий с упорядочиванием + ЛП», предложенным в данной статье (Рис.5, г).
Результаты проведенных вычислительных экспериментов показали, что:

1. При реализации внутренней (геометрической) процедуры разработанный подход, основанный на анализе точек занесения, позволяет получать 3-D упаковки, превосходящие по своему качеству известные решения в среднем на 4%;
2. Время генерации размещения больше, т.к. в реализации Ю.Г. Стояна на вход алгоритма подаются невыпуклые многогранники, представленные в виде объединения выпуклых. Таким образом, быстрее решаются задачи: построения ГФПР, проверки принадлежности точки многограннику и поиска пересечения многогранников. Однако сама проблема разбиения невыпуклого многогранника на выпуклые в статье Ю.Г.Стояна не рассматривается.
3. При реализации внешней (оптимизационной) процедуры «GRASP с ЛП» работает лучше, чем «Первый подходящий с упорядочиванием + ЛП» при малых размерах задачи. Это можно объяснить тем, что начальные решения чаще попадают в окрестности локальных минимумов, позволяя более эффективно производить локальный поиск.

Рис.5. Лучшие варианты размещения многогранников по заданиям из [6].

Заключение

В работе приведен алгоритм решения NP-трудной задачи упаковки невыпуклых многогранников в прямоугольный параллелепипед минимальной высоты, позволяющий получать результаты, превосходящие известные методы решения этой проблемы, и базирующийся на построении годографа функции плотного размещения для моделирования условий взаимного непересечения многогранников. В дальнейшем предполагается проведение углубленного вычислительного эксперимента по исследованию эффективности  применения различных методов оптимизации при реализации внешней (оптимизационной) процедуры.

Список литературы

1. Верхотуров М.А. Задача нерегулярного размещения геометрических объектов: современное состояние методов решения // Ресурсосберегающие технологии.-С.Петербург: ЦНИИТС.-2001.-С.33-56.
2. Верхотуров М.А., Верхотурова Г.Н., Ягудин Р.Р. Об одном решении задачи плотной упаковки выпуклых многогранников на основе годографа функции плотного размещения // Информационные системы и технологии.-Орел.-2012.-№4.-С.31-39.
3. Верхотурова Г. Н., Ягудин Р. Р. Построение годографа функции плотного размещения двух многогранников // Принятие решений в условиях неопределенности.-Уфа: УГАТУ.-2010.-В7.-С.150-157.
4. Вилинов И.Е, Раздорский С.А., Смирнов Е.Б. Кабины кранов: экспериментальные исследования виброакустических характеристик // Инженерный вестник Дона, 2008. – №3. – http://www.ivdon.ru/ magazine/archive/ n3y2010/88/ (доступ свободный).
5. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования // Киев: Наук. Думка.-1986.-286С.
6. Stoyan Y., Gil N., Scheithauer G. Packing of convex polytopes into a parallelepiped // Preprint.-Dresden.- MATH-NM-06-2004.-2004.-32C.