0 引言
随着大数据信息技术的快速发展,数字化制造在航空制造企业的地位日益凸显。数字化制造技术应用于产品全生命周期中,提高制造生产效率和质量,降低生产成本,实现Just-in-time市场响应目的。实现资源高效利用是数字化制造的重要课题,航空制造业中存在大量不规则零件,可靠的下料方案能够提高原坯料利用率,对提高航空类企业竞争力具有重要意义。
二维下料问题(2DCSP)在生产制造过程中应用广泛,许多学者进行了大量研究,相关的研究成果十分丰富。考虑到航空不规则零件展开件的制造过程复杂、生产周期长、原坯料利用率低,优良的下料排样技术是生产制造中的关键技术之一。马俊燕等[1]以原坯料使用量为目标,以原坯料的余料长度小于最短零件长度等为约束,提出一种基于递推矩阵的列生成算法数学模型。汤洪涛等[2]结合下料生产的实际约束,提出了一种基于加工属性的多层编码方式的改进的遗传算法,在邻域搜索阶段采用了基于禁忌表的双层协同优化策略。杜冰等[3]提出了一种基于临界多边形的混放置策略,考虑排样效果的紧密度,在优化图形的顺序时使用了自适应遗传算法,自适应地改变交叉与变异概率。陈燕等[4]提出了混合迭片价值调整公式,用动态规划的递推方法求解布局图,提出最大比值法对多规格板材的布局图进行选择。
除上述算法以外,人工蜂群算法具有参数简洁、适用性强、迭代快等特点,广泛应用于二维下料问题的求解。苏俊等[5]提出VNABC人工蜂群算法,设计2种解码策略STD和SLD,采用响应面分析法对 VNABC 进行参数标定,改进算法的操作算子。赵明等[6]构建改进维数成功历史档案,使蜂群算法能够根据优化过程适应到合适的改进维数,在跟随蜂搜索阶段,在保证维选择适度随机性的同时,提升算法的收敛能力。季雨瑄等[7]提出了一种邻域粗糙集分辨矩阵特征重要性度量方法,以邻域分辨矩阵特征重要度为基础,设计了一种人工蜂群算法优化的特征选择算法。人工蜂群算法的研究均集中在解决规则零件下料排样问题,涉及不规则零件排样问题研究鲜有提及。
本文中旨在对航空不规则零件展开件进行下料排样,基于常规蜂群算法进行改进,提出一种有效且具有实际应用价值的变邻域人工蜂群算法,采用变邻域搜索方式,实现多变量食物源编码,多规则图样解码,从而准确地表征排样零件,提高了航空不规则零件展开件排样的材料利用率。
1 航空不规则零件下料模型
航空不规则零件包含蒙皮、隔框、翼肋、导管、壁板等,部分不规则零件如图1所示。航空产品零件具有结构复杂、种类多、选材各异、批量不大等特点,使得零件成形后的性能技术要求高,加工难度大。航空不规则零件展开件定义为H1,H2,…,Hi,原坯料面积定义为S,展开件的展开面积为S1,S2,…,Si。
图1 航空不规则零件
Fig.1 Aviation irregular parts
航空不规则零件展开件下料问题描述为:第i种零件Hi展开件毛坯用Pi表示,i=1,2,…,m。第j种原坯料表示为Oj, j=1,2,…,n。如何在一定数量原坯料裁剪出规定数量的不规则展开件,使得材料利用率最高,剩余原坯料最多。在原坯料上建立二维全局坐标系,航空不规则展开件在原坯料上下料方式遵循以下规则[8]:① 毛坯在原坯料上下料时只能90°旋转;② 下料过程中从原坯料左上角开始下料,向下、向右依次展开;③ 原坯料数量、规格一定。
1.1 模型变量
以全局坐标系为基准,构建下料优化模型变量,tls为原坯料的修剪损失。在二维平面内建立2个相对坐标系X-Y,基点分别为原坯料左上角O1及右下角O-1,如图2所示。
图2 下料坐标系
Fig.2 Cutting coordinate system
其中,原坯料Oj, j=1,2,…,n,宽度为Wj,高度为Hj。展开件毛坯用Pi,i=1,2,…,m,宽度为wi,高度为hi。
展开件毛坯位置排列矩阵,如式(1)所示。
(1)
式(1)中:x1(j,i);(Oj上Pi左上角的横坐标;y1(j,i):Oj上Pi左上角的纵坐标;x-1(j,i):Oj上Pi右下角的横坐标;y-1(j,i):Oj上Pi右下角的纵坐标。∂为摆放方式,既相对于几何中心点旋转角度。
1.2 模型约束
原坯料上建立全局坐标系,宽度、高度、面积、重叠度、摆放方式等限制条件决定航空不规则展开件毛坯在原坯料上的位置[9],如图3所示。
图3 下料限制条件
Fig.3 Cutting restrictions
限制条件构成模型约束包含以下几方面:
1) 摆放方式:毛坯在原坯料上的位置坐标与其摆放方式∂相关,∂因子毛坯展开矩阵,如式(2)所示。
(2)
2) 宽度、高度:任意单个毛坯宽度及高度尺寸均小于所有原坯料宽度及高度尺寸;下料时,毛坯外形尺寸均应在原坯料的内部,不能超过原坯料的尺寸,约束如式(3)所示。
(3)
3) 面积:若k块毛坯摆放在第j原坯料上,其面积之和不能大于该原坯料的面积。约束如式(4)所示。
(4)
4) 重叠度:任意2个毛坯不能重叠摆放在同一块原坯料上进行下料。
假设有2个展开件毛坯P1和P2摆放在O1的原坯料上,毛坯P1和P2的展开矩阵,如式(5)、式(6)所示。
(5)
(6)
展开件毛坯P1和P2不重叠,则必须满足式(7)的条件:
(7)
1.3 目标函数
根据上述约束条件,建立航空不规则零件展开件下料优化布局模型,所消耗原坯料的浪费率(1-使用率)为优化目标,如式(8)、式(9)所示。
(8)
mintls=1-Us
(9)
2 基于变邻域人工蜂群算法的下料方案
Karaboga提出人工蜂群(简称:ABC)算法是一种通过模拟蜜蜂群采蜜行为的群智能算法。该算法包括1种来源:食物源。3种蜂群:引领蜂、跟随蜂及侦察蜂。ABC算法随机生成食物源位置,并分配给引领蜂,引领蜂负责采蜜和传递信息,并将食物源的信息共享;跟随蜂从引领蜂的蜜源中选取1个蜜源,并进行邻域搜寻;侦察蜂巡视所有食物源,发现新的食物源。引领蜂与侦察峰角色可以相互转换。航空不规则零件下料过程中存在种类规格多、原坯料数量大、生产混排、排样效率低等特点。原有ABC算法在特定邻域内搜索具有盲目性,采用变邻域ABC算法,以大幅提高算法的收敛速度[10-11]、排样效率及材料利用率。
航空不规则类零件展开件的下料排样算法架构包含算法层、逻辑层与优化层,如图4所示。
图4 算法架构
Fig.4 Algorithm architecture
2.1 编码操作
针对不规则零件二维下料问题,将食物源设计成4层。第1层表示展开件毛坯下料顺序;第2层表示展开件毛坯摆放角度,正数表示顺时针摆放,负数表示逆时针摆放;第3层表示毛坯与原坯料初始指派,第1层毛坯序号对应原坯料序号;第4层表示原坯料排布是否已饱和,1代表已饱和,0代表未饱和。编码操作方式如图5所示。
图5 编码操作方式
Fig.5 Encoding operation method
假设食物源中有7种毛坯,3种原坯料。其中,毛坯P1的下料顺序为第二;摆放在已饱和原坯料O3上,旋转角度为∂1。3种原坯料中仅O2未饱和。相应的食物源编码矩阵如式(10)所示。
(10)
2.2 指派策略
首件毛坯在原坯料下料加工顺序确定后,后续毛坯下料顺序由原坯料排列饱和度规则进行约束。当首件毛坯下料后,后续有多件毛坯等待下料,在符合变量约束的条件下,保证已下料原坯料优先达到饱和状态,再启用新的原坯料进行下料。若已下料原坯料无法满足后续毛坯下料要求,则可以启用新的原坯料进行下料。下料初始指派需要考虑毛坯的下料顺序、摆放位置及原坯料饱和度,是复杂的组合优化问题。
2.3 变邻域搜索策略
人工蜂群算法常用于求解连续问题,本文中采用变邻域搜索策略的改进人工蜂群算法机制,特别是用来解决在不规则零件数量的增多,下料优化计算的工作量呈指数级增加情况下,降低下料过程中邻域决策特征及组合优化的复杂度。
给定的二维下料空间X-Y中,Δ=RN×R→R,则称Δ为RN上的一个度量[12]。在给定下料空间X-Y上的毛坯有限集合P={p1,p2,…,pi}中,对∀pi的邻域δ定义,式(11)所示。
(11)
设下料过程约束属性集合为L,目标属性集合为T,邻域元素变换策略B,其中:T∈L。人工蜂群算法在引领蜂、跟随蜂及侦察蜂阶段,变邻域决策系统BLT定义,如式(12)所示。
BLT=(P,L∪T,B, f)
(12)
变邻域后下料上下限
的定义,如式(13)所示。目标属性T对邻域元素变换策略B子集b的依赖度γb(T),如式(14)所示。对∀α∈L,条件特征α的特征重要度S(α,L,T),如式(15)所示 。
(13)
(14)
S(α,L,T)=γL(T)-γL-{a}(T)
(15)
2.3.1 下料件交换策略
下料件策略是通过随机选择的2个毛坯,交换的下料位置来生成新的邻域解。以式(10)为例,随机选择毛坯件P3与P5下料位置交换,如图6所示。摆放角度、对应关系、排布状态也相应的变换,交换策略搜索后矩阵,如式(16)所示。
图6 交换策略
Fig.6 Exchange strategy
2.3.2 下料件顺序策略
下料件顺序策略是毛坯下料过程中出现所选毛坯序号相邻,则交换任意相领2个元素的位置。以式(10)为例,毛坯件P3、P4、P5下料顺序相邻,则可以分别交换P3、P4位置或P4、P5位置,如图7、图8所示。摆放角度、对应关系、排布状态也相应的变换,顺序策略搜索后矩阵,如式(17)、式(18)所示。
图7 顺序策略(1)
Fig.7 Sequential strategy (1)
图8 顺序策略(2)
Fig.8 Sequential strategy (2)
(17)
(18)
2.3.3 下料件逆序策略
下料件逆序策略是通过随机选择2个毛坯件,将所选的2个毛坯序号之间的毛坯逆序排列,从而生成新的邻域解。所选毛坯件与中间毛配件数量之和大于3,则将所选毛坯件间毛坯下料逆序排列,如图9所示;如果所选毛坯件与中间毛配件数量之和等于3,则这3个毛坯件逆序排列,如图10所示。逆序策略搜索后矩阵,如式(19)、式(20)所示。
图9 逆序策略(1)
Fig.9 Inverted strategy (1)
图10 逆序策略(2)
Fig.10 Inverted Strategy (2)
(19)
(20)
2.4 解码操作
变邻域搜索后食物源矩阵确定了每个毛坯对应的原坯料、摆放位置,算法解码流程根据原坯料是否已饱和。如果已知原坯料已使用且未饱和,则将当前毛坯下料到已知原坯料剩余空间上;若已知原坯料剩余空间不能满足下料要求,则在新的原坯料上下料[13]。
例如:式(10)中,如果毛坯P1能够在原坯料O1剩余空间下料,则P1优先在原坯料O1上下料。若原坯料O1剩余空间无法下料,P1则在新的原坯料O3上下料。
本文中提出5种下料解码方式:单坐标系优化下料(SCO)、双坐标系优化下料(DCO)、高度优化下料(HO)、宽度优化下料(WO)、角度优化下料(AO),如图11所示。不同毛坯下料可以使用单一方式或组合方式,以达到最佳解码效果。2块及以上毛坯下料在同一原坯料,需采用双坐标系优化下料(DCO)进行下料优化校核。
图11 解码方式
Fig.11 Decoding method
以P2毛坯为例,采用SOC、AO、HO下料解码方式。首先,采集P2不规则零件展开件的最大高度,寻找可以放入的已饱和或未饱和的原坯料,并以SOC确定左上方为基坐标系,调整AO角度,直到P2毛坯完成下料。如果原坯料已饱和,则结束下料P2流程,进行P1下料流程。如果原坯料未饱和,剩余空间高度小于阈值,则停止P2下料流程;剩余空间高度高于阈值,则在剩余毛坯中寻找与P2高度相似毛坯进行下料流程,重复上述下料过程,直至该原坯料饱和。
将变邻域后毛坯展开件进行解码,即根据变邻域人工蜂群算法获得的各航空不规则展开件毛坯的下料排列顺序和旋转角度,在原坯料上确定毛坯件的最终下料位置,以实现最终下料效果图,保证消耗原坯料的浪费率最低[14]。
2.5 优化下料过程
基于变邻域人工蜂群算法下料计算流程分为4个步骤,可以根据不规则零件的形状复杂程度及下料数量,对计算流程进行适当裁剪,如图12所示。
图12 优化下料计算流程
Fig.12 Optimize the cutting calculation process
步骤1：毛坯件初编码
不规则零件下料初期,设计人员需要将不规则零件展开成为二维形状,根据毛坯及原坯料数量,结合相应约束条件,生成毛坯件编码初始矩阵。矩阵中包含毛坯下料顺序、毛坯摆放角度、毛坯与原坯料对应关系及原坯料饱和程度。毛坯初编码需要考虑毛坯件在原坯料上坐标系基点。同一初始编码矩阵中,若毛坯件基点不一致,则转换到同一坐标基点,提高后续运算速率。
步骤2：指派策略
根据2.2节中指派策略原则,初始编码矩阵进行指派变换,满足原坯料的饱和度要求。变换后的初始编码矩阵在引领蜂阶段、跟随蜂阶段生成候选解,进行人工蜂群算法优化,更新生成候选解。更新候选解均需变邻域搜索。引领蜂阶段运行仿真后生成的阶段下料最优作为跟随蜂阶段的生成候选解进行优化运算。
步骤3：变邻域搜索
变邻域搜索阶段包含变化策略、顺序策略及逆序策略3种。引领蜂阶段、跟随蜂阶段生成候选解,完成变邻域搜索变换,将结果返回原流程,作为新生成候选解继续相应运算。跟随蜂阶段下料最优解,将进行解码操作。
变换后矩阵作为侦察蜂阶段的输入,进行运算仿真,确定是否进行解码。若满足解码要求,则进行解码操作;若不满足解码要求,则进行侦察蜂阶段运算仿真,生成下料最优解。侦察蜂阶段下料最优解若满足图样要求,则直接生成图样;若不满足图样要求,则进行解码操作。
步骤4：解码图样
解码图样包含SCO、DCO、HO、WO、AO 5种图样解码方式。若解码图样过程出现运算死循环,返回步骤3,重新进行变邻域搜索。图样解码保证消耗原坯料的浪费率mintls=1-Us最优。
3 仿真实例结果与分析
为验证本文中所提出变邻域人工蜂群算法在航空不规则零件下料优化问题时具有良好的求解优化性能,建立仿真下料优化模型,并选取10种不规则展开件进行仿真实验。
本文中提出的算法模型均基于C++语言平台进行编写及搭建,运行环境为Intel Core I5-12400,内存为16 G 的Windows 12电脑上运行[15],关键部分仿真代码如3.1节所示。
通过分析和对比人工蜂群算法和变邻域人工蜂群算法在航空不规则零件的排样效果(见图14和图15),获得材料浪费率低,排样时间短的最优排样结果。
3.1 仿真代码
1. for i=1 to 10
2. P
uniform(i,1,random 10)
3. ∂vlookup(P,1,Limited Angle )//寻找对应角度
4. Ovlookup(P,∂,Limited Square)//随机选择终点
5. if O=0//表示未饱和
6. if O=1//表示已饱和
7. clc,clear;
8. R=zeros(4,10)
9. …
10. //根据步骤一生成初始编码矩阵,步骤二进行指派变换
11. next
12. start_Pj
13. end_Pk
14. Define end_P-start_P=L
15. if L=2//交换所选元素
16. end
17. …
18. //根据步骤三进行变邻域搜索
19. next
20. define code R
21. define Method SCO,DCO,HO,AO,WO
22. Tz_uniform(1,1,random5)//随机选择第1种方法
23. Uz_uniform(1,1,random5)//随机选择第2种方法
24. …
25. end
26. //根据步骤4进行解码图样
27. next
28. if 满足终止条件
29. 输出解码图样
30. else
31. 返回引领蜂阶段进入下一代
32. end
3.2 算法排样结果与分析
原始排样通常会根据生产任务、下料顺序等因素,延原坯料边缘进行下料,10种航空不规则展开件原始排样,如图13所示。原始排样图中A区表示已排样展开件,A区中阴影部分为浪费原材料;B区表示未排样展开件,因排样浪费率过高,未能排样下料展开件。
图13 原始排样
Fig.13 Original layout
为了提高排样效率,减少原材料浪费率,分别采用人工蜂群算法及变邻域人工蜂群算法进行排样,排样结果如图14、图15所示。上述2种算法,10种航空不规则展开件均已在原材料上进行排样下料。
图14 人工蜂群算法排样结果
Fig.14 Layout effect of artificial bee colony algorithm
图15 变邻域人工蜂群算法排样结果
Fig.15 Layout effect of variable neighborhood artificial bee colony algorithm
根据优化下料计算流程图12,计算获得变邻域人工蜂群算与人工蜂群算法材料浪费率mintls/%和排样时间 t/s,算法迭代次数与排样时间关系如图16所示。算法迭代次数与材料浪费率关系如图17所示。排样效果数据如表1所示。
表1 算法运行数据
Table 1 Algorithm running data
变邻域人工蜂群算法mintls/%t/s人工蜂群算法mintls/%t/s结果5.217185.1217.981263.59
图16 迭代次数与排样时间关系
Fig.16 Relationship between iteration times and layout time
图17 迭代次数与材料浪费率关系
Fig.17 Relationship between iteration times and material waste rate
4 结论
1) 建立了航空不规则零件下料模型,在二维下料平面内构建双二维坐标系,为了更准确地表达不规则展开件的几何特征,以宽度、高度、摆放位置、面积及重叠度为模型约束,以原坯料浪费率最小为模型优化目标,提高了模型可靠性及构建精度。
2) 提出了基于变邻域人工蜂群算法的下料方案及算法流程,以食物源编码、指派策略、变邻域搜索、图样解码为算法框架。食物编码矩阵;变邻域搜索中交换策略、顺序策略、逆序策略;图样解码中SCO、DCO、HO、WO、AO 5种解码方式,对于提高不规则零件排样准确度,原坯料利用率具有重要意义。
3) 分别采用人工蜂群算法和变邻域人工蜂群算法对航空不规则零件10个展开件进行排样。 通过算法对比分析,变邻域人工蜂群算法较人工蜂群算法的图样排样原坯料利用率提高了约12.7%、排样效率提高了约29.7%。
[1] 马俊燕,韩志会,骆德铖,等.递推矩阵的列生成算法下的一维下料方案研究[J].机械设计与制造,2022(1):117-119.MA Junyan,HAN Zhihui,LUO Decheng,et al.Research on one-dimensional cutting stock problem based on recursive matrix column generation algorithm[J].Machinery Design &Manufacture,2022(1):117-119.
[2] 汤洪涛,郑之恒,李英德,等.采用AGV分拣的型材下料车间成组调度问题研究[J].计算机集成制造系统,2023,29(1):100-110.TANG Hongtao,ZHENG Zhiheng,LI Yingde,et al.Group scheduling problem of profile cutting workshop using AGV sorting[J].Computer Integrated Manufacturing Systems,2023,29(1):100-110.
[3] 杜冰,郭晓强,方杰,等.二维不规则图形排样问题的一种混合求解算法[J].锻压技术,2022,47(3):39-45.DU Bing,GUO Xiaoqiang,FANG Jie,et al.A hybrid solving algorithm on two-dimensional irregular graphics nesting problem[J].Forging &Stamping Technology,2022,47(3):39-45.
[4] 陈燕,郑欣亮,鲁淑飞,等.考虑切割成本的矩形件优化下料算法[J].计算机集成制造系统,2022,28(12):3859-3868.CHEN Yan,ZHENG Xinliang,LU Shufei,et al.Optimization algorithm for rectangular parts cutting stock problem with cutting cost[J].Computer Integrated Manufacturing Systems,2022,28(12):3859-3868.
[5] 苏俊,徐震浩,顾幸生.基于VNABC的多规格板材二维下料问题[J].华东理工大学学报(自然科学版),2023,49(5):712-723.SU Jun,XU Zhenhao,GU Xingsheng.Two-dimensional cutting stock problem of multi-specification plates based on VNABC[J].Journal of East China University of Science and Technology(Natural Science Edition),2023,49(5):712-723.
[6] 赵明,焦剑如,宋晓宇,等.维适应人工蜂群算法的研究[J/OL].小型微型计算机系统:1-9[2023-04-07].ZHAO Ming,JIAO Jianru,SONG Xiaoyu,et al.Research on dimension-adaption artificial bee colony algorithm[J/OL].Journal of Chinese Computer Systems:1-9[2023-04-07].
[7] 季雨瑄,叶军,杨震宇,等.一种人工蜂群算法优化的邻域粗糙集特征选择方法[J].郑州大学学报(理学版),2023,55(6):55-62,70.JI Yuxuan,YE Jun,YANG Zhenyu,et al.Attribute selection method based on artificial bee colony algorithm and neighborhood resolution matrix optimization[J].Journal of Zhengzhou University(Natural Science Edition),2023,55(6):55-62,70.
[8] SUPPHAKORN S,INTIYOT B,JEENANUNTA C.A column generation on two-dimensional cutting stock problem with fixed-size usable leftover and multiple stock sizes[J].International Journal of Logistics Systems and Management,2020,35(2):273-288.
[9] CLAUTIAUX F,SADYKOV R,VANDERBECK F,et al.Pattern-based diving heuristics for a two-dimensional guillotinecutting-stockproblem with leftovers[J].EUROJournal on Computational Optimization,2019,7(3):265-297.
[10] LIU C H,HE Q.Adaptive artificial bee colonyslime mold algorithm with improved DNR ossover operator[J].Journal of Chinese Computer Systems,2023,44(2):263-268.
[11] TAO X R,PAN Q K,GAO L.An efficient self-adaptive artificial bee colony algorithm for the distributed resource-constrained hybrid flow shop problem[J].Computers &Industrial Engineering,2022,169:108200.
[12] DIOS M,FERNANDEZ V,FRAMINAN J M.Efficient heuristics for the hybridflow shop scheduling problem with missing operations[J].Computers &Industrial Engineering,2018,115:88-99.
[13] LI Y L,LI F,PAN Q,et al.An artificial bee colony algorithm for the distributed hybrid flow shop scheduling problem[J].Procedia Manufacturing,2019,39:1158-1166.
[14] LIU J,LIU J,Yan X,et al.A heuristic algorithm combining Pareto optimization and niche technology for multi-objective unequal area facility layout problem[J].Engineering Applications of Artificial Intelligence,2020,89(Mar.):103453.1-103453.12.
[15] GAO W F.Enhanced artificial bee colony algorithm through differential evolution[J].Applied Soft Computing,2016,48:137-150.