考虑切割成本的矩形件优化下料算法

陈 燕，郑欣亮，鲁淑飞，胡小春

(1.广西大学 计算机与电子信息学院，广西 南宁 530004；2.广西财经学院 信息与统计学院，广西 南宁 530007)

0 引言

在中国制造2025和双碳目标背景下，发展资源节约型、环境友好型的智能制造业已成为紧迫要求[1-2]。二维下料问题(Two Dimensional Cutting Stock Problem, TDCSP)广泛存在于汽车、造船等产品制造过程中,该类问题的下料常采用火焰、等离子或激光等分离技术进行切割[3]。考虑切割成本的优化下料算法能够使企业以更低的材料成本和切割成本完成相应的订单需求，进而达到节约资源、降低能耗和减少碳排放的目的。

目前，已有一些研究从不同方面实现了矩形件下料的多目标优化。文献[4-6]研究了余料的再利用问题，能较好地减少整个生产周期的下料成本，并提高余料在未来生产周期中的可用性;文献[7]针对二维钢卷下料问题，不仅考虑最小化剪切损耗，还考虑固定时间和更换速度，提出一种由簇群、排序、条带化和整数规划组成的混合启发式算法;文献[8]同时考虑剪切损耗和机器设置成本，提出一种混合线性规划模型的基因算法;文献[9]采用可并行计算的顺序分组启发式算法，实现了最小化板材数量和减少排样方式的双目标优化;文献[10]提出连分数分支定界算法，在提高时间效率的同时能够有效地简化切割工艺;文献[11]考虑材料成本和机器设置成本，提出成本均衡利用率算法，获得总成本之和最小的下料方案;文献[12]采用列生成框架和三段式布局图设计，通过减少切割刀数，以实现材料成本与切割成本之和最小;文献[13]通过研究任意给定布局图的切割顺序，以获得较高材料利用率和较少切割行程的下料方案;文献[14]综述了有关激光切割路径生成文献，确定了切割路径生成的研究趋势和切入点;文献[15-16]利用共边切割的优势，分别提出阶梯型共边切割策略和启发式共边排样算法，以减少切割路径长度、提高切割效率;文献[17]综合考虑原材料利用率高、切割加工路径短等优化目标，提出一种基于候选板条的连续启发式排样算法，并在此基础上提出采用同质条带共边切割策略分离矩形件，实验结果表明所提算法在保证高原材料利用率的同时，能有效减少切割总路径;文献[18]使用包含材料成本和切割成本的综合成本最小作为下料方案的优化目标，应用顺序价值校正(Sequential Value Correction, SVC)算法框架求解，并以所含矩形件价值最大作度量标准生成布局图。SVC的每一次迭代同时考察多种板材，从中选择产出率最大者作为当前布局图。文献[19]在条带切割的基础上提出同质块切割策略，根据同质条带有无余料、条带所含矩形件数的奇偶性设计板材的切割路径，以减少切割成本。

目前，针对矩形件下料问题的研究大部分采用一刀切(guillotine cutting)工艺[20]，但该工艺存在剪切厚度能力有限、工件表面易塌陷变形等缺点。因此本文研究考虑切割成本的非一刀切(non-guillotine cutting)矩形件下料问题。目前针对该类问题的研究主要存在以下局限：在切割路径优化策略上没有充分挖掘共边切割的潜能；在算法设计上，一般是先考虑减少材料的使用量，降低切割成本只是作为辅助的优化目标，少量文献在下料方案优化层面将二者作为整体，但求解布局图的子问题依然没有将二者同时考虑。因此，本文提出两点改进：①利用不同条带组成的等高块共边特性提出等高块切割策略，并在生成布局图的过程中设置条带优先级，尽可能多地生成等高块，以充分挖掘共边切割潜力；②提出在生成单板材布局图时，以板材综合价值(板材布局矩形件总价值与切割成本之差)最大作为优化目标，通过求解有界背包问题生成当前板材布局图，以板材产出率最高作为优选目标确定布局图和所使用的板材。

1 数学模型及切割策略

1.1 问题描述及数学模型

本文讨论的多规格板材的矩形件下料问题可描述为：在n种长为Lj，宽为Wj，供应量为Dj(其中j=1,…,n)的板材上按照生产工艺要求切割出m种长为li，宽为wi，需求量为di(其中i=1,…,m)的矩形件。在生成布局图的过程中，要求矩形件正交排列、互不重叠且不超过当前所使用板材的边界。假设下料方案有K种布局图，则其整数规划模型为：

(1)

s.t.

(2)

