冠军方案之 面料剪裁利用率优化

freeopen 2021-02-13 [机器学习] #top1

冠军：行星防御理事会 团队（乔德平等）

任务说明

面料切割利用率的提升是纺织行业长期追求的目标。如何提升面料切割利用率，既是企业生产精益化的难点，也是痛点。在切割之前，需要确定多个零件在面料上的位置和角度，再充分利用零件在形状上的互补特征，对零件排布的方式进行优化。面料切割问题的特性，是零件存在多种尺寸、形状，比如用作衬衫制作的袖子、后背等零件，用来切割的布匹本身存在多类瑕疵，如破洞、折皱、漏纱等，在排版中需要避开。此外，某些订单，对零件存在个性化排版需求，因此在下料环节中，需要依照订单要求进行排版下料。当前纺织行业布匹原材料的成本占到40%左右，价值较高。

本赛场聚焦面料剪裁利用率优化，要求选手研究开发高效可靠的算法，在较短时间范围内计算获得高质量可执行的排版结果，减少切割中形成的边角废料，提升面料切割利用率，减少计划时间、提高工作效率和避免人工计算的失误，提升价值降低成本。

在规则面料的情况下，满足零件旋转角度、零件最小间距、最小边距的约束，解决以下两类问题：

初赛赛题：基于所给零件，进行面料排版加工，耗料长度最短，面料利用率最高；

复赛赛题：在问题一的基础上，避开瑕疵区域面料加工，耗料长度最短，面料利用率最高。

零件数据

编号列名说明示例
1下料批次号Primary keyL0001
2零件号Primary keys000001
3数量1
4外轮廓[[1420.0, 5998.6], [1420.0, 6062.8], [2183.1, 6062.8],[2183.1, 5998.6], [1420.0, 5998.6]]
5允许旋转角度逆时针旋转角度0,90,180,270
6面料号M0001

注：外轮廓曲线数据均离散化为点坐标序列；所有尺寸的单位为毫米(mm).

面料数据说明

编号列名说明示例
1面料号Primary keyM0001
2面料规格规则（矩形）面料，长度x宽度（单位：mm）10000x100
3瑕疵区域瑕疵均为圆形区域，标注方式为圆形中心、圆形半径。比如[[2000,400],80]，即圆形中心坐标点为[2000,400]，半径为80。坐标系的原点为面料的左下角（参考“约束说明“第（7）条说明）[[[2000,400],80], [[1000,1200],50], ⋯]
4零件间最小间距5
5最小边距10

注：瑕疵区域均为圆形；所有尺寸的单位为毫米(mm)。

约束说明

排样规则

1）排版的零件不能超出面料的可行区域；

2）排版零件互不重叠；

3）零件按批次，在同一面料上排版；

4）面料可能存在多个长宽度规格，如宽度为900mm、1000mm等、长度为10000mm、12000mm等；

5）允许用户设置切边预留量，如面料四边各预留5mm（最小边距）；切割零件间预留量5mm（最小间距）；

6）某些零件存在旋转角度上的要求，比如零件纹理方向必须保持一致；旋转角度为0表示，零件不允许发生旋转，必须原样放在面料上，面料的放置方向为面料窄边（宽度）在垂直方向，面料宽边（长度）在水平方向；旋转角度为90表示允许零件逆时针旋转90度。

7）切割零件需要避开面料上的瑕疵，瑕疵均为圆形区域，标注方式为圆形中心、圆形半径，坐标系的原点为面料的左下角（参考“数据说明”第（2）条“面料数据说明”），面料的放置方向为面料窄边（宽度）在垂直方向，面料宽边（长度）在水平方向；瑕疵与零件间间距视同零件间间距，即，如果零件间间距（最小距离）为5mm，零件与瑕疵的间距（最小距离）也为5mm。

评估指标

决赛总分 = 0.3∗B榜成绩 + 0.4∗C榜成绩 + 0.3∗现场答辩

其中：

B榜成绩 =（0.5∗批次1面料利用率+0.5∗批次2面料利用率）∗100

C榜成绩 = 权重参数1∗面料利用率 − 权重参数2∗计算时间分值

面料利用率 = 一个批次包含的零件总面积/消耗的面料总面积

计算时间分值 = f(一个批次排版的平均计算时间)

权重参数1 = 100.0 权重系数2 = 1.0

方案思路

问题： 二维不规则多边形放置

