灰狼算法在定制化家具矩形件排样中的应用

吴正佳 李金雄 单飞祥 李子奇

（三峡大学机械与动力学院，湖北宜昌 443002）

0 引言

当前，定制化家具企业面临着订单种类和数量逐渐增加的问题，而排样是企业生产加工的首要工序，其好坏程度直接影响生产成本。定制化家具排样可理解为企业利用机械设备从一定规格的原板材中切割出组装成整套家具的矩形零件，从生产成本的角度来说，板材利用率越高，所需板材越少，成本越低。

基于此种情况，部分学者采用不同方法对矩形件排样问题展开了研究。Sanchez等人[1]将模拟退火算法和遗传算法相结合，一定程度上提高了板材利用率；罗强等人[2]提出了一种改进的十进制灰狼算法，根据排样图形状设计定位算法，求解矩形件排样问题；王莉[3]结合模拟退火算法和基于匹配度的最低水平线排样算法，求解以利用率最大化为目标的问题模型；郭文文等人[4]考虑工艺约束和机器刀缝限制，设计不同切割规则求解，以提高利用率。灰狼算法是一种群智能算法，由于其较为良好的全局搜索和局部搜索能力，受到广泛关注，目前，在聚类分析[5]、路径规划[6]、车间调度[7]等诸多领域得到应用。

本文拟基于定制化家具矩形件排样问题中零件差异性较大的特点，以板材利用率最大化为求解目标，应用改进的灰狼算法进行求解，提高板材利用率，减少板材数量消耗，降低生产成本，提高企业的经济效益。

1 数学模型

1.1 问题描述

本文以定制化家具矩形件排样问题为研究对象，排样问题是定制化家具生成的首道工序，直接影响整个订单的后续生产加工。该排样问题可描述为：将长度和宽度分别为hi和wi的待切割矩形件排布在长宽固定且为H和W的原板材上，零件的排放位置不能超出板材的边界，零件在排放的过程中不能互相重叠。针对定制化家具，采用木材作为原板材，其尺寸固定，而订单中待排零件尺寸不一，所以每张板材上排放的零件数b亦不相同，如何合理安排零件的排布顺序和位置，尽可能实现每张原板材的利用率最大化，减少废料和余料的生成，从而实现整体利用率最大化，是本文要考虑的关键问题。

1.2 模型建立

模型主要基于以下假设：

（1）排样过程中，考虑零件纹理，矩形件不能旋转90°；

（3）排样过程中，原板材的尺寸固定，数量充足。

其中，约束条件（1）表示原板材利用率最大化，Ha表示最后一张板材所使用的高度，以板材的左下角为坐标原点，（xi，yi）表示零件排入板材后零件左下角的坐标。约束条件（2）和（3）表示零件不超出原板材的边界，约束条件（4）和（5）不同时成立，表示原板材上的零件互相不重叠。

2 改进的灰狼算法

排样问题在实际求解过程中，可以分为零件的定序和定位问题。定序问题为第一步，决定零件的排布顺序，考虑运用改进的灰狼算法，并调整游走和奔袭策略，实现从全局优化到局部优化的过程；定位问题为第二步，确定待排零件序列在原板材上的排布位置，该过程考虑使用改进的最低水平线算法，适当调整零件在板材上的排布位置和顺序，实现排样利用率最大化。

2.1 改进的最低水平线定位算法

改进的最低水平线算法是一种更有效的排样定位算法，其主要思想是：找到板材上的最低水平线，判断其宽度w和当前待排零件的宽度l的大小，若w＜l，则判断下一个零件的宽度与水平线宽度的大小，找到可排零件排入，否则更新水平线序列，寻找最低水平线，继续排放零件，直到零件全部排完。

改进的最低水平线定位算法流程如下：

（1）初始化参数；

Requirement Analysis of Intelligent Editing of Academic Journal……………HU Yi(1·83)

（2）选取第i张板材，初始化水平线序列；

（3）从待排零件中选取第一个可排入零件；

（4）若step3中存在可排入零件，则排入零件，返回step3，否则进入下一步；

（5）判断此时的水平线序列是否为一条，若是，则i=i+1，返回step2，否则进入下一步；

（6）提升水平线序列，更新最低水平线，若零件未排完，则返回step3，否则结束；

（7）排样完成，输出排样结果。

2.2 灰狼定序算法

灰狼优化算法也称“狼群算法”，是基于狼群群体智能，模拟狼群捕食行为及其猎物分配方式，抽象出游走、召唤、围攻三种智能行为以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制而提出的一种新的群体智能算法。

