Найти

Результаты поиска

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

  В. В. Курейчик, А. Е. Глущенко

  2020-07-20

  Аннотация ▼

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

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

  В.И. Данильченко , В.В. Бова , М. М. Семенова , С.В. Игнатьева , М. Б. Шайлиев

  2026-02-27

  Аннотация ▼

  Рассматривается одна из важных комбинаторных задач оптимизации – задача трехмерной упаковки. Оптимизация трехмерной упаковки снижает затраты и повышает эффективность логистики, что делает ее актуальной для промышленности. В работе проанализированы классические подходы, такие как жадные алгоритмы и динамическое программирование, а также широко применяемые методы, включая эволюционные алгоритмы и локальный поиск. Анализ существующих методов, включая жадный поиск, динамическое программирование, эволюционные алгоритмы и локальный поиск, позволил выявить их ключевые характеристики и определить подходящие области применения. В контексте данного анализа представлен обзор ключевых методов, доминировавших в определенные исторические периоды. Анализ включает рассмотрение условий применения различных методов, их эффективности для определенных типов задач, а также их преимуществ и ограничений. Представлен многоуровневый алгоритм поиска, который объединяет преимущества традиционных и современных методов оптимизации. Многоуровневый алгоритм позволяет улучшить точность решения задачи упаковки за счет динамической настройки параметров. Разработан программный комплекс для решения задачи оптимизации трехмерной упаковки с использованием биоинспирированных алгоритмов. Проведен вычислительный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, полученное, на основе разработанного комбинированного биоинспирированного алгоритма, в среднем на 7 % превосходит результаты упаковки, полученные с использованием известных алгоритмов, а время решения меньше от 7% до 25%, что говорит об эффективности предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае временная сложность алгоритмов O(n²), в худшем случае – O(n³).