基于排样矩形的直角边零件下料算法①

郭百海,隋 毅

(青岛大学 计算机科学技术学院,青岛 266071)

直角边零件的轮廓由直角边组成,并且任意相邻两边之间的夹角都是直角,对这种零件的排样布局称为直角边零件下料问题.直角边零件在许多领域中都有广泛的应用,如普通机械、专业设备等制造行业的型材、金属切割、木材加工、建筑行业的平板玻璃切割等,但直角边零件加工普遍存在余料剩余较多,加工效率较低,原材料浪费等问题[1,2].因此,优化直角边零件排样布局,使直角边零件下料后产生的废料最少,即板材的利用率最高,对降低企业生产成本具有重要意义和实用价值.

目前直角边零件下料布局优化问题已有大量相关研究,Gilmore 和Gomory[3]利用动态规划算法求解矩形零件的布局被认为是解决二维切割问题的基本方法；张燕玲等[2]基于改进的Basely 模型[4]设计实现了一种可用于直角边下料问题的整数规划模型；戚得众等[5]提出了一种基于工艺与形状特征的下料零件分组下料优化模型；Fabio Furini 等[6]通过建立混合整数线性规划模型表示二维切削问题中一般切刀约束的问题；葛志辉等[7]提出一种基于工艺约束策略的二维不规则排样算法；张旭等[8]给出了一种基于最大移动距离的启发式算法,改善了排样结果.然而,由于直角边零件下料布局优化是NP-Hard (Non-deterministic Polynomial Hard)[9]问题,不能在多项式时间内解决,多数研究获得的结果只能趋近于最优解而很难达到最优解；即便获得最优解,由于现有研究普遍将材料利用率作为唯一的优化目标,获得的排样结果虽然是理论上的最优,但切割操作难度却较大,依然存在实用性不强的问题.

针对上述问题,本文提出了一种基于排样矩形的动态规划方法,将板材的布局问题转化为若干个优化子问题,而每个子问题的最优解能够通过本文提出的排样矩形得到,在此基础上,基于动态规划思想构建直角边零件下料问题的求解算法,该算法通过将NP-Hard 问题转换为在多项式时间内可以进行求解的一般问题,降低了算法求解的时间复杂度.实验结果表明,对于一般直角边零件,本算法与传统的直角边零件板材切割相比,板材的利用率提高了30%-50%；同时,本算法在减少板材余料的同时保证了排样简单操作可行,降低了对工艺的要求,在工厂生产中容易实现.

1 问题描述

不失一般性,将板材抽象为L×W的长方形R,L和W表示R的长与宽,左下角为坐标原点(0,0),右上角坐标为(L,W),将R在长和宽两个方向上按照单位长度进行划分得到L×W个小正方形,称之为格点[10],格点的角点坐标表示为(x,y),其中0≤x≤L,0≤y≤W.如图1.

任意直角边零件m均存在一个最小外接矩形r,称r为零件m的最小包络矩形[11],表示为其中分别为r的右上角和左下角坐标.将记为零件的长,记为零件的宽,其中包络矩形r由其右上角坐标和左下角坐标确定.直角边不规则零件及其包络矩形如图2.定义1(m在R上的规范摆放方式).直角边零件m在R上可以有任意种摆放方式,当m的各直角边要么与最小包络矩形r的直角边垂直要么与最小包络矩形r的直角边平行时,称为m在R上的规范摆放方式.

如图1所示,板材R上的T字型零件的规范摆放方式有4 种.易见,对任何直角边零件m,通过旋转,其在板材R上规范的摆放方式最多有4 种.对给定的板材R(L×W),寻找一种使得直角边零件按规范方式摆放个数最多的排样布局,即切割后余料最少,这是一个NP-Hard 问题,不能在多项式时间内进行求解.

图1 板材的格点划分

图2 直角边不规则零件及其包络矩形

