Авторы

Оптимизация решения задачи ортогональной упаковки объектов

Эффективная модель управления объектами в задачах ортогональной упаковки и прямоугольного раскроя

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

Разработка алгоритма уплотнения упаковки для повышения эффективности прямоугольного раскроя

Алгоритмы корректной визуализации двухмерных и трехмерных ортогональных многогранников

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

В статье рассматривается задача упаковки объектов произвольной геометрии. Современные методы конструирования нерегулярной упаковки используют математическую модель размещения объектов на базе phi-функций и годографа вектор- функции плотного размещения. Эти методы позволяют получать точные решения, однако в то же время являются трудоемкими и очень чувствительными к размерности решаемой задачи и степени детализации геометрии векторных объектов. Использование дискретного представления размещаемых объектов в виде ортогональных многогранников позволяет существенно повысить скорость построения упаковки, что делает актуальной задачу адекватного преобразования формы размещаемых объектов (векторных моделей в двумерном случае и полигональных моделей в трехмерном случае). Целью исследования является систематизация методов, обеспечивающих формирование ортогональных многогранников различной размерности для описания объектов и контейнеров произвольной геометрии. Рассмотрены методы создания ортогональных многогранников на основе теоретико-множественных операций, аналитического моделирования и вокселизации. Применение теоретико-множественных операций наилучшим образом подходит для ручного создания ортогональных многогранников, характеризующихся относительно несложной геометрией. Метод аналитического моделирования предназначен для формирования вокселизированных объектов набором аналитически заданных функций. Показано применение различных операций отношения для получения ортогональных многогранников, описывающих контур, внутреннюю и внешнюю области аналитических заданных объектов. Предложен алгоритм создания контейнера в виде ортогонального многогранника на основе заданной векторной модели. Все представленные методы программно реализованы с обобщением по размерности и применимы для решения любых типов задач раскроя и упаковки. Читать дальше...

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

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