Двумерная задача упаковки в контейнеры

Этот калькулятор ищет решение двумерной задачи упаковки в контейнеры. Для поиска решения используется эвристический алгоритм максимальных прямоугольников (Maximal Rectangles). Найденное решение выводится в графическом и табличном виде.

Эта страница существует благодаря следующим персонам

Timur

Timur

Создан: 2022-05-30 11:13:42, Последнее изменение: 2022-05-30 11:13:42

Ниже необходимо ввести размеры контейнера в формате Ширина х Высота, затем размеры прямоугольных элементов, которые нужно упаковать и их количество в формате Ширина х Высота х Количество, по одному типу прямоугольников в строке.

Калькулятор попробует упаковать указанные прямоугольники в прямоугольники большего размера как можно более экономичным способом. Основная цель такой упаковки - сэкономить материал, "выкроив" все нужные детали (представленные как прямоугольники) из как можно меньшего числа прямоугольных заготовок большего размера. Так как используется эвристический алгоритм, оптимальный результат не гарантируется, но калькулятор по умолчанию использует несколько эвристических подходов и выбирает наилучший полученный результат. О деталях алгоритма можно почитать более подробно под калькулятором.

PLANETCALC, Двумерная задача упаковки в контейнеры

Двумерная задача упаковки в контейнеры

Размеры контейнера

Прямоугольники, которые требуется упаковать

Требуемое число контейнеров
 
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Двумерная задача упаковки в контейнеры

Двумерная задача упаковки, как ясно из названия, является разновидностью задачи об упаковке в контейнеры, где как контейнеры, так и объекты для упаковки представлены в виде двумерных прямоугольных областей. Обычно цель состоит в том, чтобы упаковать все объекты, используя как можно меньше контейнеров.

Если заранее известен набор объектов, которые необходимо упаковать, задача называется «оффлайновой» (либо же это никак не обозначается), в отличие от «онлайновой» задачи, где объекты появляются один за другим. Данный калькулятор решает двумерную задачу упаковки, когда все объекты для упаковки известны заранее - оффлайновую задачу.

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

Эта конкретная реализация поиска решения задачи упаковки в 2D контейнеры основана на алгоритме максимальных прямоугольников (Maximal Rectangles Algorithm). Эта эвристика является расширением эвристики гильотинного разделения и показывает отличные результаты для упаковки в оффлайновом режиме1.

Идея эвристического алгоритма максимальных прямоугольников состоит в отслеживании всех прямоугольных областей максимально возможного размера, которые остаются доступны для упаковки после упаковки текущего объекта в контейнер (см. рисунок).

Доступные прямоугольники максимального размера
Доступные прямоугольники максимального размера

Существуют также разные правила выбора того, в какой из свободных прямоугольников какой объект нужно поместить. Данный калькулятор использует "глобальный" подход, который подразумевает на каждом шаге упаковки вычисление некоторых "очков" (score) для каждого оставшегося прямоугольника и каждого оставшегося свободного места, и выбор комбинации, которая дает нам лучший результат. Очки зависят от того, насколько хорошо объект для упаковки "садится" в свободный прямоугольник, с точки зрения правила размещения внутри свободного прямоугольника. Что касается правил размещения - их также существует несколько (см. ниже), калькулятор получает результат упаковки с каждым из них, а затем выбирает наилучший результат, то есть тот, который в итоге дает минимальное число контейнеров.

Правила размещения таковы:

  1. Нижний левый (Bottom Left) — координата y верхней стороны прямоугольника должна быть наименьшей. В случае ничьей используется тот, у которого наименьшее значение координаты x.
  2. Наилучшая посадка по короткой стороне (Best Short Side Fit) — после размещения объекта свободное пространство должно иметь минимальную длину более короткой оставшейся стороны.
  3. Наилучшая посадка по длинной стороне (Best Long Side Fit) — после размещения объекта свободное пространство должно иметь минимальную длину более длинной оставшейся стороны.
  4. Наилучшее соответствие площади (Best Area Fit) — после размещения объекта площадь свободного пространства должна быть наименьшей. В случае ничьей используется правило наилучшей посадки по короткой стороне (Best Short Side Fit).

  1. A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing by Jukka Jylänki 

Ссылка скопирована в буфер обмена
PLANETCALC, Двумерная задача упаковки в контейнеры

Комментарии