智能制造环境下考虑可加工性的矩形件下料方案优化

陈 燕，鲁淑飞，胡小春，孙 宇，黄晓冬

(1.广西大学 计算机与电子信息学院广西多媒体通信与网络技术重点实验室，广西 南宁 530004；2.广西财经学院 信息与统计学院，广西 南宁 530003;3.广西大学 机械工程学院，广西 南宁 530004)

0 引言

近年随着现代通信、计算、网络和控制技术的发展，智能制造在制造企业生产中的重要作用日益突显[1]。与此同时，制造业的劳动力成本也在不断攀升，生产企业为了降低生产成本、提高生产效率和精细化，势必会大量使用制造机器人、机械手。信息化与自动化结合的物联制造和制造清单自动付诸于制造执行等各种需求更加迫切。因此，适合智能制造的切割工艺如减少火焰切割、激光切割等是制造业未来的应用趋势，而制定面向可加工性的下料方案是实现智能制造的前提和基础[2]。

下料问题(Cutting Stock Problem, CSP)是国际上一个重要研究领域，相关的理论研究和实践应用十分丰富[3-4]。然而，下料问题的涉及面非常广，而且是具有NP难度的组合优化问题[5]，因此面向不同应用的下料问题需要设计具体的求解方法[6]。下料优化排样方法可提高原材料的利用率，路径优化可缩短切割加工的路径，这对矩形件的生产加工具有重大的实用价值[7]。目前，很多研究已经从单纯的提高材料利用率转向多目标优化、切割操作简化和面向可加工性发展，使下料方案更符合实际生产需要。文献[8]的研究目标是尽量减少材料成本和设置的数量，使用整数规划方法进行求解；文献[9-10]主要从减少排样方式数量的方面研究，考虑减少设备重置费用；文献[11]从减少切割刀数考虑来减少切割成本；文献[12]主要研究减少下料过程中需要存放毛坯的堆数，以减少生产需要的临时存储空间；文献[13]阐述下料问题应综合考虑下料工艺、切割成本、生产效率等因素，在保证较高利用率的同时具有良好的可加工性;文献[14]提出一种支持一刀切工艺约束的多规格板材组合的构造算法，依据工件的总面积形成多种可行的板材组合，采用组化策略和启发式的排样规则并用启发式方法求解;文献[12]利用同质条带组合构造成块T型块，在满足一刀切的工艺约束前提下提高材料利用率;文献[14-15]分别利用同质条带的共边切割，提出面向可加工的矩形件下料方法，综合考虑材料利用率和切割成本的优化，其中文献[14]使用主从目标的优化模型，首先以材料最大利用率作优化目标，利用连续启发式方法寻求最优布局图，再用条带共边切割的路径优化方法设计切割路径；文献[15]将综合考虑材料成本和切割成本，以最大价值寻求最优布局图，使用顺序价值校正(Sequential Value Correction, SVC)框架多次迭代获得多个可行的下料方案，并从中选择综合成本最小的方案。

已有的考虑可加工性的矩形件下料问题研究中，在切割路径优化策略上只考虑毛坯或条带的共边切割，忽略了相同条带所组成的同质块的共边特性，不能充分挖掘块共边切割的潜能。而且大部分研究都是先考虑材料的最大利用，其他可加工性等约束只作为辅助优化目标，不利于综合成本最小的整体优化。因此，本文首先提出考虑材料成本和切割成本综合最小的多目标规划问题(Multi-Objective Programming, MOP)模型。在此基础上，提出同质块的共边切割策略，根据同质条带有无余料、条带所含毛坯数的奇偶性设计板材的切割路径，以减少切割成本。设计生成布局图的前瞻法时，不仅要考虑当前条带利用率，还要考虑布局当前条带后板材的整体利用率，以减少材料成本。切割成本与材料成本的减少相互并不冲突，但如果生成布局图的启发式方法不当，很难在有限时间内寻找到近似最优的解。本文通过前瞻法判断每块拼入的毛坯对利用率的影响、拼入的条带对切割成本的影响，每次选取放置的毛坯都优先考虑组成同质块。实验数据证明，所提方法实现了综合成本最小的Pareto改进，在保证材料利用率较高的基础上减少了切割的路径。

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 毛坯和条带的布局