(3)

(4)

1.2 等高块的切割策略

1.2.1 等高块的概念

1.2.2 等高块共边切割策略

以等高块规则对布局图进行块的划分，块间采用“直线型”切割路线进行分离，相邻条带内的矩形件采用“之”字型切割路线进行分离。等高块的共边切割规则如下：

板材上条带布局后存在无余料生成和有余料生成两种情况，条带的布局存在水平和垂直两个方向，同时条带中所含的矩形件个数有奇偶之分，因此将等高块分为8种类型。每个等高块共有4个可供切割的切入点，分别为4个顶点，默认板材左上角为最初切入点，后续块的起点是根据与前一块的切割结束点之间的最短空程来选择。这8种类型等高块以其左上角为切割起始点的路径示意图如图2所示(其他3个角类似)，需要注意的是由于同质块是等高块的特殊形式，图2中等高块共边切割同样适用于同质块。

2 算法设计与实现

求解多规格板材下料方案的算法采用SVC主框架[19]，并对其中的单板材布局图生成算法进行改进，即在生成单板材布局图时同时考虑布局图所含矩形件价值与切割成本，在不影响材料利用率的前提下，尽可能多地生成等高块。

2.1 考虑切割成本的单板材布局图生成算法 SinglePattern()

2.1.1 算法设计

本文以布局图的综合价值最大作为优化目标。假设板材的长宽分别为x和y，用F(x,y)表示该板材上的综合价值，因此最优布局图的求解模型可表示为：

(2)

其中：ci为第i种矩形件的价值;qi为布局图所含第i(i=1,…,m)种矩形件的个数;P为布局图的切割成本;ri为第i种矩形件的剩余需求量;λ为非负整数，其值大小表示对切割成本的重视程度。

设lmin，wmin分别为矩形件尺寸中的最小长度和最小宽度，在尺寸为x×y的板材上生成同质条带的多级规范布局方式，板材的综合价值为F(x,y)，切割成本为P(x,y)，则动态规划的递推公式如下：

当x

(3)

算法使用两个递归函数来实现当前规格板材最佳布局图的生成，SinglePattern()负责进行主板布局图的生成，PlusPattern()负责生成剩余子板的布局图，并返回剩余子板所含矩形件总价值与整个板材布局图的切割成本之差的值。具体实现将在2.1.2节进行介绍。

设F(i,x)表示排入由第i种矩形件组成的条带后的分支综合价值，则F(i,x)=条带价值+(剩余子板所含矩形件总价值-λ×整板布局图切割路径总长度)，四种不同类型的同质条带对应的分支综合价值如下：

FXX(i,x)=vXX(i,x)+PlusPattern(x,y-wi)，i=1,…,m；

FXY(i,x)=vXY(i,x)+PlusPattern(x,y-li)，i=1,…,m；

FYX(i,y)=vYX(i,y)+PlusPattern(x-li,y)，i=1,…,m；

FYY(i,y)=vYY(i,y)+PlusPattern(x-wi,y)，i=1,…,m；

考虑切割成本的单板材布局图生成过程如图3所示。在生成布局图的过程中，每次确定布局一根同质条带，直到满足所有矩形件需求或者剩余子板不能布局任何剩余需求的矩形件为止，图中条带的确定顺序为a3→b1→c2→d2。考察布局新条带的方法为：遍历每种有剩余需求的矩形件，针对每一种矩形件，考虑XX、XY、YX、YY四种条带布局类型(以矩形件1生成的条带为例)，而对于每种类型的条带，会产生一个剩余子板，剩余子板则根据条带产出率进行布局并返回(剩余子板所含矩形件总价值-λ*整板布局图切割路径总长度)的值。以条带分支综合价值大为目标，确定新布局的条带并记录对应的条带信息。

2.1.2 算法实现

函数SinglePattern()用于生成单板材最佳布局图，其伪代码如下：

1 SinglePattern()

2 初始化剩余子板最大综合价值F(x,y)_max=0，取得最大综合价值时条带所含矩形件号maxID=0

3 for(i=1 to nLeftTypes)

4 if(第i种矩形件剩余需求不为0)

5 if(剩余子板大小不能布局第i种矩形件)then Continue

6 else(令F(x,y)=max{FXX(i,x),FXY(i,x),FYX(i,y),FYY(i,y)})//需调用PlusPattern()

7 if(F(x,y)>F(x,y)max)then F(x,y)_max=F(x,y),maxID=i

8 if(maxID=0)then return

9 else

