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

Аннотация

Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер- ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех- мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра- ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю- чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под- задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под- хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время получения результата, частично решить проблему предварительной сходимости алгоритмов и получить наборы квазиотимальных решений за полиномиальное время. Разработан про- граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли- тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен- ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред- нем на 5 % превосходит результаты упаковки, полученные с использованием известных алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре- менная сложность алгоритмов O(n2), в худшем случае – O(n3).