基于蚁群算法及矩形法的钣金排样算法研究

李荣强，吴淑芳，冯梓彤，高 鑫，王靖宇

(1.中北大学机械工程学院，山西 太原 030051) (2.山西省起重机数字化设计工程技术研究中心，山西 太原 030051)

钣金零件在工业生产中应用十分广泛，研究钣金排样策略可以避免钣金零件切割过程中不必要的材料浪费。钣金排样对钣金件的合理性与经济性等具有重要影响[1]，因此设计有效的钣金排样算法具有重要意义。在我国工业生产中，主要依靠人工经验进行钣金排样，需要经过不断尝试才能找出较为可行的方案[2]。这种排样方法主观性太强，效率较低，并且无法保证排样结果为最优。

针对上述问题，国内外专家学者进行了诸多研究：文献[3]将人工排样经验与启发思想结合，提出根据零件长宽尺寸定序排样；文献[4]针对板材不限宽度的问题，使用多种智能算法对实例进行计算，证明同时使用多种算法对得到排样结果有促进作用；文献[5]将遗传算法与模拟退火算法相结合对钣金排样策略进行研究，然后采用填充算法填充剩余部分；文献[6]针对二维不规则排样问题进行了研究；文献[7]针对钣金件展开以及排样问题，使用AutoCAD进行优化排样；文献[8]对剩余矩形法进行深入研究，并采用遗传算法对定序问题进行了研究。

目前钣金排样研究依然存在一些不足：对于零件尺寸特征的总结较为片面，没有将长度、宽度、面积等因素综合考虑；对定位算法的使用不够完美，未达到理想的排布效果；对于一些可用矩形算法排样的零件，没有适合的改进措施。因此本文主要针对排样算法以及钣金图形优化两大方面进行研究。

1 排样问题简介

排样问题是指将需要排样的零件放置到一块宽度不变的板材上，且零件之间不能干涉。数学模型如下：

假设参与排样的第i个零件为Pi，则在板材B上参与排样的零件P1，P2，…，Pn必须满足以下约束条件：1)Pi，Pj互不干涉，i,j=1,2,…,n，且i≠j；2)零件Pi必须完全在板材B内；3)必须满足所需的工艺加工要求，比如板材边距等参数。

在钣金件排样过程中，需解决钣金零件的定位问题。首先，用(xi,yi)表示零件位于板材上的位置，其中xi为宽，yi为高,除此之外，需要对零件进行旋转摆放，旋转角度αi顺时针方向为正。因此位置可表示为Mi(xi,yi,αi)。

Di(xi,yi,αi)∩Dj(xj,yj,αj)=Ø

(1)

0

(2)

0

(3)

式中：Di(xi,yi,αi)为零件属性。

由于目标函数的分子固定，因此目标函数可简化为：在满足式(1)、(2)、(3) 3个约束条件的情况下，使WH最小。在排样中，定义宽度W固定，所以该问题的目标为求解高度H的最小值。

2 矩形排样算法改进

2.1 排样优化策略

在剩余矩形法中，当排入零件顺序不合适时会造成空间上的浪费，从而产生无法填补的矩形空间，如图1左图所示，在3和4两个零件中，按排样效果应该优先选择4，如选择3先行填入就会得到右图所示的结果，造成空间浪费。

图1 剩余矩形法造成的空间浪费

本文针对此类情况进行改进，意在避免不合适零件被优先排样。以图1为例，在产生剩余空间时，先用空间大小与待排零件的长和宽进行匹配，若匹配成功则优先填入此零件，从而减少板材浪费。优化后的排样结果如图2所示。

图2 优化后剩余矩形算法排样结果

2.2 改进剩余矩形算法排样过程

优化后的排样步骤如下：

1)进入循环，多次排样,预设hmin(hmin为每次排样的最小高度，本文设置为零件宽度之和)。

2)按最左最下的原则，将随机选出的第一个零件排入板材中，计算剩余矩形空间。

3)在未排样零件中选取零件，首先挑选符合要求的矩形空间，将面积大小相近以及排入点最低作为判断要求排入零件，计算剩余矩形空间，再将零件信息记录到已排样信息中。

4)对剩余矩形空间信息与零件信息进行匹配，若长宽相近则将此零件优先排入，并将结果记录到已排样信息中。

5)重复步骤4)、5)直到所有零件排样完成为止，记录排样高度h。

6)将h与hmin对比，若h小于hmin则保留此次排样序列及排样图，删除已有的排样图并且令hmin=h，直到循环结束，绘制出排样图以及利用率曲线图。

2.3 定序问题研究

排样顺序是一个必须要考虑的问题，本文使用蚁群算法对定序问题进行研究。蚁群算法是一种较好的寻优算法，目前蚁群算法使用的启发式为面积大小，然而只考虑面积这一因素无法全面概括一个矩形零件的全部特性，本文以(yi+xi)表示长宽特性，蚁群算法启发式ηij为:

ηij=aSi+b(xi+yi)

(4)

