МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРЕХМЕРНОЙ УПАКОВКИ БОЛЬШОЙ РАЗМЕРНОСТИ
Ключевые слова:
Трехмерная упаковка, упаковка в контейнеры, многоуровневый подход, комбинированный биоинспирированный алгоритм, генетический алгоритм, эволюционный алгоритмАннотация
Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер-
ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных
и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех-
мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра-
ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю-
чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под-
задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор
объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под-
хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на
эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время
получения результата, частично решить проблему предварительной сходимости алгоритмов
и получить наборы квазиотимальных решений за полиномиальное время. Разработан про-
граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной
упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли-
тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен-
ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред-
нем на 5 % превосходит результаты упаковки, полученные с использованием известных
алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности
предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить
теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре-
менная сложность алгоритмов O(n2), в худшем случае – O(n3).
