基于贪心混合定位算法三阶段排样问题研究

陈烨烨,李捍东

(贵州大学电气工程学院,贵州 贵阳 550025)

0 引言

在现代制造和加工行业中,矩形件排样作为工厂下料第1步,其原材料利用率最大化是提高工厂经济效益的重要环节[1]。从数学复杂度的角度来看,大多数类型的矩形块布局问题都属于多项式复杂程度的非确定性问题(non-deterministic polynomial,NP),该类问题计算复杂,难以得到最优解[2],且在实际生产中,需要满足特定工艺。因此,构建一个算法模型,使得该模型能够缩短计算时间、提高板材利用率并同时满足特定生产工艺是此类问题的研究重点。

对于矩形件排样问题,国内外学者已开展了相关研究,并取得了一定的研究成果[3-5]。目前,三阶段排样方式主要有3种不同类型:三阶段非精确排样(three-stage non-exact cutting pattern,3NE)、三阶段匀质排样 (three-stage uniform cutting pattern,3E)、三阶段同质排样 (three-stage homogeneous cutting pattern,3H)[6]。其中,3E 和 3H 排样方式采用齐头切方式,在3个阶段内切割出准确尺寸的方形件,属于精确排样方式。目前,矩形排样优化算法主要为启发式算法和群体智能优化算法。启发式算法主要用于处理矩形件定位问题,BL算法[7]采用最下最左的“占角”思想将矩形件垂直向下、向左平移确定矩形件的最终排列位置。贾志欣等[8]提出最低水平线法对矩形件位置进行确定,根据矩形件的高度不断更新最低水平线直至不能放入;张德富等[9]提出砌墙式启发算法,将板材进行区域划分,设置相应的放入条件,以此提高板材利用率。群体智能优化算法主要用于定序,确定矩形件排布顺序,包括模拟退火算法、蚁群算法、粒子群算法和遗传算法等[10]。文献[11]对传统的遗传算法进行改进,使用并行交叉遗传算法来解决二维不规则的排样问题,但该算法具有极强的随机性,在数据集中表现不一;文献[12]提出一种遗传-贪心混合搜索算法,首先使用遗传算法对矩形件进行优化排列,再使用贪心算法对择优后的工件序列进行二次优化,使工件排布更合理,利用率更高,但遗传算法进行序列择优时,需缓慢迭代才能得到最优解;文献[13]使用传统的贪心算法对矩形件进行无约束排样,以面积最大的矩形件为局部搜索目标,以此来提高板材利用率,该算法流程简单,排样速度快,但原片的利用率比较低;文献[14]在传统的贪心算法上加入局部枚举求解方法,解决齐头切排样问题的同时提高了原片利用率,但运算时间会随着枚举空间的增加成指数增长,不适合应用在矩形件数量多的排样场合。

针对上述算法存在的问题,本文提出了贪心混合定位算法模型,以板材利用率为优化目标,采用分区占角的启发式算法[15]确定矩形件的排布位置,再采用贪心算法对矩形件排布序列进行优化,以达到板材利用率最大。

1 混合整数规划模型

1.1 目标函数

矩形件排样优化属于典型的多项式复杂程度的非确定性问题(NP)[2],对于此类计算复杂度高的问题,本文构建了混合整数模型加以解决。排样优化的目的是优化原片排布,提高板材的利用率。基于矩形件排样流程,研究发现,影响板材利用率的参数主要有5个,分别为产品总数、产品的长和宽、使用板材的总数和每块板材的面积,因此,本文以板材利用率为目标,提出的目标函数为

(1)

式中:N为产品总数;lk、wk分别为第k个产品的长和宽;n为使用板材总数;Slw为每块板材的面积。

1.2 约束条件

为满足工厂特定生产工艺需求,设置如下约束条件。

a.齐头切约束。

本文使用齐头切工艺对矩形件进行切割。假设有一组矩形件{k1,k2,…,kn},集合为K,排布在长为2 440 mm,宽为1 220 mm的原片上。以板材左下角为原点建立坐标系,如图1所示,坐标系x、y表示板材的长和宽。板材上的排布为齐头切排布,即任何1次直线切割都要保证板材可分离,换言之,每次直线切割都应使得板材分成2块。

图1 坐标系建立方法及齐头切示意

本文采用三阶段齐头切精确排样方式,具体为生产1个产品最多只能切3刀。因此在分区类型为Type3时,产品的长或者宽应该等于分区的宽。