最先考虑山寨开源的svgnest，发现初赛结束前可能搞不出来。

又考虑NFP，但计算太复杂，初赛结束前可能做不出来。

按像素暴力枚举实现左底法，原理和实现都很简单，但性能和内存可能惨不忍睹。

预期纯左底优化到1小时内出个解就行，后来优化到1秒内，就觉得贪心暴力枚举也可以试试了。

复赛开始前把暴力贪心实现了，然后主要精力花在像素法的性能提高上，这个地方足够快以后，后面的贪心算法就可以暴力按像素枚举最佳位置了。

贪心算法原理和实现都很简单，缺陷也很明显，很容易挂在小规模或者不太随机的数据集上，比赛期间也没解决这个问题，以后有时间慢慢优化。

算法中还包含了遗传算法调优的部分，这部分直接参考了svgnest，只有很小的调整，提升效果不大。

遗传调优这部分直接删掉也行，效果略微降一点，时间可以降到3分钟内，内存降到几十兆。

freeopen：冠军选手的思考轨迹，个人认为有很高学习价值，感谢冠军选手这么细致的分享。

算法设计

基于高精度像素法实现多边形相交检测

像素法的基本原理：将不规则多边形零件及面料像素化（初始化）；检测零件的像素与已放置的像素是否有重叠（相交检测）；将零件的像素放到面料对应的像素上（放置）。

左底法

对每个零件，从左下角像素开始，逐像素上移直到与已放置像素无重叠为止。如果失败，向右移动一个像素并重复该过程。

像素法的精度相关问题

像素法将浮点数转换成了整数，必然会有精度丢失。为了保证间距边距要求，在多边形扩张时通常要将像素向上取整，这就造成了一定的浪费，通常为0到1像素大小。通常精度越低，浪费越大。

无论多高的精度，即使到原子级，都是有误差的；

为了减小浪费，通常需要提高精度，高精度往往意味着低性能。

本文实现的像素精度为0.1mm，对于面料即16000*200000=32亿像素。如果采用位图，仅面料就需要32亿像素/8=4亿字节，约380M。如果全局搜索采用遗传算法之类的算法，内存消耗会再增加数十倍，性能也比较低。

基于扫描线的像素法

基于扫描线实现像素法，即将零件和面料横向和纵向的连续像素使用线段来表示。零件横向或纵向扫描线一般在1～2个线段，零件扫描线根数一般在几百到12000。

面料初始状态横向和纵向都是1个线段，在零件全部放置后，则纵向10个线段左右，最多20万根扫描线，一般内存消耗在20M左右；横向扫描线数量要高一些，但横向的扫描线只有16000根，内存消耗和纵向差不多。

纯左底法的内存消耗估计在20M左右，性能估计也会有数量级的提升。

扫描线相交检测的回溯问题

左底法扫描线的基础版本，是对于零件的每条扫描线可以直接上移若干像素保证该条扫描线可放置或者直接失败。该方案当下一条扫描线需要上移时，需要回过头来从零件的第一根扫描线重新检测是否相交，这样会有大量的回溯检测，性能较低。

改进方法一（记录最小移动距离）：

改进方法二（调整扫描顺序，尽早失败，提前回溯）：

基于扫描线的多边形边缘扩张

零件间距可以通过边缘扩张来处理，对于像素法的边缘扩张，对每个顶点画圆，将预先计算的扫描线叠加到多边形上；对每个线段向平移构成平行四边形，画该平行四边形，将扫描线叠加到多边形上。

像素法改进小结

贴合度+贪心算法

贪心算法的主要原理：每次放置都从所有零件中跳出最贴合的来放置。

但由于零件数量较大，每次都从所有零件中来选择的话，性能较低，所以我们每次只从其中一部分来选择最贴合的零件。

贪心算法整体步骤

基于扫描线贴合距离的贴合度公式

左底+遗传算法

使用遗传算法对左底的零件放置顺序进行调整。

方法效果
纯左底改为左底或左上+0.0%～0.2%
旋转的选择通过直接比较2x+y 取小的搜索空间大幅下降
允许零件向右滑动一小段距离提升0.x%
逐步放大参与优化的零件数略微提升

总结

像素法的优点

像素法的缺点

贪心算法的优缺点

遗传算法的优缺点

进一步的工作

像素法实现方面待改进的地方

针对不同规模不同形状分布的数据集更好的适应

Back to top