面向智能制造的不规则零件排样优化算法

高 勃，张红艳，朱明皓

(1.北京交通大学 计算机与信息技术学院，北京 100044;2.北京交通大学 经济管理学院，北京 100044)

0 引言

二维零件排样是实际应用中最常见的排样问题，广泛应用在机械制造、轻工、服装和印刷业等行业中。排样就是在给定原材料区域内将多个零件按照一定的工艺需求以恰当的方式进行排列，最终使得原材料获得较高的利用率，并且要求排样零件之间不能交叉或重叠。排样问题主要分为规则件排样和不规则零件排样两类。在规则件排样中，矩形件排样是排样问题的基础，研究最为广泛，由于矩形件形状简单，可以较快地进行碰撞检测，并且排样方式只有横排或竖排两种，规则零件排样计算复杂度较低，实现起来相对容易。而不规则零件边数为多边形，零件凹凸性不定且形状复杂，并且可以任意角度旋转，因此，在零件定位以及零件之间碰撞检测判断方面时间复杂度较高。随着工业生产规模的不断扩大，针对不规则零件排样问题，综合考虑板材利用率以及耗时情况找到有效的解决方法，对企业尤为重要。另一方面，由于排样问题属于典型的NP完全问题，不规则零件排样问题求解的重点和难点在于如何在尽量短的时间内找到使得原材料利用率尽可能高的排样结果，设计和研究更加高效的不规则零件排样算法具有非常重要的理论研究意义和实际应用价值。

在研究初期，由于不规则件的复杂性，为了化简问题的复杂度，一部分学者针对零件形状进行优化处理，根据自身的几何特点对其进行包络矩形，三角形，以及梯形等预处理，将不规则多边形首先转换成包络矩形[1]，然后进行组合[2]排样，虽然这种转变大大降低了问题的复杂度，但造成了空间的严重浪费，不符合实际生产需求。之后，在包络矩形的方法上加以改进，研究者提出利用临界多边形的方法进行求解[3-4]。临界多边形可以较好地保留不规则零件的形状信息，不需要将零件进行规则化拟合和离散化，但随着不规则件数量的增加，会大大增加耗时，严重影响排样效率。而后，随着计算机的发展，智能优化算法在排样问题中得到了广泛应用。梁利东等[5-6]利用混合智能排样优化算法以及粒子群算法进行排样；韩伟等[7]提出基于模拟退火的贯通约束方法进行排样；史俊友等[8]利用神经网络混合优化算法优化排样；梁利东等[9]基于遗传算法的不规则件优化排样研究；王静静等[10-11]改进遗传算法针对不规则图形排样，李敬花等[12]结合遗传和模拟退火两种智能算法来求解不规则件排样问题，杨卫波等[13]基于实数编码量子方法解决不规则排样问题。虽然智能算法的应用使得板材利用率有所提高，但算法计算开销较大，计算过程较复杂。

本文针对待排件的几何特征信息，提出将不规则件进行对排或双排处理，使其尽可能地组合成矩形或近似矩形，然后对其包络矩形进行处理，这样在化简问题复杂度的同时又降低了板材浪费。另一方面，蚁群算法不容易陷入局部最优解，能够对解较好地进行全局搜索，对排样结果进行进一步的优化。基于此，本文利用启发式和蚁群学习混合算法来进行不规则多边形零件排样，而算法之间的结合可以在不规则排样的解空间内将最优的求解方案搜索出来，综合考虑板材利用率和算法的耗时情况，并通过仿真实验结果表明，该算法取得了较好的结果。同时，基于最大板材利用率，本文算法还给出了最少需要的板材数量，以给出企业合理订购原材料的方案，减少原材料的积压，提高企业的经济效益。

1 不规则件排样问题

1.1 问题描述

二维板材下不规则件排样指将若干规格不一的不规则零件排列在矩形板材上，并最终使得原材料获得较高的利用率。排样过程如图1所示，不规则排样比规则件排样要复杂得多，一方面，由于边界轮廓的复杂性，不规则多边形的靠接计算需要大量的计算时间；另一方面，不规则件轮廓具有多样性，因此不同的放置角度会产生不同的排样方案，若零件可在全角度范围内旋转，则急剧增加了排样动作的选择，大大增加了问题的复杂度。

在不规则零件排样过程中，需要满足以下约束条件：

(1)不规则零件ri排列在板材内部，不能超过边界；