W3=ljorwj

(2)

式中:W3为当分区类型为Type3时分区的宽;lj、wj分别为第j个产品的长和宽。

b.切片之间不能相互重叠。

(3)

(4)

式中:xj+1、yj+1为第j+1个产品的左下角顶点坐标;xj、yj为第j个产品的左下角顶点坐标;lj、wj分别为第j个产品的长和宽。

当分区类型为Type3时,应该满足约束如式(3)所示,当分区类型为Type1或者Type2时,应该满足约束如式(4)所示。

2 算法分析

2.1 BL算法

BL算法是一种二维矩形件排样问题的算法[7],该算法的思想主要是“占角”,待放置的矩形件从右上角进入,最终到达左下角;其移动方向固定,只能垂直向下、向左平移,且矩形件放入的最终位置不能继续向下、向左进行移动;当矩形件放置完毕或者原片材料没有多余位置放置矩形件为止。具体过程如图2所示。

图2 BL算法过程

由图2可见,BL算法步骤如下:

a.矩形件从右上角进入,向下平移。

b.接触到原片边界或者已放入的矩形件,不再继续向下移动,转而向左移动。

c.当到达左边界或者接触到左边已放入的矩形件,左移停止,转向下移。

d.当把原片上左下角“填满”,即不能向下、向左移动时,矩形件放置完成,并转向新的矩形件放置。

BL算法虽然可以解决二维矩形排样问题,但在进行排样时,会存在待放入的矩形件与已放入的矩形件存在高度差,导致排样时板材出现大部分空余,造成板材的浪费,降低了材料的利用率。

2.2 分区界定

基于上述研究,为了更好区分板材切割过程中出现的不同情况,本文引入分区[15]。分区是由切割线与板材构成的为未被放置的区域。以原片左下角底点为坐标原点,原片的长为x轴,原片的宽为y轴。将板材切割过程中的3种情况用3个分区类型(Type1、Type2、Type3)来表示,如图3所示。

图3 分区类型

由图3可知,图3a为Type1分区,即未放置矩形件的原片,将第1块矩形件从左下角位置放入,然后根据齐头切原则,在矩形件最右侧进行完全切割。切割之后的区域为Type2分区,如图3b所示,在该分区继续放置矩形件;放置矩形件还留有区域,则设置成Type3分区,如图3c所示,在该分区放置的矩形件的长或者宽必须与该分区的宽相等。如果Type3分区已经没有剩余空间可放入矩形件,则舍弃该分区,在该分区上方开辟新的Type2分区,如果Type2分区不能放入任何矩形件,则在当前原片剩下的部分开辟新的Type1分区,如果Type1分区也不能放入任何矩形件,则说明当前原片已经用完了,所以选择新的原片开辟新的Type1分区。以上是分区放置原则。

产品不能超过分区的边界,具体约束如式(5)和式(6)所示。

lj≤LiorWi

(5)

wj≤LiorWi

(6)

式中:lj、wj分别为第j个产品的长和宽;Li为分区i的长;Wi为分区i的宽,i=1,2,3。

为了能在分区中将产品j切出,产品j的长不能同时大于分区的长和宽,产品j的宽也不能同时大于分区的长和宽。

分区不能超过原片的边界,原片的规格为2 400 mm×1 200 mm,如式(7)所示。

(7)

式中:xi为分区i左下角的横坐标;yi为分区i左下角的纵坐标,i=1,2,3。

2.3 贴边度

本文在BL算法的基础上加入贴边度,即矩形件与在板材右边界的距离。当分区类型为Type2或Type3时,取放入矩形件与有边界的最小值为第一贴边度,该值是一个正值。随着放入的矩形件,第一贴边度值不断进行更新,所添加的矩形件不能超出分区边界。贴边度值越小,说明该矩形件放置越贴合,对整体布局影响越小,板材面积空余,原片利用率就可以得到较大提升。

由图4可知,图4a显示的Type2分区放入矩形件,b代表贴边度,L2表示Type2分区的长度,图4b显示的Type3分区放入矩形件,L3表示Type3分区的长度,分区2贴边度计算如式(8)所示,分区3贴边度计算如式(9)所示。

图4 贴边度放置

bk=(L2-lk)min

(8)

bk=(L3-lk)min

(9)

式中:bk为第k块矩形件的第一贴边度。

2.4 贪心混合定位算法