本文将改进的灰狼定序算法与最低水平线定位算法相结合，一个在解空间中不断地搜索更优解，另一个解码计算当前利用率，每次迭代都保存最佳排样方案，不断更新迭代，直到达到最大利用率或者最大迭代次数。对算法中根据狼群行为抽象出来的游走和奔袭策略进行简单更改，尽量使游走过程中种群的差异性增大，提升全局搜索范围。在奔袭过程中，重新定义种群和头狼之间的距离，并不断让种群向头狼靠近，实现局部搜索。

（1）编码。结合矩形件排样问题，采用十进制的编码方式对零件序列进行编码，例如（1，3，5，2，4）表示在原板材上依次排入零件1、零件3、零件5、零件2和零件4。

（2）初始种群。采用十进制的编码方式对所有的待排零件进行编码，形成一个从数字1开始的连续不重复十进制整数零件序列，从而得到一个灰狼个体。按照该方式，随机生成不同的零件序列，形成初始种群。

（3）游走。即将一个灰狼中的某一个编码位向左或向右移动一个较大的距离，例如将灰狼Zi=（1，3，5，2，4）中的第一个编码位的zi1向右移动4个单位长度变为Zi′=（3，5，2，4，1）。基于企业加工情况调研，大部分零件在实际切割时有纹理要求，本文不进行旋转。定义游走策略为T（Zi，Q，s，d），表示从第i个灰狼Zi=（zi1，zi2，zi3，…，zin）的可编码位Q=（1，2，3，…，n）中选择连续的s个编码位进行位移为d的操作。在文本中，若连续的s个编码位的起始位置小于（1+n）/2，则向右位移，否则向左位移，尽可能增大游走范围，实现游走过程中的全局搜索。

（4）奔袭。即灰狼向头狼靠近的过程，用灰狼与头狼对应编码位的值不同的个数体现其距离，例如灰狼Zi=（1，3，5，2，4），头狼Z=（1，2，3，4，5），灰狼和头狼的编码位2、编码位3、编码位4和编码位5对应的数都不相同，则定义两者的距离为4。奔袭策略R（Zi，L1，L2，d）表示选择第i个灰狼Zi=（zi1，zi2，zi3，…，zin）中与头狼编码位不同的前d个编码位，用头狼中对应位置替代，例如若L1=（2，3，4，5），L2=（2，3，4，5），则R（Zi，L1，L2，1）表示用头狼Z中第2个编码位中的数将灰狼Zi中数进行替代，得到奔袭后的灰狼Zi′=（1，2，5，3，4）。

（5）解码。解码是运用改进的最低水平线算法将一串有序、不重复、代表矩形件的十进制整数序列转化为零件排布图。整个解码过程中，会对序列进行简单调整，为保证编码的有效性，该十进制整数序列不存在两个相等的数且不遗漏任何一个整数。

3 算例分析

3.1 某批次订单零件尺寸

根据某制定化企业的生产情况，选取了5个不同批次的生产订单，为满足零件排样要求，将所有订单数据按照零件尺寸、材料进行整理，表1为其中一个批次的部分订单数据信息。

表1 零件数据信息

基于订单数据信息可知，由于单个订单中零件数量一般较少，对订单零件进行排样前，会将订单按照其交货期合并到一个批次，从而减少生产过程中的切换频率，在一定程度上提高利用率，本文中每一个批次零件的材质、颜色和厚度相同，所有零件均可排布在尺寸为2 440 mm×1 220 mm 的原板材上。

3.2 实例计算

根据矩形件排样问题的数学模型，结合各批次的零件尺寸，以原板材的利用率最大化为目标进行求解。对比订单分批后的经验算法，将算法运行50次，得到不同批次的利用率及其所需板材数量，如表2所示。

表2 不同批次排样结果

在不同的排样批次中，为了较充分地比较算法的有效性，分别选取了不同零件规模的算例，零件个数从42个到196个不等，将本文中的改进灰狼算法和企业订单分批后所使用的经验算法进行比较，板材利用率均有不同程度的提升，分别提升了8.58%、5.23%、7.13%、9.36% 和7.31%，对应批次所需板材的数量分别减少2、3、1、4和4块。改进的灰狼算法较经验算法利用率有较大的提升，减少了企业生产成本，提高了企业的生产效益。

部分零件的排布情况如图1所示。

图1 部分零件排样图

4 总结与展望

本文应用改进的灰狼算法求解定制化家具矩形件排样问题，针对排样优化中的零件定序和定位问题，改进灰狼定序算法中游走、奔袭策略和最低水平线定位策略，实现从全局求解到局部求解的优化过程，并与实际的经验排样算法对比，利用率有较大程度的提升。但文中都是单个批次分别排样，未考虑整个排样过程中废料与余料再利用的情况，且文中待排零件都是已分类完成的，未考虑零件本身的尺寸情况对排样利用率的影响，以上两个方面还有待进一步研究。