(2)不同的零件ri和rj(i≠j)排列不能重叠；

(3)不规则零件rj可进行旋转、翻转等操作。

因此，对于N个零件参与的排样问题，排样方案种类可以计算为：

T(N)=N!×(360/θ)N。

(1)

可以看出，当零件数量N增大时，排样方案种类数量将呈阶乘级数量增长；另外，θ表示不规则零件每次旋转的角度变化，θ越小，则零件的选择动作就越多，排样方案相应地也会增加。

1.2 数学模型

在不规则零件排样问题的数学建模过程中所使用到的变量定义如表1所示。

表1 变量定义表

续表1

多个不规则零件排样，通过定位及定序规则确定零件的排样方案，并以最大化板材利用率为目标，则不规则零件排样问题的数学模型定义如下：

(2)

(3)

ri∈A,i=1,2,…,R;

(4)

ri∩rj=∅,i,j=1,2,…,R;

(5)

(6)

上述数学模型中目标函数式(2)表示以最大化每张板材利用率为目标，得到最优排样方案；约束式(3)表示第i张板材上排列零件的总面积；约束式(4)表示不规则件需要排列在板材区域内部，不能超过边界；约束式(5)表示零件之间的位置关系，不能交叉或重叠；约束式(6)表示n个板材裁剪的rj型号的零件总数为Mrj。

1.3 相关定义

1.3.1 不规则多边形面积

在排料之前，一般需要对多边形零件面积进行比较，并在计算板材的利用率时，需要求所有布局在板材上的零件的面积总和。由于不规则多边形的面积不易求解，将不规则多边形切割成多个三角形进行求解。

如图2所示的三角形的面积求解公式为：

(7)

将不规则多边形切割成若干个三角形，如图3所示。

因此，不规则多边形的面积为:

(8)

1.3.2 不规则多边形坐标

零件排样过程中，需要记录零件的质心(x,y)以及旋转的角度，来确定零件的排列位置。由于不规则零件有凹凸两种，针对凸多边形，可直接根据多边形的坐标点求解质心，n条边的凸多边形的质心求解如式(9)所示：

(9)

对于凹多边形则不能根据上面的方式进行计算，因为上述方式只关注了坐标点，而没考虑组成的图形。对于凹多边形，相同的顶点分布，可能组成不同的多边形，且质心相差很大。于凹边形，可以将它切割成多个三角形，其中每个三角形可以抽象为一个带质量的点p，点的位置为三角形的质心，根据n个点的系统的质心求解公式，可得凹边形质心求解公式：

(10)

其中:t1,t2,…,tn为分割的三角形质心，s1,s2,…,sn为三角形的面积。

零件在排样过程中，需要进行一定程度的旋转，使得排列更加紧密，因此需要根据旋转的角度，确定不规则多边形的位置坐标。多边形的旋转操作是指将多边形的各个顶点相对某参考点旋转一定角度后得到新的顶点构成新的多边形。如图4所示，零件P逆时针旋转角度为θ，求解旋转后的A点坐标。

x′=x×cosθ-y×sinθ,

y′=x×sinθ+y×cosθ。

(11)

逆时针旋转时θ>0，顺时针旋转时θ<0。

2 不规则零件排样优化算法

2.1 启发式算法预处理

由于不规则件轮廓的复杂性，在排样之前首先利用启发式算法对不规则多边形进行预处理。排样之前零件的预处理主要是针对不规则件的几何特征信息，对零件进行组合、填充等操作。本文对零件的预处理主要根据零件的几何特征通过平移和旋转等操作，对其进行双排或对排操作，使组合后的零件形状为矩形或近似矩形。零件的预处理将不规则件组合为较规则的件，简化了排样的复杂度，在一定程度上简化排样过程中的重叠检测和碰撞靠接，能够较好地提高算法的执行效率，生产规模越大，优势越明显，在实际工业大规模生产中的应用是非常重要的。

2.1.1 局部零件组合

由于不规则零件轮廓的复杂性，根据零件的特征，对不规则多边形零件进行双排或对排，即将其中一个零件旋转180°与另一个零件进行对排，将两个零件的互补边进行碰靠检测，使其排列紧密，如图5所示。将组合后的零件包络成矩形，然后比较两种组合方式所形成的包络矩形的面积，选取面积小的组合方式来作为零件组合排列的方案。

预处理后的零件如果矩形包络较好，可进行联排，即对单次双排或对排所得复合零件的形状再次进行普通单排，使零件之间更加紧密。