设有N个直角边零件在R上规范摆放,ri表示直角边零件i(1≤i≤N)的包络矩形,令 ∩{ri|1≤i≤N}表示N个包络矩形在R上所占区域的交集,当 ∩{ri|1≤i≤N}=Φ时表示N个包络矩形在R上不重叠,反之则表示在R上存在重叠区域.类似的,令 ∩{mi|1≤i≤N}表示N个直角边零件在R上所占区域的交集,当∩{mi|1≤i≤N}=Φ时表示N个直角边零件在R上不重叠,显然,当 ∩{ri|1≤i≤N}=Φ时必然有 ∩{mi|1≤i≤N}=Φ.

直角边零件下料问题：求解在给定长为L,宽为W的板材R上排样N个直角边零件最省料的排样模式,即是求解以下目标函数：

优化子问题1.求解在R上给定宽为w(w≤W)的局域长方形区域内排样p个直角边零件最省料的排样模式,即是求解以下目标函数：

优化子问题2.求解在R上给定长为l(l≤L)的局域长方形区域内排样q个直角边零件最省料的排样模式,即是求解以下目标函数：

针对优化子问题1 和问题2,要在全排列中确定一个最优的排列组合,也是一个NP-Hard 问题.但是,对于此问题,数据量较少时可以通过合理的穷举进行解决.根据文献[12],下面给出排样矩形(Layout Rectangle)的定义.

定义2(排样矩形).根据先验知识对板材R的某一小块区域进行手动排样,确定一个排样矩形LR,使得按照LR沿水平或竖直方向进行排样有一定的规律可循.其中,沿水平方向有规律可循的称为水平排样矩形(Horizontal Layout Rectangle,HLR),HLR的宽度为常数w,长度为可变参数x,零件在HLR上的排样个数满足规律函数Gx(x)；同样,沿竖直方向有规律可循的称为竖直排样矩形(Vertical Layout Rectangle,VLR),VLR的长度为常数l,宽度为可变参数y,零件在VLR上的排样个数满足规律函数Gy(y).

2 基于排样矩形的直角边下料模型

对于直角边零件m,假设总共有4 种不同的规范摆放方式,对于每种摆放方式,都分别存在一个HLR和VLR,则直角边零件m共有8 个排样矩形.将直角边零件m沿第j(j=1,2,3,4,下同) 种规范摆放方式得到的水平排样矩形记为HLRj,排样矩形的宽度记为wj,m在HLRj的排样个数满足的规律函数记为Gxj(x)；同理,m沿第j种规范摆放方式得到的竖直排样矩形记为VLRj,排样矩形的长度记为lj,m在HLRj的排样个数满足的规律函数记为Gyj(y).图3(a)和图3(b)分别是T 字型零件和工字型零件的水平排样矩形和竖直方向排样矩形,其中红色和蓝色区域可以进行排样,浅灰色区域为排样矩形的未利用部分.基于排样矩形可以确定规律函数Gxj(x)、Gyj(y)的具体形式.

针对于直角边下料问题,把它分解成若干优化子问题1 和优化子问题2,然后从这些子问题的解得到原问题的解.

由定义2 可得,采用HLR进行排样可以使得在宽度为w的矩形中零件m的数量最多,因此优化子问题1的解转换为：

同理可得,采用VLR进行排样可以使得在长度为l 的矩形中零件m的数量最多,因此优化子问题2 的解转换为：

按照动态规划[13]的思想,直角边零件在(x,y)处按照方式j(j=1,2,3,4)放置时点(x,y)的最大放置数量N(x,y)的有：

图3 排样矩形

(1)如果排样矩形采用HLR,当y＞wj时,设点(x,y) 的最大放置数量为N(x,y),则N(x,y) 与点(x,y−wj)的最大放置数量N(x,y−wj)有关.点(x,y)的最大放置数量N(x,y)可表示为：

(2)如果排样矩形采用VLR,当x＞lj时,点(x,y)的最大放置数量为N(x,y),则N(x,y)与点(x−lj,y)的最大放置数量N(x−lj,y)有关.点(x,y)的最大放置数量N(x,y)可表示为：

