A reduction approach for solving the rectangle packing area minimization problem
A reduction approach for solving the rectangle packing area minimization problem
复制标题
DOI：
10.1016/j.ejor.2012.08.006
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
Andreas Bortfeldt
中科院分区：
文献类型：
--
作者：
Andreas Bortfeldt
在矩形布局面积最小化问题(RPAMP)中，给出了一组尺寸已知的矩形。我们必须确定在一个面积最小的包络矩形内所有矩形的排列，而不是重叠。本文提出了一种求解RPAMP问题的通用方法，该方法基于两种算法，一种是求解2D背包问题(KP)，另一种是求解2D排样问题(SPP)。这样，求解RPAMP的一个实例就简化为求解多个SPP和KP实例。SPP算法采用快速构造性启发式算法，而KP算法采用树搜索和遗传算法交替实例化。所有这些SPP和KP方法都已发表过。最后，最终得到的RPAMP启发式算法的最佳变体被组合在一个过程中。断头台切割条件总是作为一个附加约束来观察。该方法在15个知名的RPAMP实例(尤其是MCNC和GSRC实例)上进行了测试，并针对10个实例获得了新的最佳解决方案。计算方面的努力仍然可以接受。此外，还介绍了24个新的基准实例，并报告了令人振奋的结果。
In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.