在预处理过程中，零件的组合排放需满足以下约束：

(1)将第i个零件放在第i-1个零件的右边，使零件紧密贴合；

(2)零件之间不得重叠；

(3)组合零件的最长边不能超过矩形板材的宽，否则，停止组合。

不规则零件在预处理时，可选择不排列、单排或双排等组合方式，而组合的目的是为了将不规则件转成矩形件参与排样，因此通过比较每种方式的包络矩形的面积大小，来选择相应的方式对不规则件进行预组合。

2.1.2 碰撞检测

在零件组合排列时需要进行零件的定位以及碰撞检测，为了更好地判断零件之间的位置，采用已有的经典方法——临界多边形(NFP)方法[14]，能够较好地实现图形的精准定位。如图6所示，对于给定的两个多边形A和B，保持多边形A固定，将多边形B绕多边形A旋转一周，并使得多边形B至少有一点与A接触但不能重叠，旋转一周后，多边形B上的参考点所形成的轨迹便是B相对于A的临界多边形，记为NFPAB。

根据构建的临界多边形NFPAB，在零件排放中便可以较快地判断两个多边形之间的位置关系：

(1)当B的参考点在NFPAB外部时，B和A不相交；

(2)当B的参考点在NFPAB内部时，B和A重叠相交；

(3)当B的参考点在NFPAB上时，B和A刚好接触。

2.1.3 填充处理

对已排样零件的孔和零件之间的封闭区域进行检测，对这部分未利用区域进行填充处理，其中不能填充的区域称为废料，具体来说有两种情况：比未排的零件中最小的尺寸面积还小的区域为废料；不能放置未排零件中的任何一个的区域称为废料。填充处理的目的就是降低废料率，提升板材的利用率。

针对封闭区域填充零件的具体步骤如下：

(1)计算未利用区域E的面积S；

(2)搜索所有面积小于或等于S的待处理零件，记作集合Ι，数量记作K；

(3)计算E和填充零件Ι的形心坐标点，然后放置零件Ι与E的形心重合，并将填充零件进行旋转，以使得该坐标均在填充区域的内部，若可填充则执行(5)，否则执行(4)；

(4)继续查找集合Ι中的零件，若仍存在待填充零件则返回步骤(3)，否则在该区域内不存在合适的零件可填充；

(5)将不规则零件的坐标值存入集合Η。若查找完毕，则执行步骤(6)；

(6)比较集合Η中零件的面积大小，选择面积最大的零件排入区域E。

2.2 蚁群学习算法排样

零件预处理后，采用群智能算法——蚁群算法[15-17]对处理后的零件进行排样。群智能算法能够较好地在全局进行搜索，以避免较快地陷入局部最优解中。该算法的寻优过程主要包含两个阶段：①适应阶段，在该阶段信息素会不断积累，以调整各个候选解的自身结构，性能好的解，该信息素积累的就越多，而信息素多的解则会有较大的概率被再次选择；②协作阶段，各个候选解之间进行信息的交流，最终使得算法更好地向最优解或近优解收敛。

2.2.1 信息素初始化

在该算法中，信息素和启发式信息会影响蚂蚁的行动，蚂蚁访问每个节点的先后顺序对应着零件的排放顺序，而在板材排样问题中，定序规则影响最终的排样布局。因此，如何定义排样问题中的信息素、启发式信息以及信息素的更新规则，是问题求解的关键及重要内容。

在实际排样问题中的定序规则，通常按零件面积从大到小排放，在排样中产生的空隙用小零件进行填充，以提高板材的利用率。另一方面，考虑到零件的形状，对于长宽比相差大的矩形件对板材空间要求更高，因此可以优先排列这样的零件。因此定义：

ηi=α×(l×w)+β×(l/w)。

(12)

式中：l，w为矩形件i的长和宽;α表示矩形件面积在启发信息中所占权重值;β表示矩形件长宽比值在启发信息中所占权重。

2.2.2 状态转移规则

(13)

式中：τj(t)表示t时刻矩形件j上信息素的强度值；ηj在排样问题中表示排列矩形件j的启发信息值；β为常数值，表示矩形面积值对蚂蚁选择待排件的影响因子参数；allowedk={r1,r2,…,rn}表示下一步蚂蚁k允许选择的矩形件，与之对应，禁忌表tabuk用于记录蚂蚁k当前已选取的矩形，在以后的搜索中该集合的矩形件不能被访问，在排样过程中集合allowedk，tabuk会随着零件的排放进行动态更新。

