蚁群算法在定制家具矩形零件排样中的应用

王洁，陶涛*，陈星艳，钱筱楠，欧阳周洲，刘忠会，冯万福

(1. 中南林业科技大学，长沙 410004；2. 欧派家居集团股份有限公司，广州 510000；3. 江苏凯蒂家居用品有限公司，邳州 221300)

当前，定制家具市场以其高效低成本的优势逐渐成为制造业发展的主流模式。但由于定制家具产品结构和外观的多样性，给企业的生产带来一定难度[1-4]。如何在满足客户个性化需求的同时提高企业的经济效益，缩短订单的交货期，高效且快速响应客户需求，是定制家具企业亟须解决的问题[5-7]。

蚁群算法是一种群体智能搜索算法，具有较强鲁棒性和全局搜索能力的特点[8]，通过正反馈机制使得搜索结果不断收敛逐步达到最优解。通过模拟自然界蚁群寻找食物的行为，根据真实的蚁群之间的信息传递及路径选择行为，通过种群行为的变换最终实现某种功能行为[9]。本研究将蚁群算法应用于定制家具矩形零件排样问题中，结合定制家具生产特点，以最大化原材料利用率为目标，基于蚁群算法搜索得到零件排样顺序，实现定制家具零件排样问题优化，以期提高定制家具企业的生产效率、降低生产成本，从而提升企业的综合竞争力。

1 矩形零件排样问题概述

1.1 矩形零件排样问题描述

板件排样，是指在一定规格的原料板材上，按照一定规则排布若干个不同尺寸规格的零件，在满足订单配套和切割要求的前提下，达到一定的优化目标[10-11]。本研究的问题具体描述如下：已知原料板材长为L，宽为W，一个批次中待切割的零件有k种，每种零件的宽为wi，长为li，每种零件数量分别为ni个(i=1,2，…，k)。最终求得一个批次订单的优化下料方案由N张原料板组成。在第j张原料板中共排放Cj个零件，零件所在的矩形命名为Rl(1

1.2 家具矩形零件排样的数学模型

家具矩形零件排样的约束条件用数学模型表示如下：

目标函数为：

(1)

式(1)为板件排样问题的目标函数，表示最大化一个批次排样原材料利用率。

2 矩形零件排样的蚁群算法设计

2.1 蚁群算法原理

蚁群算法(ant colony algorithm，ACA)是模拟蚂蚁寻找食物过程中搜索到最短路径的群体智能算法[13-14]。蚂蚁觅食时在其经过的路径上会释放一种被称为“信息素”的化学物质，蚂蚁群体中每只蚂蚁在其经过的路径上释放信息素，经过一段时间搜索之后，被众多蚂蚁多次选择的路径上信息素浓度逐渐增加，最终，所有蚂蚁都将选择信息素浓度最强的那条路径，这样整个蚁群就寻找到了从蚁穴到食物源之间的最短路径[15]。

基于蚁群算法的矩形零件的排样思路如下：将矩形零件作为蚂蚁寻找路径时经过的节点，通过蚂蚁的搜索，通过节点间概率选择，节点之间信息素的不断更新，用算法找出矩形零件排放的先后顺序和排放方式，最终形成具有最大原材料利用率的矩形零件排布顺序。

2.2 算法设计

将批次的板件集合记为X={X1,X2,…，Xi,…,Xt}，Xi是指第i个板件，该批次总共有t个板件，设系统中的蚂蚁个数为m个，各个蚂蚁根据概率依次选择板件，每个蚂蚁选择的板件的序号作为一个解，第k只蚂蚁形成的解可表示为{Xk5,Xk10，…,Xkj，…,Xk30}，其中Xk5表示的是当前迭代次数中，第k只蚂蚁第一次选择的是编号为5的板件，以此类推。

2.2.1 节点与路径选择概率

本研究将矩形零件作为蚂蚁寻找路径时经过的节点，节点信息包含矩形的长度、宽度、材料描述以及数量、纹理要求等。初始时，将m只蚂蚁放置在代表不同矩形零件的节点上，m只蚂蚁同时寻找下一个待排零件。蚂蚁k根据概率选择下一个节点构建路径，公式如下：

(2)

式中：τi(t)为t时刻零件i的信息素浓度；ηi(t)为零件i的启发信息值；α和β分别决定了信息素浓度和启发式信息对算法性能的相对重要程度；S为蚂蚁k在t时刻可选择的节点集合，对应到矩形排样问题中是指未排零件集合。

2.2.2 信息素与信息素更新机制

蚂蚁遍历节点完成之后，更新路径上的节点之间的信息素。为了减少算法计算时间，本研究只针对每一次迭代中蚂蚁的最优解即最优路径进行更新。当蚂蚁在节点i处选择节点j对应的矩形作为下一个待排样的零件，更新节点i与节点j之间的的信息素值，本研究设置信息素增量为选择次数。公式如下：

τij(t+1)=(1-ρ)*τij(t)+Δτij(t)

(3)

式中：τij(t)为t时刻Xi到Xj路径上残留的信息素量；ρ为信息素挥发系数；Δτij(t)为第t次迭代中信息素值的增量,本研究设置为当节点i选择节点j时，则Δτij(t)=1。

2.2.3 启发式信息

本研究的启发式信息考虑两个方面：节点对应的矩形零件面积和该零件的长宽比。根据定制家具的生产实际可知，在对板材进行排样时要优先排布面积较大的零件，如果优先排放小零件，后面再排放大零件时容易产生浪费。因此，本研究在对启发式信息进行定义时，要优先考虑零件的面积因素，对于面积相同的零件，要考虑选择该零件不同的长宽比可能产生的浪费。

对启发式信息的定义为：

(4)

式中：Si表示板件i的面积；ωi、li分别表示板件i的宽度和长度；p、q分别为面积的影响因子和长宽比的影响因子。

2.3 矩形零件排样问题的蚁群算法求解流程

通过以上对蚁群算法相关参数定义及取值确定，下面将介绍基于蚁群算法求解定制家具矩形零件排样问题的详细流程。

第k只蚂蚁的路径搜索步骤如下：

1)给蚂蚁k随机分配第一个零件i，编号为(±i)，表示原料板横切或纵切得到零件i。蚂蚁k访问节点i之后，更新节点对应的矩形零件的数量。