10 更新布局图信息，包括新增条带类型、所含矩形件种类与个数，以及已布局条带总个数、所含矩形件总价值fVal、总面积fArea等

11 根据新增布局条带类型更新剩余子板尺寸

12 递归调用SinglePattern()

其中：步骤2初始化剩余子板最大综合价值和取得最大综合价值时条带所含矩形件号。步骤3～步骤7为遍历所有剩余种类的矩形件，并找出使剩余子板综合价值最大的一根条带作为布局图的新增条带。其中步骤6为考察第i矩形件的4种布局类型并选择综合价值最大的布局方式。步骤8用于判断是否已完成板材布局图的生成，若完成则退出函数，否则转步骤10～步骤12。其中，步骤10为更新布局图信息，步骤11为更新剩余子板尺寸，步骤12为递归调用自身函数以循环生成新增条带直至完成板材布局图的生成。

函数PlusPattern()返回当前剩余子板所含矩形件总价值与整板布局图总切割成本之差的值，其伪代码如下：

1 PlusPattern()

2 接收剩余子板尺寸(x,y)，初始化条带最大产出率Omax=0，剩余子板已布局矩形件总价值V=0

初始化矩形件剩余需求，并保存主板已布局条带的相关信息(条带类型、含矩形件种类及个数)

3 do{ //以条带产出率最大作为择优条件循环布局剩余子板

4 for(i=1 to nLeftTypes)

5 若第i种矩形件还有剩余需求且能够放入剩余子板，令O=max{uXX(i,x),uXY(i,x),uYX(i,y),uYY(i,y)}求出第i种矩形件四种布局图中产出率最大的条带

6 若O=Omax且此条带与前一根已布局条带共边或O>Omax，则令Omax=O，并更新条带信息

7 if(存在产出率最大的条带)

8 将此条带布局到剩余子板，更新布局此条带后的相关信息，包括该条带布局类型、所含矩形件种类及数量、矩形件剩余需求、主板已布局条带数量，更新剩余子板已布局矩形件总价值V=V+此条带价值，根据新增条带布局类型更新剩余子板尺寸，重置Omax=0

9 else break

10 while(true)

11 根据等高块切割规则计算当前整板布局图的切割路径总长度cutLen

12 根据板材综合价值计算公式计算当前整板布局图的综合价值F(x,y)=fVal+V-λ*cutLen

13 if(F(x,y)>F(x,y)max)

14 更新整板布局图最大综合价值、切割路径总长度、布局图所含条带个数。记录最佳布局图条带信息。

15 return V-λ*cutLen

其中：步骤2接收函数SinglePattern()中步骤11更新后的剩余子板尺寸，并初始化条带最大产出率和剩余子板已布局条带总价值，初始化矩形件剩余需求和主板已布局的条带信息。步骤3～步骤10对剩余子板进行条带布局。其中步骤4～步骤8每执行一次便确定布局一根条带，直至剩余子板布局完成。步骤4至步骤6遍历每种剩余矩形件的4种条带布局类型，以条带产出率最大作为选择待布局条带的目标，其计算公式为：

若出现条带产出率相等的情况，则优先放置与已布局的上一根条带共边的条带从而形成等高块。步骤11根据等高块切割规则计算当前整板布局图的切割路径总长度。步骤12为计算当前整板布局图的综合价值。步骤13判断当前整板布局图的综合价值是否大于已记录的整板布局图的最大综合价值，若是则执行步骤14更新整板布局图相关信息，并记录布局图所含条带信息为最佳布局图条带信息。步骤15返回剩余板材所含矩形件总价值与整板布局图切割成本之差的值供函数SinglePattern()调用。

2.2 最优布局图选择算法GetPattern()

SVC启发式算法每次遍历所有剩余规格板材并调用单板材布局图生成算法生成布局图，并从中选择一个最优布局图作为下料方案的一部分[19],本文将板材产出率最大作为选择布局图的择优目标，其中板材产出率=板材中所布局矩形件总面积/板材面积+λ×板材切割路径总长度。设函数SinglePattern()返回当前待排样板材最优布局图，U为板材最大产出率，最优布局图选择算法步骤如下：

步骤1令j=1，U=0。

步骤2若bj>0，则初始化x=Lj，y=Wj；否则，转步骤5。

步骤3调用函数SinglePattern()生成当前板材的布局图。

步骤5若j

步骤6输出最优布局图。

其中：步骤1为算法开始时的初始化。步骤2～步骤3为生成当前规格板材的布局图。步骤2判断当前板材是否还有剩余库存，若有，则初始化布局图生成函数的板材规格。步骤3为生成当前规格板材的布局图。步骤4为计算当前板材的产出率，并判断是否进行最优布局图的更替。步骤5为判断是否所有规格的板材均已生成布局图。步骤6为输出所有规格板材中的最优布局图。

3 实验结果与分析

算法用C#实现，实验环境为i7-8565U的CPU，参数Gmax=500，λ=7。实验分为3部分：①单独验证等高块切割策略的有效性;②采用单算例实验与相关文献及商用软件优化结果进行对比，以验证本文算法和切割策略的叠加优化效果;③在多组随机算例上进一步验证。

3.1 等高块与同质块的切割路径长度对比

由于板材的切割可与下料方案的生成过程解耦，为充分说明等高块的切割比同质块的切割更有利于减少路径长度，使用文献[17]和文献[18]的下料方案，与文献[19]的同质块切割路径长度进行对比。结果如表1所示，表中SL和IL分别表示同质块和等高块的切割路径长度，ΔL表示两者的差值，ΔL%表示路径长度减少的百分比；T_SL和T_IL分别表示下料方案总的切割路径长度，ΔTL表示两者的差值，ΔTL%表示减少的百分比。

从表1可看出，在所有布局图中，采用等高块切割的路径均有不同程度的减少，最多达到11.74%，最少也有2.93%。文献[17]和文献[18]的下料方案总切割路径长度分别减少1 480和3 360，平均减少7.33%。由此说明：等高块切割策略在减少切割路径方面具有有效性。

表1 切割路径的比较

3.2 单一算例实验对比分析

为了验证本文算法和切割策略在矩形件切割下料过程中的可行性和有效性，采用文献[19]的单一算例进行实验，分别运用本文算法和商用软件Cutleader(https://cutleader.com/)对算例进行优化处理，得到两种不同的下料方案。本文算法生成的下料方案如图4所示，含3种布局图，每种布局图使用次数为1，板材尺寸均为800×600，其中图4d的带箭头实线是块内的切割线，带箭头虚线是块间的切割线。将本文算法生成的下料方案与Cutleader及文献[19]生成的下料方案进行数据对比，如表2所示。

表2 两种算法生成的下料方案相关性能数据表

从表2的数据可知：①相较于CutLeader，本文算法材料利用率提高了2.79%，切割路径减少了24.25%；②本文算法与文献[19]生成的下料方案利用率均为99.58%，切割路径减少了5 320，减少约15.75%。而由表1可知，若使用同一个下料方案，仅使用等高块的切割方法对路径进行优化，减少的路径长度仅为9.95%。由此可知，本文算法在材料利用率相同的情况下，由于改进的布局图算法策略在考虑切割成本时会优先生成等高块，下料方案的切割路径将会得到进一步的优化。因此，本文算法和切割策略在矩形件切割下料过程中具有可行性和有效性。

3.3 多组算例实验对比分析

为了进一步验证算法和切割策略的可行性和有效性，采用文献[18]的20个基准算例进行测试，并与文献[19]及商用优化软件——仁霸板材优化企业版(http://www.renbakeji.com/)的结果进行比较。实验结果如图5所示，其中SU_R、SU_C和SU_S分别为仁霸、文献[19]和本文算法的下料方案利用率，CL_R、CL_C和CL_S分别为仁霸、文献[19]和本文下料方案的切割路径长度。

由图5可知：本文算法得到的下料方案利用率比仁霸和文献[19]总体上略有提高，分别提高了1.32%和0.16%；本文算法平均切割路径长度比仁霸和文献[19]分别减少了18 612和2 403，减少比例分别达到19.56%和3.04%。从图5三种算法实验数据对比折线图可以看出，本文算法和切割策略在提高材料利用、降低切割路径方面具有可行性和有效性。

4 结束语

本文针对多规格矩形件下料问题，以生产成本(材料成本与切割成本之和)最小为下料方案的优化目标。在SVC算法框架基础上，提出在生成单板材布局图时，以布局图综合价值(所含矩形件总价值与切割成本之差)最大作为优化目标，通过求解有界背包问题，前瞻性地考虑子板与当前考察条带拼合后的综合价值最大化。在路径优化方面，提出等高块概念并设计等高块共边切割策略。通过多组基准算例实验数据对比分析证明了本文所提算法和切割策略的可行性和有效性。3.1节的实验结果说明等高块切割规则并不受限于某种算法，而是可以作为一种策略为不同算法所调用，在此研究基础上，笔者将把本文所提出的等高块共边切割策略引入十进制灰狼算法以开展后续的研究工作。