2.2.3 信息素局部信息更新

在蚂蚁运动过程中将选中的矩形件参与排样，同时会更新矩形件上的信息素，但在排样过程中，蚂蚁的访问顺序决定了矩形件排放的顺序，而由于排放顺序的不同，排样结果也不同，则更新的信息素大小也不相同。假设越早被访问到的矩形件，则该矩形件上被蚂蚁留下的信息素增量就会越大。信息素局部信息更新是指在搜索矩形件排样的过程中根据矩形件排放的顺序实时更新矩形件的信息素浓度，信息素更新规则定义如下：

τi+1=(1-ψ)×τi+ψ×τ0。

(14)

式中：ψ为初始参数(0≪ψ≪1)，τ0为信息素浓度的初始值。

2.2.4 适应度函数

随着不规则零件逐渐排入板材中，会产生众多零碎的水平线段以及空隙，则可以选择合适的零件进行填充处理，而在排样矩形件选择顺序中，将小零件放置在后进行排列，可以较好地对余料空隙进行填充。另一方面，板材排样以最大化利用率为目标函数，即排样零件相对紧密，以使得排样板材高度最低，因此更小的板材高度代表着更优的学习效果，而蚁群算法中适应度函数表示期待优化的方向。基于此，定义适应度函数如下：

f=Area′/Area+1/hri。

(15)

式中：Area′指已排样零件的总面积，Area为所生成的排样图最大高度以下的板材面积，hri表示当前零件排入板材时的最低轮廓线。显然,适应度函数的数值越大越好。

2.2.5 求解算法及步骤

蚁群学习进行板材排样的流程如图7所示，具体步骤如下：

步骤1初始化矩形件排样的相关参数值。

步骤2循环执行以下步骤：

(1)假设初始有m只蚂蚁，首先按一定的策略选择它们的初始矩形件，并加入到禁忌表tabuk中。

(3)根据适应度值优化排样，生成排样图，计算出对应排样图的板材利用率，得出本次迭代的最优排样方案，保存当前矩形件的定序及定位信息。

(4)判断当前解空间中是否存在比目前最优解更优的解，如果存在则更新最优解，更新最优排样方案。

(5)对排样矩形件进行信息素修正。

步骤3定义count值为迭代的次数，每轮排样过后count=count+1，如果count小于最大迭代次数，则重新初始化相关参数，转步骤2，进行新一轮的搜索排样；如果迭代次数达到最终值，则输出当前的最佳排样方案，程序结束。

3 仿真与结果分析

为验证本算法的优越性，在VS2010及MATLAB 2018Ra平台下进行仿真实验，本文预处理算法与包络矩形算法对不规则件进行排样对比，采用欧洲排样问题兴趣小组ESICUP提供的基准问题数据以及自定义的一组数据作为测试算例。

由表2排样结果可得，本文改进算法的利用率远高于包络矩形算法，虽然本文预处理过程相比于直接包络矩形处理复杂，但耗时并没有大幅度增加。为直观地比较两种算法的排样结果，本文给出Trousers数据集下的排样方案，图8为包络矩形算法板材一排样图，图9为包络矩形算法板材二排样图，图10为本文算法板材一排样图，图11为本文算法板材二排样图。

表2 算法排样结果对比

由排样图可以看出，包络矩形算法不考虑零件的形状，都统一转化为矩形件进行排样，排样中产生了较多空隙，严重造成了浪费，而本文算法针对不规则零件进行预处理组合，使得零件排列更加紧密，减少浪费，具有较好的排样效果。

4 结束语

本文对不规则零件优化排样进行研究，提出了一种基于启发式预处理和蚁群学习的混合排样算法来求解此问题。针对单一算法排样板材利用率低，处理时间长的缺点，在排样过程中首先对图形进行预处理，使其组合为矩形件或近似矩形件，提高了板材排样利用率。然后利用蚁群学习算法，对组合后的零件进行排样。通过实验验证，板材利用率较高，但是蚁群算法的求解效率在很大程度上受到参数取值的影响，如何选取适当的参数，使不规则件优化排样进一步取得更优的解，还有待继续研究和改进。另一方面，由于本文处理的不规则零件形状轮廓均为直角边，没有考虑曲线轮廓，这将是未来研究的工作重点。