使用贪心算法对排布顺序进行优化,之后使用混合定位算法对矩形件进行排布,找出一个最佳的排布顺序。对于一个给定的产品序列号,该算法按序列中的排列方式依次将产品放入箱中,每次都将产品放到一个目前来看最优的位置,如果当前产品在任一分区无法排布,则将产品放入候选序列,考虑剩余可以进行的产品,以此来提高板材的利用率。算法框架如图5所示。

图5 算法框架

由图5可知,算法步骤如下:

a.对产品进行排序,并初始化分区类,将分区类型初始化为Type1分区。

b.使用贪心算法对输入列表产品进行序列优化并输入优化后的序列。

c.判断产品能否放入当前分区,若能放入,将产品放入该分区,并转向步骤d;若不能放入,则转向步骤e。

d.更新分区类型,将现有分区更新为放置矩形件之后出现的分区,并转向步骤f。

e.判断剩余产品能否放入该分区,若能放入,转向步骤d;若不能放入,开辟新分区,并转向步骤c。

f.判断产品列表是否为空,若不为空,程序转向步骤b;若为空,程序继续执行。

g.程序结束。

3 实验验证

3.1 实验数据

为了更好验证本文所提贪心混合定位算法的有效性,本次实验环境为Python3.7,实验数据采用华为杯数学建模中的4组板材数据,每组数据集有700多块工件。原片规格为2 440 mm×1 220 mm,部分实验数据如表1所示。

表1 矩形件排样数据集(部分)

实验数据包含产品序列号、产品材质、产品数量、产品长宽以及订单号,每种材质的矩形件需在同一块原片上进行切割,4组数据中,每组数据的矩形件材质均相同,故不考虑材质不同问题。

3.2 实验结果

对4组数据进行数据预处理,将矩形件按照长度从大到小排列。结合贪心混合定位算法,运用Python3.7进行实验。使用4个数据集分别进行10次实验。表2中记录的是矩形件排布信息,包括所用的第几块原片,原片上排布的矩形件编号,矩形件左下底角位于原片上的x、y坐标以及在x、y方向的长度。图6根据表2所提供的数据进行绘制,显示的是矩形件在原片上的排布结果。

表2 矩形件排样数据集(部分)

图6 矩形件排布

由表2和图6可知,原片上排布的是序列号为256、222、311、156、710、296、774、703、647、583、227、143、680、432、417、560、171的矩形件。排布在第86块原片上,实验结果如表3所示。

表 3 实验结果

由表3可知, dataA1原片利用率为94.15%,所用时长为23.56 s;dataA2原片利用率为93.32%,所用时长为20.16 s;dataA3原片利用率为95.05%,所用时长为23.56 s;dataA4原片利用率为94.67%,所用时长为30.21 s。

3.3 对比分析

使用数据集所包含的4组数据,对贪心及局部枚举算法[14]、并行交叉遗传算法[11]以及遗传贪心混合搜索算法[12]进行对比测试。在4组数据中4种模型得到的原片利用率对比结果如表4所示,实验运行的时长如图7所示。

表4 不同模型利用率对比 %

图7 不同模型在测试数据中的运行时长

由表4可知,在数据集dataA1中,本文算法原片利用率较其他算法分别提高4.14百分点、2.79百分点、0.90百分点;在数据集dataA2中,分别提高5.37百分点、0.20百分点、0.72百分点;在数据集dataA3中,分别提高2.84百分点、7.91百分点、0.35百分点;在数据集dataA4中,分别提高9.55百分点、4.46百分点,较遗传贪心混合搜索算法利用率低0.93百分点。从整体来看,贪心混合定位算法优于其他3种算法,且在4个数据集中算法优化结果较为稳定。

由图7可知,贪心混合定位算法在运行时长上明显优于其他3种算法。最长时长仅为30 s,贪心及局部枚举算法最低时长为1 800 s;并行交叉遗传算法最低时长为7 800 s,遗传贪心混合搜索算法最低时长为9 600 s。因此在处理多数量矩形件排布时,本文模型具有显著优势。

4 结束语

本文针对三阶段矩形件排样优化问题,以板材利用率为目标,提出贪心混合定位算法。

a.使用贪心算法对输入序列进行优化,使得矩形件能更快速地进行排布。

b.使用混合定位算法对矩形件的位置加以确定,使得矩形件在板材上排布最优,提高板材利用率。

本文方法经实验验证,能在一定程度上提高板材利用率并能在较大的数据集中进行快速排布。在4个数据集中,本文方法利用率波动较小,算法较为稳定。