An efficient deterministic heuristic for two-dimensional rectangular packing
An efficient deterministic heuristic for two-dimensional rectangular packing
复制标题
DOI：
10.1016/j.cor.2011.08.005
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
Kun He;Wenqi Huang;Yanqi Jin
中科院分区：
文献类型：
--
作者：
Kun He;Wenqi Huang;Yanqi Jin
本文提出了一种求解NP-hard二维矩形填充问题的确定性启发式最佳拟合算法（BFA），以最大化矩形板材的填充率。这种新方法有两个阶段：构造阶段和树搜索阶段。前者旨在利用动作空间和拟合度的概念来评估不同的放置位置，从而快速生成初始解。后者寻求进一步改进解决方案，并通过部分树搜索过程搜索有希望的位置。然后，我们将BFA与其他方法在解决方案质量和计算时间方面进行比较。我们在Hopper和Turton提出的C21和Burke等人提出的N13两组众所周知的基准实例上进行了计算实验。BFA在短时间内获得了C21实例的平均填充率为100%，表明获得的所有布局都是最优的。据我们所知，这是第一次通过确定性算法获得所有21个实例的最优布局。对于N13问题，迄今为止，研究人员已经找到了前三个问题的最优解，而BFA在合理的时间内解决了包括前三个在内的七个问题。另一项工作是利用BFA来解决一个相关问题，即受限二维切割（或包装）问题（CTDC）。虽然BFA在原始设计中不是针对CTDC的，因此没有考虑CTDC的一些特定特征，但改编后的算法在21个公共CTDC实例上仍然表现良好。
This paper proposes a deterministic heuristic, a best fit algorithm (BFA), for solving the NP-hard two-dimensional rectangular packing problem to maximize the filling rate of a rectangular sheet. There are two stages in this new approach: the constructive stage and the tree search stage. The former aims to rapidly generate an initial solution by employing the concepts of action space and fit degree in evaluating different placements. The latter seeks to further improve the solution and searches for promising placements by a partial tree search procedure. We then compare BFA with other approaches in terms of solution quality and computing time. We carry out computational experiments on two sets of well-known benchmark instances, C21 proposed by Hopper and Turton, and N13 proposed by Burke et al. BFA gained an average filling rate of 100% for the C21 instances within short times, indicating that all the layouts obtained are optimal. To the best of our knowledge, this is the first time that optimal layouts on all the 21 instances were obtained by a deterministic algorithm. As for the N13 instances, to date, researchers have found optimal solutions to the first three instances, whereas BFA solved seven, including the first three, within a reasonable period. An additional work is to adapt BFA to solve a relevant problem, the constrained two-dimensional cutting (or packing) problem (CTDC). Though BFA is not for the CTDC in the original design such that some specific characteristics of CTDC are not considered, the adapted algorithm still performed well on 21 public CTDC instances.