摘 要 为高效解决实际生产制造中的二维不规则多边形排样问题,提出一种设计知识驱动的启发式算法.利用临界多边形判定多边形之间的相对位置,并建立局部适应度数学模型用于衡量多边形的贴合程度;根据设计知识建立数学模型来评价多边形待摆放位置,利用基于局部搜索的贪心算法完成排样. 通过对国际通用基准用例进行实验测试并与现有智能优化算法进行对比,证明了所提算法在排样质量与时间性能上不但具有一定优势,而且稳定性高。通过实际生产中样片数据的实验测试证明了所提算法的实用性。
关键词:不规则多边形排样,不规则排样问题 ;临界多边形 ;知识驱动 ;启发式算法
作者 冯毅雄1,2 ,钟锐锐1,2 ,张志峰1,2+ ,黄 城1,2 ,李中凯1,3 ,胡炳涛1,2 ,洪兆溪1,2 ,谭建荣1,2
(1. 浙江大学 流体动力与机电系统国家重点实验室 ,浙江杭州 310027;
2. 浙江大学 设计工程及数字孪生浙江省工程研究中心 ,浙江 杭州 310027;
3. 中国矿业大学 机电工程学院 ,江苏徐州 221116)
中图分类号:TP391 文献标识码:A
近年来,随着信息化技术的高速发展 ,数字化、智能化、网络化等前沿技术广泛应用于制造行业 ,智能制造技术推动着现代制造业走向全新的发展阶段[1-2] 。不规则多边形排样是现代智能制造中的一项关键技术,这是一种常见的布局优化问题,排样要求将一定数量的多边形对象按照一定的摆放规则约束全部放到一个纵向距离固定、横向距离不定的区域中,摆放结果要求纵向填满 ,横向尽量缩短 ,而且所有多边形之间没有重叠或从容器中突出 。不规则多边形排样问题在机械制造业的许多领域均有重要应用,例如家居沙发、纺织服装、汽车内饰、气模复合 材料、钣金加工等行业都需要处理排样问题 。在这类机械制造行业中 ,原材料通常以卷的形式提供 ,排样问题更有效的解决方案可以产生显著的经济和环境效益 ,尤其在纺织行业 , 经济效益提升得更加突出 ,当前纺织行业布匹原材料成本占 40%左右 , 因此不规则多边形排样问题是一个重要的研究领域。
通常,计算机自动生成多边形布局方案比人工手动排样能够获得更加优异的面料利用率,然而不规则多边形排样问题属于NP难[3]问题,大规模多边形样片可能无法在有限时间范围内获得最佳布局,目前最为广泛的研究思路是将不规则多边形排样问题细化为不规则多边形摆放策略问题与不规则多边形摆放顺序优化问题,分而治之后获取不规则多边形的最终排样方案。
不规则多边形摆放策略问题需要确保不规则多边形的摆放位置符合规范,不规则多边形之间不允许发生碰撞并需要摆放在矩形板材内部 。针对不规则多边形的几何特征复杂这一特点,部分学者采用简化不规则轮廓的方式降低碰撞检测和轮廓定位的计算复杂度[4-7],虽然能够有效降低计算复杂度 ,但是在实际应用过程中会受计算机硬件性能影响且产生浪费,存在一定局限性 。
因此,BURKE等[8]提出一种高效且稳定的临界多边形 (No-Fit Polygon,NFP)求解算法来获取各种复杂形状裁片的NFP轮廓 ;
周鑫等[9]一种改进轨迹线法应用于求解NFP;
刘玲玲等[10] 提出一种左下临界多边形(Bot- tom-Left-No-FitPolygon, BL-NFP) 定位规则 , 能够有效利用裁片中的孔洞;
GUO等[11] 提出一种基于几何相似性特征搜索和2D自由格式布局的模糊匹配方法，能够有效提高填充率;
饶运清等[12] 提出一种基于无碰撞区域的混合启发式定位规则,综合考虑了不规则裁片之间的重合率、左下 (Bottom- Left, BL)定位规则以及无碰撞区域可能出现的特殊情况 ,通过板材动态边界搜索有效解决了超边界约束条件下的排样问题。
不规则多边形排样问题的另一难点在于如何求解出最优的摆放顺序 ,高质量的摆放顺序能够显著提升最终布局方案的排样利用率 。目前多采用启发式算法结合智能优化算法来解决不规则排样问题 , 并且往往结合多种智能优化算法 ,或者对原有智能 优化算法进行改进 ,使其更适合解决不规则排样问题 。
MUNDIM等[13] 利用偏随机键遗传算法完善交叉变异机制 ,对不规则裁片排样顺序进行迭代优化 , 获得了更高质量的布局方案;
王静静等[14] 对遗传算法进行改进来求解不规则排样问题,算法收敛速度较快且具有优异的全局寻优能力 ;
杨卫波等[15] 提出基于改进实数编码的量子进化算法来确定不规则裁片的排样顺序和摆放旋转角度;
RAO等[16] 提出结合波束搜索与禁忌搜索的混合算法,能够在短时间内求解出高质量的布局方案 ;
高勃等[17] 提出基于蚁群学习的排样顺序优化方法,能够有效满足实际生产需求。
综上所述,针对不规则多边形摆放策略问题一般采用 BL策略、左下填充(Bottom-Left-Fill,BLF)策略和重心 NFP策略等,这类策略虽然简单高效,应用比较广泛,但是仅考虑待摆放多边形自身特性去确定最佳的摆放位置 ,没有考虑待摆放多边形与其他多边形之间的贴合情况 ,容易错过更优解。解决不规则多边形摆放顺序问题一般采用智能优化算法,智能优化算法能够有效提升排样利用率 ,但是缺点很明显 :①计算复杂度较高, 意味着迭代次数更多,算法所需要的时间也更多;②由于智能优化算法的优化过程存在随机因素 ,导致算法稳定性不高,文献中常通过计算平均利用率来衡量算法的稳定性。然而,实际生产过程中往往要求在短时间内获取排样结果,并要求算法稳定性较高。
本文针对实际生产环境的需求 ,提出一种设计知识驱动的启发式算法(Design-Knowledge-Driven Algorithm,DKDA)来解决排样问题,这种启发式算法不仅能够确定多边形的摆放策略 ,还能用简单而高效的策略调整多边形的摆放顺序,以达到优化排样效果的目的 ,并且算法整体所需排样时间少于智能优化算法 ,更适合实际生产环境。通过求解欧洲切割与布局特殊兴趣研究组织(EURO Special In- terestgroup on Cutting and Packing, ESICUP)提供的基准测试用例并与几种有效的智能优化算法的测试结果进行对比，验证了算法具有良好的排样效果,同时利用实际生产中的样片数据进行实验测试,证明算法具有实际生产应用价值。
查看全文：