式中：a为面积权值；b为长宽特性权值。

为对a,b值进行确定，本文使用2.2节零件定位方式对a,b值进行测试，得到当a=2、b=7时排样结果较好，因此启发式确定为：

ηij=2Si+7(xi+yi)

(5)

2.4 蚁群算法与剩余矩形算法排样过程

根据上述描述可设定算法步骤如下：

1)根据零件信息计算式(5)。

2)进入蚁群算法循环，判断是否达到最大代数,若达到最大代数跳到步骤7)；若没有执行步骤3)。

3)蚂蚁开始随机选择零件，判断是否所有蚂蚁都已排样完成，若完成返回步骤2)。

4)根据式(6),蚂蚁随机选择零件进行排样:

(6)

5)按2.2所示的排样过程进行零件排样，若触发空间匹配则不使用步骤4)进行选择，直接将此零件排入，记录零件信息，否则重复步骤4)。

6)判断零件是否排完，若排完按式(7)更新信息素，返回步骤3)；若未排完继续执行步骤3)、4)、5)。

(7)

(8)

7)绘制排样图，得出迭代次序图。

3 钣金类零件简化

3.1 矩形钣金件简化

因为柜体零件大多为凸形钣金件，如果将其简单地定义为矩形，会造成材料的浪费。若按不规则零件排样，又会增加算法难度，所以本文提出图3所示的策略来优化此类问题。

图3 阶梯形钣金示意图

为减少计算量，使用式(9)求解λ。

(9)

当比值λ大于1/10时，则将其视为一个矩形。如图4所示，将B部分作为剩余空间区域进行记录。此区域与其他空间区域不存在相容关系，因此需要提前排入。采用这一方法可以减少资源的浪费。

图4 凸阶梯形钣金简化图

3.2 非矩形钣金件简化

图5(a)所示为目标图形，以往的处理方案如图5(b)所示，这种处理方案会造成上方空间浪费，因此要先对目标图形的角度进行比对，若有相同(或相近)的则先进行组合，否则使用式(9)进行计算，若比值大于1/5，按图5(c)所示的方案进行排样。

图5 非矩形钣金件简化图

3.3 实现方法

综上，本文采用的解法如下所述：

1)在预处理阶段，利用3.1节所提到的方法进行简化，然后建立其关系式。在填入其中一块时，将所对应的剩余空间加入到原有的剩余空间集合中。

2)将钣金类零件优先排入板材，以此保证这些零件所对应的剩余空间能够优先排入钣金类零件。

4 实例分析

4.1 矩形钣金件排样

本文以文献[9]中的算例2为例，使用MATLAB进行实例测试，设置蚂蚁数量m=30，α=1.6，β=10.2，ρ=0.1，Q=1×106，迭代次数为100代。得到的排样结果如图6所示。

图6 改进剩余矩形法排样图

排样顺序为{-30 10 48 12 39 14 20 49 16 54 42 27 18 19 44 7 40 38 43 60 24 15 51 47 28 11 33 13 34 29 23 50 35 55 17 41 -2 57 45 59 3 -56 25 26 -9 1 46 5 21 32 58 22 53 4 31 37 6 52 8 36}，板材占用最大高度为355 mm，材料利用率为94.6%，图7为以零件面积为蚁群算法的优缺点启发式和按本文所提蚁群算法启发式迭代对比图。

图7 迭代曲线图

通过表1统计结果可知：相比于文献[9]的算法，本文算法的板材利用率提高了3.5%；相比普通蚁群算法，收敛提前了10代。由此可知本文算法解决矩形排样问题的效果优于其他两种算法。

4.2 钣金类零件排样

以4.1节中矩形组成几个凸形钣金件为例，用MATLAB进行实例测试，其步骤为：1)进行数据输入；2)按3.3节所述，将以下几个矩形(件10、件20、件30、件39)进行切分、排样，如图8所示。

表1 结果对比表

图8 阶梯形、斜面形钣金件

如图9所示，排样顺序为{-30 20 39 10 12 29 41 13 28 43 50 -17 25 54 42 15 48 18 16 1 27 33 22 21 14 59 53 35 38 44 34 11 60 19 55 2 26 49 47 7 57 40 23 -56 51 24 9 5 3 -46 4 31 32 58 6 -52 8 -36 -37}，板材占用最大高度为353 mm，材料利用率为94.5%。

图9 阶梯形、斜面形钣金件排样图

5 结论

本文通过对蚁群算法以及钣金零件排样问题的研究得出以下结论：

1)用空间匹配原则对剩余矩形法进行改进，解决了排样定位问题，提高了板材利用率。

2)利用蚁群算法对矩形零件排样的定序问题进行研究，使用面积和长宽尺寸因素提取零件特征，经算例验证，此启发式可以有效提高排样效率和加快蚁群算法的收敛速度。

3)针对不规则钣金件浪费板材问题，进行图形优化，提出零件自带剩余空间策略，使用改进剩余矩形算法进行仿真计算，结果证明可以有效解决此类钣金件排样问题。