黄秀玲，李 宸，董 浩

（南京林业大学 机械电子工程学院，南京 210037）

0 引言

目前铝合金是应用较为普遍的一类合金。铝合金型材具有低密度、高强度且可塑性强的特点，并且其导热性、导电性和抗腐蚀性都很优秀，所以广泛应用于工业，仅次于钢[1]。铝合金型材的切割问题属于一维下料问题。关于下料问题，它主要指是利用规格相同或不同的原材料，将其切割成大小不同的零件[2]，这是制造业典型的加工方式之一。在下料的过程中，对相关工序进行优化能够带来很多好处[3]。

“一维下料问题（One-dimensional Cutting-stock Problem，简称 1CSP）”[4]可以简单描述为：有不同规格的原材料，生产目标是将这些不同规格的原材料加工为所需求的不同规格的零件，在保证零件形状和尺寸满足要求的情况下，对原材料进行充分利用，最大限度地减少材料损失。对于本文的研究而言，就是建立在以下料问题求解最优的基础上展开分析。本文针对这一问题结合某门窗公司的实例对铝合金型材的切割方法进行研究，从而得出提高利用率的有效方法。

一维下料问题也是一种典型的NP（非确定多项式）问题，问题中还有原材料数量和种类限制，使得这类问题求解起来较为复杂，目前还不存在一个精确的方法用于解决这类问题。求解小规模下料问题，通常用线性规划、动态规划、分支界定法求得全局最优解[5]，而对于大规模的下料问题，通常使用一些启发式算法或者智能算法求得近似最优解。在对一维下料问题进行求解时，有很多种常见的求解问题方法。其中有数学模型，比如：常规线性整数规划模型和基于切割损失的模型；还有算法求解，比如：顺序启发式算法、遗传算法等等[6]。

1 数学模型的建立

在对铝合金型材进行切割时，由于型材的长度主要取决于工厂的标准，所以有不同长度的原材料，长度用Lk（k=1，2，…，K）表示。每种数量表示为Dk（k=1，2，…，K）。这里的零件指切割后未加工的型材，在铝合金门窗下料中即为窗框，由于有不同长度的需求，长度用li（i=1，2，…，n）表示，需要数量表示为为di（i=1，2，…，n）。对于切割完成后的剩余原材料，按照计算，已经满足切割需求，无需继续下料，称之为余料。余料中尺寸如若有可以用于下次继续下料的，可以回收使用，其他的则为废料。

对于一维下料问题通常以所用原材料数量最少，即消耗原材料总长度最少或者余料最少为目标函数。对于铝合金门窗下料的问题，结合某门窗厂实际情况，本文采用以消耗原材料总长度最少作为目标函数。

假设零件按顺序编号，零件需求的总数为d。铝合金原材料按长度顺序排列，D个铝合金型材原材料可以满足d个零件的切割需求。满足min{lk}>max{li}，k=（1，2，…，K），i=（1，2，…，n）。求解怎样下料使得用到的原材料最少，使用原材料最少的目标函数表示如下：

其中：

k表示为原材料的种类；

j表示为切割方式；

Xjk表示第k种原材料采用第j种切割方案的重复次数，Xjk≥0，且为整数。

对于铝合金型材而言，其原来的长度必须大于切割长度，除此之外，切割重复次数也必须少于原材料数目，并且在切割完成时，所得到的零件数量需满足客户需求的零件数量。约束条件表示如下：

其中：

式(2)表示原材料的切割重复次数小于等于原材料的数量。

式(3)表示产生的总零件数量等于客户需求数量。

式(4)表示单根原材料上切割长度不超过其本身长度。

2 算法求解

2.1 改进的蚁群算法

蚁群算法应用于寻优问题的基本思路简单描述为[7]：在求解相关问题最优时，将整个问题视为蚂蚁觅食路径，所以问题的解空间就对应蚂蚁走过的路径。蚁群算法在解决单目标函数优化问题时效果较好，但是解决多目标函数优化较困难[8]。因为本文是解决多规格下料的问题，所以利用启发式算法思想将多目标转换为单目标进行求解。每只蚂蚁基于信息素的概率来进行路径的选择。针对一维下料优化的相关问题，对其进行合理的编码，同时认为所有零件都有独立性，将所有下料方案模拟成蚂蚁行走所有的路径。

在具体处理时首先是从第一个零件开始，在零件消耗总长度和原材料长度十分接近但是不超过原材料长度的情况下，此时可以得到其中的一个下料方案，基于此，可以进一步计算出更多的下料方案，按照这样的方式继续进行计算可以得到这一路径上全部的零件，从而获得该路径消耗的原材料总长度、余料长度以及下料方案的数目。

step1：输入原材料和零件的信息，并对其升序排列。