将矩形件(或矩形毛坯)布局在规则板材上，毛坯的布局不能超过板材的边界，毛坯之间不允许重叠。毛坯可旋转90度放置，即可水平放置和垂直放置两种方式。本文采用同质条带的布局方式，即条带内毛坯相同、放置的方向亦相同。可用X和Y标记毛坯和条带的放置方向，用T=(t1t2)表示条带，其中：t1表示条带方向，t1={X,Y};t2表示毛坯的方向,t2={X,Y}。因此，有T={XX,XY,YX,YY}四种条带类型，具体信息如表1所示。其中一种毛坯的同质条带在长、宽分别为L和W的板材上的4种布局方式如图1所示，阴影部分为余料。

表1 条带类型信息表

1.3 条带优选方法

由于本文使用的是有约束的排样方式，每次放置条带时必须考虑当前的剩余毛坯需求。m种毛坯的基本信息为可用元组(i,li,wi,ri,vi)表示，其中vi和ri分别为第i种毛坯的价值和剩余需求。利用条带的产出率对条带进行优选，条带的产生率=条带所含有效毛坯总价值/条带面积。所谓有效的毛坯是指条带布局的毛坯数量不能超过当前的剩余毛坯的需求数量。

分别用XXi、XYi、YXi和YYi表示第i种毛坯对应的4种条带类型，用O(XXi)、O(XYi)、O(YXi)和O(YYi)分别表示第i种毛坯对应4种条带的产出率，其值分别为：

O(XXi)=(vi×min(ri,⌊L/li⌋)/(L×wi)，

O(XYi)=vi×min(ri,⌊L/wi⌋)/(L×li)),

O(YXi)=(vi×min(ri,⌊W/wi⌋)/(W×li)，

O(YYi)=vi×min(ri,⌊W/li⌋)/(W×wi))。

其中：L和W分别表示待排样板材的长和宽;⌊L/li⌋、⌊L/wi⌋、⌊W/wi⌋和⌊W/li⌋分别表示上述4处条带所含的毛坯个数。当遍历共m种毛坯时，最多的可行条带数为4m根。

1.4 布局图生成方法

最优布局图是指根据当前需求的毛坯，寻求在给定板材上合理的放置方式，使布局图的综合价值最大。假设板材的长宽分别为L和W，用F(L,W)表示该板材上的综合价值，则最优布局图的模型可表示为：

(5)

式中：qi为第i(i=1,…,m)种毛坯布局图放置的个数;ri为第i种毛坯的剩余需求量;ci为第i种毛坯的价值。该问题是有约束的二维背包问题，具有NP难度，可用具有分支遍历的前瞻法求解。板材上放置一根条带后，整板面积会划分为放置条带面积与剩余板材面积两部分；然后将剩余板材面积作为母板再次进行布局，直至板材不能布局任何下一根条带或已经满足所有毛坯需求。布局图生成算法思想如图2所示，其中虚线箭头表示递归算法的回推过程。

1.5 下料方案求解方法

SVC框架技术相对成熟，已在多种下料问题中获得成功的应用[9，12]。SVC是基于价值校正的顺序启发式算法，经过多次毛坯价值校正和生成多个方案后，可从中选择综合成本最小的下料方案。生成下料方案的算法如下：

输入：毛坯的初始需求(ri,li,wi)和板材供应(Dj,Lj,Wj)，其中i=1,…,m，j=1,…,n。

步骤1令G=1，Gmax=100作为最高迭代次数，令毛坯初始价值为毛坯的面积vi=li×wi，令最佳下料方案的总成本Zbest=+∞。

步骤2令剩余毛坯需求量等于初始毛坯需求量ri=di。

步骤3令j=1，最佳布局图的利用率为0，使用步骤3.1～步骤3.5生成最优布局图。

步骤3.1：令当前剩余毛坯需求bi=ri。若Dj≤0，则转步骤3.5；否则针对每种剩余毛坯考察在当前板材上的4种可能的布局。板材布局条带的总产出率U(L,W)等于确定放置的第一根条带的产出率与剩余子板材(x,y)所布局条带的总产出率O。令已确定条带所含毛坯个数为ni，更新当前剩余的毛坯需求，令bi=bi-ni。

步骤3.2：根据当前剩余的毛坯需求和子板材的尺寸(x,y)，考察每种剩余毛坯在子板材上的4种布局，U(x,y)等于放置的第二根条带产出率与剩下的子板材的条带总产出率。更新当前剩余的毛坯需求，令bi=bi-ni。

