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

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

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

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

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

Ширина x высота

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

4x72x1 4x30x1 26x60x2 36x58x1

Ширина x высота x количество

Правила размещенияПроверить все, использовать лучший результат Наилучшая посадка по короткой стороне Наилучшая посадка по длинной стороне Наилучшее соответствие площади Нижний левый Жадная наилучшая посадка по длинной стороне

Рассчитать

Требуемое число контейнеров

 

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

Загрузить 

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

Загрузить 

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

Загрузить 

 Ссылка  Сохранить  Виджет

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

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

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

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

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

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

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

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

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