step2：初始化参数。令迭代次数Nc=0，设最大迭代次数为Nmax=200，赋予参数α，β，ρ初始值，设α=1，β=1，ρ=0.2。

step3：将D个零件从1到D进行编码，相同的零件由于编码也记为不同的零件。

step4：计算候选节点集合。

step5：开始进入循环Nc=Nc+1。若满足Nc≥Nmax，则结束循环。

step6：停止计算，输出下料方案及余料。

流程图如图1所示。

图1 蚁群算法解一维下料问题流程图

2.2 遗传混合模拟退火算法

遗传混合模拟退火算法在遗传算法中引入一种代沟策略，根据适应度的值设置一个代沟值，大于这个值的保留为精英个体，不进入轮盘赌选择，将模拟退火算法使用到其余个体之中，应用Metropolis准则来判断是否被接受为新的种群，进而使得遗传算法寻优效果更好，避免了早熟问题的发生。

step1：对适应度函数进行合理设置，这里使用原材料利用率来表示：

step2：将不同零件进行合理编码，同时将原材料编号，编为类似地，将全部零件编号为中，随机选择个数字，构成不同个体的染色体编码。比如，（1，4，5，…，2）表示的是零件号为1需要通过1号原材料来切割，……，第di号零件需要从2号原材料上切割。

step3：对种群进行初始化处理，得到随机的N个个体，设N=100。

step4：计算个体适应度。

step5：根据适应度函数设置一个代沟值，因为适应度函数为材料的利用率，故本文将这个值设置为0.9，大于这个适应度值的个体不进入轮盘赌选择，直接保留为精英个体参与接下来的流程，其他的个体进行轮盘赌选择后运用模拟退火算法中的Metropolis准则，通过公式exp（-（fit（i）-fit（best）/T）计算接受概率来判断接受或拒绝。

step6：合理设置基本参数。对于交叉算子而言，使用双点交叉的方式，在染色体上随机选择两个点，两点间不变，对两端基因片段进行交叉。设置交叉率为0.8，变异算子变异率是0.1；迭代次数为1000次。模拟退火设置初始温度T=1000；退火系数设置为0.9。

step7：不断进行迭代，满足结束条件结束迭代并且将最优解输出，若不满足条件返回step4。

流程图如图2所示。

3 实例计算分析

本文所有计算的例子均在主频2.50GHz，内存为8GB的计算机上完成，通过MATLAB进行编程并设计下料软件。根据在某门窗有限公司采集的数据和实例进行分析，再根据所采集数据的规模，分别给予不同的计算和分析。

实例：仓库有铝合金原材料3200mm的30根，3600mm的30根，4000mm的20根。现在需要切割外窗框长为1390mm，宽为790mm，中柱框为735mm，内开窗框长为962mm，宽为736mm，扇压线长为837mm，270mm。扇压线宽为611mm，654mm的窗户15套。

窗户图纸如图3所示。

原材料长度如表1所示，下料尺寸表如表2所示。

图2 遗传混合模拟退火算法流程图

图3 窗户图纸

表1 原材表

表2 下料尺寸表

3.1 蚁群算法

计算结果如表3所示。

表3 蚁群算法切割方案

表3 （续）

表3 （续）

经过计算得实例的原材料利用率为91.91%，消耗了30根3200mm铝合金型材，30根3600mm铝合金型材，3根4000mm铝合金型材，总共216000mm。余料为17475mm。对于个别原材料来说还是存在余料较长的结果，可以收集继续下料。但是计算时间变长。由结果可以看到蚁群算法在计算较大规模多规格下料问题时候寻优的效果明显下降，计算时间变长。

3.2 遗传混合模拟退火算法

具体切割方案如表4所示。

表4 遗传混合模拟退火算法切割方案

表4 （续）

表4 （续）

经过计算，运用遗传混合模拟退火算法的原材料利用率为94.17%，相比蚁群算法的利用率91.91%提升了2.26%。消耗了30根3200mm铝合金型材，23根3600mm铝合金型材，8根4000mm的铝合金型材，余料为12275mm，总计210800mm。与蚁群算法消耗材料总长为216000mm进行对比，遗传混合模拟退火算法节省材料的同时提高了整体原材料利用率，且余料中没有出现余料过长的情况，遗传混合模拟退火算法具有良好的计算效果。

4 结语

本文对于一维下料问题，提出了一种遗传混合模拟退火算法，使算法寻优效果更好，避免了早熟问题的发生。结合某门窗有限公司的下料实例建立数学模型，为了使材料利用率得到有效提高，文中利用蚁群算法与遗传混合模拟退火算法对下料问题进行分析，结果表明，使用基于遗传混合模拟退火算法来提高材料的利用率具有重要的现实意义。