根据上述讨论可知,板材在点(x,y)若要获得最大的零件放置数量,需要考虑以下8 种情况：

采用文献[14]的动态规划算法对建立的式(8)进行求解,具体的算法步骤如下：

Step 1.根据特定的直角边零件m,确定排样矩形对应的规律函数Gxj(x)、Gyj(y).建立两个矩阵NL×W、TL×W,初始化为全0 矩阵.其中N矩阵用来存储各点处的零件最大放置数量,T矩阵用来记录具体的排样方式.

Step 2.按照由左至右、由上至下的顺序递推出在该点(x,y)处的零件最大放置数量,并将(x,y)处的切割方案记录在T(x,y)中.

Step 3.判断当前坐标可否放置零件.将当前坐标记为(x,y),若min(x,y)＜min{wj,lj}(j=1,2,3,4),则表示当前坐标不能放置零件,N(x,y)=0,T(x,y)=0,转至Step 2,否则转至Step 4.

Step 4.根据动态规划的思想,如果已经求得当前点的所有子状态的最优解,那么当前状态的最优解根据式(8)可用所有子状态的最优解推导出来.

Step 5.求解得到整块板材的最优解N(L,W),根据矩阵T(L,W)回溯得到具体的切割方案.

算法的伪代码如算法1.

算法1.切割算法输入：问题的实例参数N,T,wj,lj(j=1,2,3,4),规律函数,输出：问题实例的最优解方案GxjGy j 0 初始化N,T 1 N=zeros(L,W)2 T=zeros(L,W)3 For x in range(0,L)：#约束个数4 For y in range(0,W)：5 If y＞=wj：Gxj 6 tyj=N(x,y−wj)+ (x)7 Endif 8 If x＞=lj：Gy j 9 txj=N(x−lj,y)+ (y)10 Endif 11 N(x,y)=max(tyj,txj)12 T(x,y)=对应N(x,y)取最大值时的切割方案13 Endfor 14 Endfor

3 算例与结果分析

使用的计算机配置环境为Win10,intel CORE i5 8th Gen,8 GB 内存.选用的软件语言Python 3.7.

采用几组相关的基准数据进行测试,基准数据[2]由北京铁路信号公司的生产实例中产生.

针对不同的排样零件类型以及不同的板材尺寸,生成相应地排样方案,并计算出对应的板材利用率,与传统排样算法进行比较,具体结果如表1及图4至图11所示.如表1所示,针对不同的直角边零件,本文提出的算法与传统的排样算法相比其材料利用率都有较大的提高.

表1 不同尺寸板材切割利用率结果

对于一些常见的直角边零件,将本文算法与已有研究文献中的算法进行比较,具体结果如表2和表3所示.结果表明,针对于T 字型零件、十字型零件、凸字型零件,本文提出的算法在材料利用率优于文献[2,15,16]阐述的算法,包括格点改造算法、顶点覆盖算法、以及滚动优化算法.同时,排样矩形的引入使得本文算法提供的排样方案有一定的规律可循,与目前存在的所有算法相比,降低了对机器工艺的要求,更具有实际操作意义.

图4 T 字型切割方案图(210×150)

图5 T 字型切割方案图(2000×940)

图6 凸字型切割方案图(1000×500)

图7 凸字型切割方案图(2000×1000)

图8 十字型切割方案图(1200×500)

图9 十字型切割方案图(2000×1000)

图10 工字型切割方案图(320×160)

图11 工字型切割方案图(650×320)

表2 T 字型和十字型零件板材利用率对比(单位：%)

表3 凸字型零件板材利用率对比(单位：%)

4 总结与展望

本文针对直角边零件下料优化布局问题,提出了一种基于排样矩形的动态规划求解算法,该算法通过将整块板材的优化问题转换为若干最小子优化问题,采用动态规划的思想进行模型的建立与求解.实验表明,与现有的排样算法相比,本算法能够显著提高材料利用率,同时减少了复杂排样的产生,便于在生产中进行操作.未来将进一步拓展本文算法将其应用于二维不规则零件的下料布局优化问题.