步骤3.3：若剩下的子板材还可以再放置毛坯，且还有剩余的毛坯需求，即bi>0，则转步骤3.2；否则剩余子板材不能再放置毛坯或已满足所有毛坯需求，转步骤3.4。

步骤3.5：若j

步骤4根据f=min{ri/zi|zi>0∧i∈{1,…,m}}确定本次所得布局图使用次数，将当前布局图加入当前的下料方案。更新剩余的毛坯需求数，ri=ri-zi，其中zi为当前布局图所含第i种毛坯的总数，更新板材的可用数量，令Dj=Dj-f。

步骤5若剩余的毛坯需求ri>0，调整毛坯的价值。

步骤6若还有剩余需求的毛坯，则转步骤3；否则根据式(1)计算当前下料方案的Z，并记录当前最好的下料方案。

步骤7令G=G+1，如果G≤Gmax，转步骤2。

输出：最好的下料方案。

因为每次迭代结束就得到一种下料方案，所以通过毛坯的价值调整，可生成多样化的布局图和多样性的下料方案。当整个算法结束时，已经考察了Gmax个下料方案，G为当前迭代次数。

2 路径优化计算方法

2.1 块切割路径优化方法

板材切割即按布局图切割出板材上所布局的矩形件，采用有效可行的切割路径优化设计对缩短零件生产周期、提高生产效益具有重要意义。针对板材切割路径的优化，文献[14]利用条带中毛坯的共边布局设计条带共边切割策略，即条带内采用“之”字型切割分离毛坯，条带间采用“直线型”分离，以条带为单位进行板材的切割。在此基础上，本文提出同质块概念以及基于同质块的共边切割方法，不仅考虑毛坯间的共边布局，还考虑条带间的共边布局，可进一步缩短空刀行程，降低切割成本，提高加工效率。下面将介绍同质块概念及其共边切割规则。

同质块是由长度和方向均相同、相邻且有共边的同质条带组成的矩形区域。如图3所示的布局图共有7块同质块，图形边上标弧线的数字为块数，条带内的数字表示该条带所布局的毛坯号数。该图共包含4种毛坯，可组成4种同质条带。例如：3号同质块由3根2号毛坯布局的同质XX型条带组成。值得注意的是，图中块1与块7均为4号毛坯组成的同种类型的同质条带，但在板材上的布局条带不同，而且区域不相邻、长度不相同，因此是两个不同的块。同理，块3与块5也是不同的块。由以上描述可知，块包含了条带，当块内只有一根条带组成时，块就简化成了条带，即同质条带是同质块的特例。

由于板材上条带布局后存在有余料生成和无余料生成两种情况，而条带的布局存在垂直和水平两个方向，同时条带中所含的矩形件个数也有奇偶之分，因此排样方式中所布局的同质条带块根据其是否有余料生成、所含条带布局方向以及条带所含矩形件个数的奇偶性可以分为8种类型的同质条带块。而根据同质块类型的不同，其切割规则也不尽相同，具体分类以及切割路径规则如图4所示。

切割路径的走向与块切割起点的选择有关。现实情况中，无论是火焰切割还是激光切割，通常默认从板材的左上角开始；后续块的起点根据与前一块的切割结束点之间的最短空程来选择，每个块的4个顶点均可作为切割的起点。以左上角作切割起始点为例，如图5所示为8种类型块的切割路径走向示意图。

2.2 整板切割路径优化方法

在同质块切割路径优化设计完成的基础上，合理安排布局图中同质块的切割次序，能够有效地减少板材切割时同质块之间的空刀行程，从而降低切割板材的成本、提高切割板材的效率。由于同质块具有4个可切入点，在一个同质块切割完毕后，选择具有最短空刀行程距离切割点的同质块进行切割，依次循环直至完成整个板材的切割。如图6所示为一个布局图的整块板材切割的路径示意图，图6a为板材的布局图，图6b为切割过程中走刀的路线图。图中实线箭头为同质块内部毛坯的切割路径与方向，虚线箭头表示同质块间的切割路径与方向。实际操作过程中只要按照上述路径走刀，即可完全把毛坯分离出来，完成下料过程。

3 实验结果与分析