3)根据排放规则，判断该层中剩余区域能否满足未排零件的排布，如能够满足，则继续下一步。否则返回2)。

4)根据蚂蚁k选择的新节点信息，通过选择概率选择下一个节点。

5)蚂蚁选择完毕。

基于蚁群算法求解定制家具排样问题的流程如下：

1)所有待排零件进行横切和纵切的两个编号，即一个零件有两个编号。

2)设最优解数组为paiyang_best，计算启发式信息，并初始化信息素矩阵。

3)初始化参数：α、β、ρ、m、p、q、r0。

4)对每一蚂蚁

②选择第2个零件：根据已选节点i的切割方向，求得第一层剩余空间的长度和宽度。求解节点i的可选邻域Ni，根据2.2.1定义的选择概率选取零件。

③对于同一张原料板，判断节点的可选领域是否为空集，若为空集，转向下一张原料板的排样。

④判断所有零件都选择完毕，计算各板件的原材料利用率，求取平均值，作为该只蚂蚁求得的解的目标函数。

5)判断所有蚂蚁是否对所有零件都选择完毕，找出目标函数值最大的蚂蚁，将该蚂蚁搜索出的数组存入R_best。

6)对信息素进行更新。

7)是否满足迭代次数要求，若否，返回步骤4)。

8)输出目标函数值最大的数值对应的排样序列，即为蚁群算法求得的最优排样方案。

3 算法运用

3.1 某批次家具订单矩形零件

本研究选取某定制家具生产企业的3个批次家具为例，根据批次内的零件尺寸、材料信息对零件进行节点序号编排正负号编码。某批次内零件的信息如表1所示。

表1 某批次零件信息Table 1 Information of a batch of parts

3.2 算法参数确定

用MATLAB编写蚁群算法程序，对蚁群算法中的各个参数进行确定取值，根据前文对矩形零件排样问题的蚁群算法的设计，算法中的参数设置如表2所示。

表2 参数设置Table 2 Parameter setting

3.3 运行实例分析

根据前文所述步骤，本研究选取3个批次A、B、C进行排样方案示例，批次A总面积为41.86 m2，共98块板件；批次B总面积为44.52 m2，共135块板件；批次C总面积为48.37 m2，共201块板件，将各批次中的零件信息导入MATLAB软件中，通过蚁群的多次迭代搜索后，最终完成对3个批次订单的排样优化方案，节选部分批次A排样方案如图1所示。

通过蚁群的多次迭代搜索，可以计算出3个批次最终生成的排样方案原材料利用率，并与传统经验算法的原材料利用率进行比较，如表3所示。

图1 部分批决A排样方案示例Fig. 1 Sample layout plan of Batch A

本研究设定的目标函数为批次的最大原材料利用率，只有每一次迭代中原材料利用率最大的零件组合才能实现信息素更新，经过蚂蚁的多次选择零件之间的信息素浓度不断增加而零件的启发式信息固定，同一张原料板上的零件被选择在一起的概率不断增大，被多次选择的零件组合更容易出现在同一张原料板上，最终实现该批次板件利用率最大化。

表3 不同算例的排样结果Table 3 Layout results of different examples

对不同算例进行排样时，对比了A企业不同的订单数据样本聚类分批后排样的传统经验算法与本研究优化的排样算法对原材料利用率的影响，结果表明，在不同的订单样本量条件下，本研究优化的排样算法较传统经验算法原材料利用率分别提高6.1%，11.1%和10.0%。通过多次迭代能够最大利用原料板剩余尺寸，提高了原材料的利用率和企业的经济效益。

4 结 论

蚁群算法是一种结合分布式计算以及正反馈机制的智能算法，具有较强的全局搜索能力。本研究以最大化一个批次排样原材料利用率为目标对定制家具矩形零件的排样问题构建模型，将蚁群算法的结构与定制家具排样问题的实际信息结合，对蚁群算法中的信息素更新机制和启发式信息定义进行设计，将其应用于求解批次排样问题。通过多次实验分析确定了蚁群算法中各项参数值，最后通过实例验证证明该算法能够有效提高批次的原材料利用率，在定制家具生产中排样问题中求解具有有效性。