二维异形件排版算法介绍（二）

1       二维异形件排样算法

上一篇博客提到二维异形件排样算法涉及到高速几何算法、排样策略和优化算法，并且系统综述了临界多边形（NFP）的求解算法，感兴趣的童鞋可以查看博文：https://bbs.huaweicloud.com/blogs/175385

2       二维异形件排样策略

二维不规则异形件主要有两种策略：分别是基于可行解的排样策略和基于重叠移除的排样策略。所谓基于可行解的排样策略，是指在排样过程中零件之间始终是不重叠的，而基于重叠移除的排样策略，是指在排样过程中允许零件之间发生重叠，在搜索过程中采用一定策略减少零件重叠的程度，直至最终得到可行解为止。下面分别详细介绍。

2.1   基于可行解策略

基于可行解的排样策略的好处是排样方案总是可行的。设计该类算法需要考虑两个主要因素：零件的可行放置位置和零件摆放的评估方法。最经典的策略是“左底法”，即将零件摆放在所有可行点中最靠左的位置，若出现多个最左点，则选择最底下的位置。

如何确定零件的可行放置位置呢？上文我们知道，NFP可以表征两个简单多边形“相切”的情况，因此，当固定一个简单多边形时，第二个简单多边形可以选择其相对第一个简单多边形的NFP上的点作为可行放置点。当然，这样的点有无穷多个，因此，一般只选择NFP的顶点（也可能再加上线段中点）作为可行放置点。

你可能会有这样的疑问，当只有两个简单多边形时当然可以这样摆放，但是如果已经摆放了若干个简单多边形，再摆放下一个简单多边形时，该如何保证其不与所有的多边形都不重叠呢？这的确是一个非常好的问题，也正是开发异形件切割排版算法遇到的第一个难题。解决方案主要有两个，一是将已经排版的简单多边形合并成一个大多边形，然后再进行排版，如图1所示，二是考虑所有NFP的顶点以及NFP每条线段的交点，然后再判断这些点是否在某个NFP的内部，如果该点不在任何一个NFP内部，则该点为可行点，否则不是可行点。第一个方案的问题是，零件之间的空隙将无法再放其他的简单多边形，造成原料浪费，第二个方案的问题计算成本大。

图1. 基于可行解的排样选点策略（图片来源：参考文献[1]）

零件排放位置该如何评估呢？常见的方法如表1和图2所示：

表1. 异形零件摆放位置评估方法

图2. 零件摆放位置评估常见方法（图片来源：参考文献[2]）

上述基于可行解策略得到的排样方案效果一般不会太好，还需要智能优化算法改善结果。常见的智能优化算法有遗传算法、模拟退火算法、价值修正、束搜索等方法，下面详细介绍一下束搜索方法。

图3. 束搜索方法示意图（图片来源：参考文献[3）

束搜索（Beam Search）是一种启发式图搜索方法，在每一步深度扩展的时候，剪掉一些质量比较差的节点，留下一些质量较高的节点。这样就减少了空间消耗，并提升了时间效率。具体而言，如图3（a）所示，束搜索使用广度优先策略创建搜索树，在树的每一层，按照局部启发式评价方法对节点进行排序，留下预先指定个数（filter width）的节点，而后再对这些节点进行全局启发式评价，再次留下预先指定个数（beam width）节点。仅这些节点在下一层次继续扩展，其余节点就被剪掉了。图3（b）展示了filter width=3，beam width=2时的搜索过程。束搜索评价函数采用顺序搜索评价函数加和模式，选择表1中Incentive列中的L1和R1，Balanced列中的O2，令评价函数等于L1+R1-O2。

束搜索还需要考虑零件的排序，常见的零件排序方法有如下几种：（1）面积；（2）长度；（3）宽度；（4）周长；（5）凸包面积；（6）包络矩形面积等等。一般采用零件面积进行排序。

2.2   基于重叠移除的排样策略

所谓重叠移除算法，如图4示，是指在初始可行解的基础上，减少原料长度，并通过交换、平移等邻域搜索技术改变当前的排版方案，在改变时允许裁片之间发生重叠，然后采用分离技术消除重叠，得到改进可行解。上述过程不断交替进行，直到达到算法终止条件为止。

图4. 重叠移除方法示意图（图片来源：参考文献[4]）

首先，使用启发式方法得到一个可行解，假设原料长度为L。若得到了可行解，则缩小原料长度，若没有得到可行解，则适当增加原料长度。之后，扰动当前解，实施上述优化程序。该过程迭代进行，直到达到算法终止条件。最终选择原料长度最小的可行解作为算法的输出。

重叠移除排版算法的详细介绍将在后续博客中更新，欢迎大家关注。

参考文献

[1] Oliveira J F, Gomes A M, Ferreira J S. TOPOS–A new constructive algorithm for nesting problems[J]. OR-Spektrum, 2000, 22(2): 263-284.

[2] Bennell J A, Song X. A beam search implementation for the irregular shape packing problem[J]. Journal of Heuristics, 2010, 16(2): 167-188.

[3] Bennell J A, Song X. A beam search implementation for the irregular shape packing problem[J]. Journal of Heuristics, 2010, 16(2): 167-188.

[4] Elkeran A. A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering[J]. European Journal of Operational Research, 2013, 231(3): 757-769.