9435

11

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

431 наименования. Приложения выполнены на 60 страницах.

Личный вклад автора. Все теоретические и практические результаты работы, изложенные в диссертации, получены лично автором. Конфликт интересов со всеми соавторами научных работ отсутствует.

Основное содержание работы

Во введении обосновывается актуальность темы диссертационной работы; формулируются цель и задачи исследований; представляются основные положения работы, выносимые на защиту; определяются научная новизна, теоретическая и практическая значимость полученных результатов; приводится краткая характеристика основных разделов диссертации.

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

Среди основных методов, применяемых для решения задач раскроя и упаковки можно выделить методы математического программирования, комбинаторной оптимизации, эвристические и метаэвристические методы. Методы математического программирования обеспечивают возможность получения решения задачи с заданной точностью, однако их применение ограничено лишь небольшими размерами задачи (как правило, до 20 объектов) ввиду их высокой вычислительной сложности. Методы комбинаторной оптимизации, основанные на выполнении частичного перебора различных вариантов решения задачи, также являются очень чувствительными к размерности задачи. Наилучший компромисс между скоростью решения и качеством решения в условиях единичного и мелкосерийного производства достигается при использовании эвристических и метаэвристических методов оптимизации. Для задач раскроя и упаковки наивысшую эффективность демонстрируют метаэвристические методы, основанные на эволюционных моделях оптимизации. Эвристические методы могут быть использованы как для выполнения однопроходной оценки возможности размещения объектов, так

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

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

12

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

Ниже приведена общая постановка задачи плотной упаковки

системе координат, связанной с этим ортогональным многогранником. Положение объекта в D -мерном контейнере j определяется точкой D -мерного параллелепипеда, описанного вокруг этого объекта, которая расположена на минимальном расстоянии от начала координат контейнера

контейнера в нижнем индексе указывается только номер объекта). Число размещаемых объектов обозначается через n , число контейнеров – через N .

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

Для обеспечения размещения объектов в требуемом направлении

определяет порядок выбора координатных осей контейнера в процессе геометрического конструирования упаковки.

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

13

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

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

1.Рёбра всех размещённых в контейнере объектов должны давать ненулевую проекцию только на одну координатную ось контейнера.

2.Размещённые объекты не должны перекрывать друг друга, т.е. для

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

упаковки для каждого ортогонального объекта i {1,K, n}, размещённого в контейнере j , должны выполняться условия:

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

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

15

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

Рисунок 2. Блок-схема алгоритма размещения объектов

16

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

различных уровнях линейных связных списков, содержащих элементы, упорядоченные по возрастанию уникальных значений (рисунок 3). Каждый

элемент j списка i на уровне вложенности Ld содержит координату siL, dj = xkLd

такого потенциального контейнера k , что внутри каждого связного списка

Исследование многоуровневой связной структуры данных проводилось на примере сравнения с упорядоченным одномерным линейным связным списком. Относительная временная эффективность многоуровневой связной структуры данных определялась как отношение времени размещения объектов при использовании линейного списка ко времени, затрачиваемого при использовании многоуровневого связного списка. Для всех тестовых задач двухмерной (S.P. Fekete, J. Schepers1) и трёхмерной (S. Martello, D. Pisinger, D. Vigo2) ортогональной упаковки предложенная структура данных обеспечивает более быстрое формирование упаковки по сравнению с одномерным линейным связным списком (рисунок 5).

1 http://people.brunel.ac.uk/~mastjjb/jeb/info.html

2 Martello, S. The three-dimensional bin packing problem / S. Martello, D. Pisinger, D. Vigo // Operations Research. – 2000. – Vol. 48, № 2. – P. 256–267.

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

Анализ эффективности модели потенциальных контейнеров проводился при решении тестовых задач двухмерной прямоугольной упаковки (S.P. Fekete, J. Schepers) и трёхмерной ортогональной упаковки (S. Martello, D. Pisinger, D. Vigo). В качестве показателя качества размещения служит относительное отклонение μ от нижней границы решения, которое рассчитывается по

формуле μ(%)= (N * − Λ)n ×100% , где N * – число заполненных объектами контейнеров; Λ – точная нижняя граница задачи. Проведённые вычислительные эксперименты показали, что модель потенциальных контейнеров обеспечивает получение наилучших показателей размещения (как по плотности упаковки, так и по скорости её конструирования) в сравнении со всеми рассмотренными моделями геометрического описания упаковки на всех наборах тестовых задач различной размерности (рисунок 6).

Вычислительные эксперименты на тестовых задачах упаковки на полубесконечную полосу (E. Hopper, B.C.H. Turton3) показали, что оптимальные решения для всех тестовых задач достигаются только при использовании модели потенциальных контейнеров.

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

3 https://github.com/Oscar-Oliveira/OR-Datasets/tree/master/Cutting-and-Packing/2D/Datasets/HT2001a

19

3. Эвристика FWF («First Width Fit» – «первый подходящий по ширине»):

Мультиметодный генетический алгоритм, использующий разработанные эвристики, превосходит по качеству размещения объектов классический генетический алгоритм, а также другие варианты реализации генетического алгоритма на всех классах тестовых задач S.P. Fekete, J. Schepers.

Для задач трёхмерной упаковки разработаны эвристики размещения (таблица 2), основанные на использовании пар правил выбора неразмещённых

20

Проведённые вычислительные эксперименты на тестовых задачах трёхмерной ортогональной упаковки (S. Martello, D. Pisinger, D. Vigo) показали, что правила O1 , O3 и O4 обеспечивают примерно одинаковое качество размещения. Наибольшую эффективность обеспечивает правило O1 , в то время, как правила O2 и O5 обеспечивают наихудшее размещение объектов на всех классах тестовых задач. При использовании правил O2 и O5 затрачивается время, на порядок большее по сравнению с остальными правилами выбора объектов. Все правила выбора потенциальных контейнеров обеспечивают в среднем одинаковое качество размещения, однако правила P6 и P7 затрачивают время, большее (в среднем) в 2–3 раза в сравнении со всеми остальными правилами. На основе полученных результатов тестирования были определены вероятности включения различных правил в эвристики для мультиметодного генетического алгоритма (таблица 3), который использует хромосомы, представленные последовательностями применяемых эвристик.

Таблица 3

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

В таблице 4 приведены тестирования мультиметодного генетического алгоритма с разработанными эвристиками (МГА) на тестовых задачах трёхмерной ортогональной упаковки 3DBPP (S. Martello, D. Pisinger, D. Vigo), а

также результаты решения этих задач следующими алгоритмами (наилучшие решения в таблице выделены полужирным шрифтом и курсивом):

−O1 P3 – эвристика, использующая правила O1 и P3 ;

−C-EPBFD – эвристический алгоритм размещения по экстремальным

точкам (T.G. Crainic, G. Perboli, R. Tadei);

−MPV-BS – метод ветвей и границ (S. Martello, D. Pisinger, D. Vigo);

−HA – эвристика Height first – Area second (A. Lodi, S. Martello, D. Vigo);

−LB – нижняя граница, вероятностно рассчитанная M.A. Boschetti.

Таблица 4

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