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

我不是女神ヾ 2023-01-14 11:54 89阅读 0赞

转自： [https://bbs.huaweicloud.com/blogs/196289][https_bbs.huaweicloud.com_blogs_196289]

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

## 1       二维异形件排样算法 ##

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

## 2       二维异形件排样策略 ##

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

### 2.1   基于可行解策略 ###

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

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

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

![图2-1.png][2-1.png]

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

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

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

![表2-1.png][2-1.png 1]

![图2-2.png][2-2.png]

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

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

![图2-3.png][2-3.png]

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

![图2-4.png][2-4.png]

图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.

登录后可下载附件，请[登录][Link 1]或者[注册][Link 2]

[https_bbs.huaweicloud.com_blogs_196289]: https://bbs.huaweicloud.com/blogs/196289
[https_bbs.huaweicloud.com_blogs_175385]: https://bbs.huaweicloud.com/blogs/175385
[2-1.png]: /images/20221022/74017fa151a247f3aae2faa01390f7ac.png
[2-1.png 1]: /images/20221022/1f1af14770f34448870232f1bce862c6.png
[2-2.png]: /images/20221022/e3c5d9e97bba40c983e53cdd62ab928a.png
[2-3.png]: /images/20221022/3a4a5849569b4047aabb707c601e8540.png
[2-4.png]: /images/20221022/5908228e0e924f03a92ccec682b055ac.png
[Link 1]: https://auth.huaweicloud.com/authui/login?service=https://bbs.huaweicloud.com/blogs/196289#attachment&locale=zh-cn
[Link 2]: https://reg.huaweicloud.com/registerui/public/custom/register.html?locale=zh-cn&service=https://bbs.huaweicloud.com#/register
[huaweicloud.bbs_huawei.com]: mailto:huaweicloud.bbs@huawei.com