Найти

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

• СОВРЕМЕННЫЕ ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ 3D УПАКОВКИ

  М.М. Сорокин , Л. А. Гладков , Н. В. Гладкова

  131-150

  2026-09-10

  Аннотация ▼

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

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

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

  2026-02-27

  Аннотация ▼

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

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

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

  2020-07-20

  Аннотация ▼

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