Исходные данные

Ширина кузова:
см
Длина кузова:
см
 
Коробки  
 ШиринаДлинаКол-во
1 см см шт
 
Длинномерные - в начало
 

Укладка коробок в кузов, на поддон или паллет

Укладка коробок

У этой задачи комбинаторной оптимизации есть несколько названий: задача о рюкзаке (ранце), задача о загрузке, оптимальное размещение маленьких коробок в большой, размещение заготовок для раскроя и т.п. Суть их сводится к тому, что нужно максимально компактно разместить имеющийся набор предметов в заданном объеме (площади). Критерии оптимизации могут быть разные: количество резов, количество отходов, занимаемая площадь. В данном случае оптимизация производится по площади. Значение площади, которое выдает программа — ширина кузова, умноженная на длину укладки.

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

В принципе, можно решить задачу прямым перебором. В этом случае количество вариантов растет в геометрической прогрессии, и например, для 2D-задачи по размещению 4 коробок, количество вариантов будет составлять порядка 4000. На современном компьютере на расчет размещения 50 коробок уйдет более суток. Да, можно получить оптимальное (или одно из оптимальных) решение.

При создании данной прграммы мы написали алгоритм с элементами эвристики. В некоторых случаях решение является оптимальным, в большинстве случаев оно близко к оптимальному и отличается от него (по площади) не более, чем на 10%. Зато на расчеты уходит всего 5-20 секунд.

В форме ввода исходных данных есть чекбокс: "Длинномерные — в начало". Длинномерными считаются коробки, наибольший размер которых превышает ширину кузова. Если эта опция выключена, программа попробует найти коробки, один из размеров которых близок к ширине кузова, и поставит их в начало. Затем — все остальные. На размещение "маленьких" коробок этот переключатель не влияет.

Ваш вопрос, комментарий

Калькуляторы   1999-2024 © Advanced Research