实验算法用C#编程实现，研究环境为Intel Core i5-4590 CPU，3.3 GHz主频，4 GB内存。算法设置参数Gmax=100，λ=7。先在单一基准算例上将文献[14]的方法(简写为WU)和文献[15]的方法(简写为LU)应用块切割策略进行路径优化计算对比分析；然后在多组随机基准算例上用本文方法(简写为SV)进行实验测试，主要从材料利用率和切割路径长度两方面与LU方法进行对比分析。

3.1 单一算例实验对比分析

下面与文献[14-15]采用相同的基准算例进行测试，分别采用两种不同的切割策略，分析对切割路径长度的影响。先用块切割策略对WU与LU下料方案的切割路径进行优化，结果如表2所示。表中：PID表示4种方法的代号;WT和WS表示WU方法分别用条带切割和块切割;LT和LS表示

LU方法分别用条带切割和块切割；P和PL表示每种算法生成的最优布局图序号及其切割路径长度；SL表示下料方案总的切割路径长度，ΔL和Δ/%表示每种方法使用块切割与条带切割的路径长度的实际差值和优化的百分比。表2中WT和LT的数据分别从文献[14]和文献[15]复制而来，WS和LS的数据是使用本文方法求解，并使用块切割策略对切割路径进行优化的结果。

由表2可看出，WS比WT减少了5 200的切割路径，优化的百分比是14.2%(=(5 200/36 660)×100%)；LS比LT减少了2 400的切割路径，优化的百分比是6.63%(=(2400/36180)×100%)。从这两个算例的结果来看，使用块切割策略的路径优化减少平均约为10.41%(=(14.18%+6.63%)/2)，已经超过了10%，优化效果非常明显。由此可知：块切割比条带切割的优化较为明显，可在保持材料利用率不变的基础上进一步减少切割成本。

表2 切割路径的比较

3.2 多组算例实验对比分析

用文献[15]的20个基准算例进行测试，每个算例都有20种毛坯需求，每种毛坯的长和宽取值范围是[50，450]、需求量取值范围是[1,10]。上述取值均服从随机的正态分布，且均为整数。供使用的板材有5种，尺寸分别为1 400×700、1 700×850、2 000×1 000、2 800×1 400和4 000×2 000。

分别用本文方法SV与文献[15]的LU方法求解，其下料方案的利用率和切割路径长度结果如表3所示。表中：U_LU和U_SV分别为LU和SV算法求解的利用率，L_LU和L_SV分别为LU和SV算法求解的切割路径长度，ΔU=U_SV-U_LU，ΔU=U_SV-U_LU；Avg.表示各项的平均值。由表3可知：针对每一个算例，与LU相比SV求解的切割路径都更短，其平均切割长度降低了5.15%，从而充分说明本文应用的块切割策略比文献[15]应用的条带切割更优。SV与LU相比，利用率并没有降低，其中6组还略有提高，从平均数看提高了约0.16%。通过多组随机算例的测试可充分说明，本文提出的块切割是用条带切割，而后者是用块切割，因此只影响了切割成本。

表3 多组算例的测试结果

续表3

3.3 多目标优化的Pareto改进分析

通过实验测试结果证明，本文所提方法可实现Pareto改进(Pareto Improvement)，即在保证材料利用率、不增加废料的前提下，使切割路径长度大幅度降低。分别从单一算例和多组算例的路径长度和利用率角度分析Pareto的改进，如图7所示。从图7a可看出，在单一算例测试中，4种算法均获得最优的材料利用率，与WU与LU相比，本文提出的方法对减少切割路径长度有明显的效果；由图7b可以看出，在多组随机算例测试中，SV的Pareto改进程度更大。

4 结束语

本文研究了多规格、大批量的矩形件切割路径优化问题，创新之处在于提出了以材料成本和切割成本综合最小的多目标规划模型；生成单张板材的布局图时，设计了同质块的共边切割策略，允许毛坯可转向布局，考察了4种类型的条带组合，利用条带的产出率对考察的条带进行优选，使条带的利用率最大化；在生成整板布局时前瞻性地考虑了子板与当前考察条带拼合后的综合价值最大化，设计并实现了综合成本最小化的Pareto改进的路径和方法。通过多组基准算例测试，证实了所提方法的有效性和实用性，该方法同时实现了多目标优化的Pareto改进。未来将在此研究基础上，针对二维异形件的切割加工路径优化设计方法开展后续的研究工作。