郭欣哲 王浩洋 刘峥 孙学峰 施金豆 李明壮

摘 要：在钢材制造业中，针对钢材切割下料的问题，提高原材料利用率是各个企业迫切需要解决的问题。本文通过对几种版式不同的原材料进行切割，通过将其规整为1.5维问题，结合充分的线性约束，结合遗传算法与蚁群算法的新式算法，建立数学模型，计算出最优的排样方案，节省原材料，使其在理论价值和生活实际中具有重要作用，提高企业经济效益。

关键词：二维切割问题  调度策略NP  动态规划  线性约束  新式启发算法

中图分类号：TG50                          文献标识码：A                  文章编号：1674-098X（2021）05（c）-0061-06

The problem of steel cutting in the steel manufacturing industry

GUO Xinzhe  WANG Haoyang  LIU Zheng  SUN Xuefeng  SHI Jindou  LI Mingzhuang

（Shenyang University of Aeronautics and Astronautics， Shenyang， Liaoning  Province， 110000  China）

Abstract： In the steel manufacturing industry， aiming at the problem of steel cutting and blanking， improving the utilization rate of raw materials is an urgent problem to be solved by various enterprises. In this paper， several raw materials with different formats are cut， which are regularized into 1.5-dimensional problems， combined with sufficient linear constraints， combined with the new algorithm of genetic algorithm and ant colony algorithm， a mathematical model is established to calculate the optimal layout scheme， save raw materials， make it play an important role in theoretical value and life practice， and improve the economic benefits of enterprises.

Key Words： Two-dimensional cutting problem; Scheduling strategy NP; Dynamic programming; Linear constraint; New heuristic algorithm

隨着社会生产力的不断提高，生产规模不断扩大，钢材的原材料消耗量也随之增加，但是由于钢材价格的上涨，导致企业生产成本大幅上升，由此综合利润极剧下降，一些企业甚至出现亏损等情况。为了减轻企业压力，当务之急是在钢材切割下料生产环节有效提高钢材利用率，节省钢材，降低产品的生产成本。本文阐述的钢结构产品排样系统通过算法构建了一个排样效率高、计算速度快和排样效果好的方法，充分地提高了钢材的利用率，减少余料剩余及废料的数量，大大提高了企业的生产力与效益。

1  问题分析

1.1 问题回顾

某钢材生产制造商的钢材切割流程。其中开卷上料环节将原材料钢卷放在开卷机上，展开、放平送至右侧操作区域剪切过程在剪切台上完成，剪切台上依次有切头剪和圆盘剪。

工厂未来一批订单需求已给出，订单需求数量必须恰好满足（不允许超额供应）。根据工厂现有原料切割订单，每种原料的使用数目不能超过其库存，如表1、表2所示。

1.2 初步分析

本文研究的主要问题就是二维板材切割问题，其中夹杂着众多约束。如表1所示，对于原料下料问题首先要确实采用那些合理的模式[1]。本题要求不允许超额供应，即为线性等式约束。其次根据题目要求的变量，将其数据化处理：排刀走刀限制、原料限制、余料限制等。可以将产品的长设为l，宽设为W，原料的长为L，宽为W，在研究面积的同时，把长度和宽度也作为两个维度放入问题进行研究。但因为面积与长宽有乘积关系，所以可以近似看成2.5个维度。运用数学思想，找出每一个问题的所求函数关系，然后根据约束条件，分别添加到不同的问题中，主要运用遗传算法，设置合理的参数进行模拟仿真下料，然后求解。

1.3 符号变量选取

符号变量如表3所示。

1.4 维切割模型的假设与建立

（1）假设切割过程无操作失误导致原料浪费。

（2）假设无追加订单。

（3）假设切割的钢材全为合格品。

2  数学模型

2.1 问题分析

一共有10种原料，在本问题中，考虑5种订单。使用最少的原材料，将这些订单合理排布在原料钢材上，将问题数据化。

（1）目标函数：总原材料最少。

（2）适度函数：总的成材率最高。

（3）决策变量：使用的材料序号，不同订单的序号，材料数目，订单数目。

（4）约束条件：满足板料的需求量（不能超额供应），材料库存，排刀上限，余量标准。

2.2 蚁群算法和遗传算法融合模型

遗传算法是通过数学思维对达尔文生物进化论中的自然选择和遗传思想进行模拟的进化过程推演，是一种通过将自然进化的转置到计算机上的过程搜索最优解的方法。该算法通过数学的方式，利用计算机模拟运算，将问题求解过程转化为类似于生物进化中染色体基因交叉变异的过程。在求解复杂的组合优化问题时，与一些传统的优化算法相比，通常可以快速获得更好的优化结果。

遗传算法的基本运算过程如下。

（1）重置：设置进化解析几何电子计数器t=0，设置更大的进化解析几何T，随机生成M个个体作为原始种群P（0）。

（2）个体评论：计算组P（t）中每个个体的相关性。

（3）选择计算：选择算法应用于组。选择的目的是将上升个体的基因立即遗传给下一代或基于匹配交叉使新个体遗传到下一代。选择的实际操作是建立对群体中个体相关性的基本评估。

（4）交叉计算：交叉算法应用于种群。进化算法中的主导作用是交叉算法。

（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P（t）经过选择、交叉、变异运算之后得到下一代群体P（t+1）。

（6）终止条件判断：若t=T，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

蚁群算法是一种用于寻找提升路径的概率优化算法。这类优化算法具有普适计算、信息内容反馈调整和启发式搜索的特点，它本质上是进化算法中的研究型全局蚁群算法。将粒子群算法应用于优化问题的理论基础是：蚂蚁的行走路径用于表示待优化问题的可行解，所有蚂蚁群的所有路径构成了该室内空间。有待优化的问题。路径较短的蚂蚁会释放大量的引诱剂。随着时间的推移，在较短路径上积累的引诱物浓度逐渐增加，选择这条路径的蚂蚁数量也在增加。最后，所有蚂蚁在反馈调整的作用下都会集中在最佳路径上，此时的匹配就是待优化问题的最优解。

（1）采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。

（2）每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接的通讯[4]。

（3）启发式算法拥有其独特的概率搜索方式，很容易达到全局最优的情况。

遗传算法虽然具有快速全局搜索能力，但是对于系统中的反馈信息却没有利用，往往导致无效的积冗迭代，求得的解往往不是最优解[2]，而蚁群算法是通过信息的积累收集和更新，来预测收敛最优路径，但是算法开始阶段信息匮乏，可使用信息较少，会导致算法速度变慢，前期准确性降低，误差积累到后期会导致误差较大[3]。通过将两种算法融合，一方面克服了遗传算法陷入局部最优解的情况，另一方面对照遗传算法父代，减少蚁群算法的误差，优势互补，形成了一种时间效率准确性都比较好的启发式算法[4]，并通过仿真模拟，进行计算二维切割问题。

2.3 MIN（原材料）数学模型

原材料消耗最少数学模型：

，

且为整数。

余料约束：

适额约束：

长度与宽度约束：

面积约束：

目标函数：

最优解存在，但干扰近似解也同样很多。我们將数学模型代入Lingo，求得最优解如表4所示。

将得到的特解反向代入在MATLAB中构建的启发式算法中，得到遗传算法迭代图和蚁群算法轨迹图[5]。如下图1、图2所示。

由图3可知，在遗传算法100次迭代之后，目标函数优化曲线已经触碰到最优值，但波动较大，在经过500次迭代之后，曲线的波动性减弱，渐渐平稳于最优解。在蚁群算法轨迹图中，可以看出在经历多次迭代之后，轨迹图形成闭环，且路程最短，可以判定函数已经找到最优解。将从Lingo得出的答案代入启发式算法函数，结果满足约束条件，且全局最优。

2.4 二维矩件排样模型

工厂加工要求使用圆盘剪前，需根据订单切割方案进行排刀。假设排刀架上可以以任意间距排刀，但刀具数量是有限制的，一次排刀上限不能超过5刀。用同一排刀方案切割得到的订单称为一组订单，切割不同组时需要工人重新排刀，称为一次换刀。切割每卷原材料之间均需要换刀[6]。切头剪为“一刀切”，即将整个钢板横向完全切断。经过横向切割后，当且仅当某些订单还需要额外横向一刀将其与废料分开，则将这些订单移至小机器再次切割[7]。同一组内相同订单可以通过一刀同时变成成品。钢材切割订单有两种，分别是板料订单和卷料订单，切完的板料订单直接通过下料小车包装入库[8]。

运用遗传算法，将在Lingo中求得的数据进行排样，然后直接进行优化处理。遗传算法设计如下。

（1）编码：采用十进制整数编码方式。

（2）适应度函数：将适应度函数定义为f? = Area / Area1，其中，Area是待排入矩形零件的面积总和，Area1是所得排样图高度轮廓线以下的矩形板材面积。

（3）初始种群：使用随机函数来生成一定数量的十进制整数序列组成父辈群体，设定种群规模 M=50。

（4）交叉算子：采用单点交叉和双点交叉设置交叉概率pc=1，单点交叉与双点交叉各占一半。

（5）变异算子：采用位置变异和旋转变异设置位置变异概率pm1=0.1和旋转变异概率pm2=0.1。

（6）选择算子：根据适应度函数值从大到小排列执行完交叉、变异操作的个体，选择前M个个体组成下一代父辈群体。

（7）结束条件：设置迭代多少代，设置maxgen = 500。

针对矩形板材排样问题，建立了整数规划模型，利用Lingo，给出了多种限制的条件下的最优排样方案。通过软件计算，需要切割的订单的总面积为s=2336.8，原材料面积S=2715.6m2。

目标函数为零件面积所占板材面积最大：

约束条件：

对于上述线性规划，结合已求的原材料数量，利用Lingo软件求解，得到了最优排样方案，如表5所示。

2.5 切割方案

得到具体切割方案，如表6所示。

3  结语

（1）通过利用数学工具和各种编程软件，严格地对模型进行求解，具有科学性。

（2）本文针对矩形钢材地优化排版切割问题，建立了在不同限制条件下地约束方程，得到了可以解题地各个优化模型，通俗易懂，且在保证使用最少原材料地基础上，同时拥有较高地成材率，模型可以推广到其他二维切割领域使用。

（3）同时对于可行解较多的模型计算，采用了不同的数学工具，大大减少计算时间，利用遗传算法和蚁群算法的启发式算法对计算过程和计算结果进行优化，得到了模型的最优解，使模型的可操作性提高。

（4）本文数学模型建立在原材料供应充足，并且完全切割的情况。但是在实际生产生活中，原材料供给不足，刀具损毁等多种情况发生，影响企业效益，那么在这种情况下如何改变参数和约束条件是今后研究的方向。

（5）本文研究并解决了一些特殊的切割问题，即1.5维切割问题。不仅把切割材料的长和宽作为思考方向，而且加入了面积因素。同时因为面积被材料的长和宽所限制，所以把面积以一个0.5维度放入问题进行考虑。针对其特殊性，采用蚁群和遗传算法进行求解。计算结果表明，该新式混合算法对解决1.5维问题行之有效。其次对于可进一步减小切割损耗的切割路径优化问题进行讨论。通过对比切割路径优化问题和旅行商问题，这双方之间有很多共同之处，最终采用遗传算法求解。最后为了进一步减少浪费，对排样切割所剩下的废料采取进一步的优化措施。经过一次切割之后，由于所剩废料的数量和大小都不同，因此针对这些余料可建立二维切割矩形模型，解法同上。

參考文献

[1] 熊慧，黄菊永.基于贪心启发式算法的多目标二维切割问题[J].电子技术与软件工程，2016（24）：154-155.

[2] 丁建立，陈增强，袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析[J].自动化学报，2004，30（4）： 629-634.

[3] 李淑芳.数控切割下料误差产生的原因及应对策略[J].自动化应用，2018（10）：155-156.

[4] 武小年，奚玉昂，张润莲.DEM中基于遗传与蚁群的混合路径规划算法[J].计算机应用研究，2020，37（9）： 2694-2697.

[5] 李明.基于特征粒子算法的云资源调度策略研究[J].计算机与数字工程，2016，44（2）：307-310，342.

[6] 姚奕，郑潇，张文聪，等.重工钢材智能切割管控系统软件设计[J].电子技术与软件工程，2021（8）：83-84.

[7] 张衡.基于二维平面装箱模型的产品切割问题研究[J].运筹与模糊学，2019，9（4）：249-263.

[8] 何双池，陈学松.二维矩形件排样的切割式填充算法[J].数学的实践与认识，2019，49（18）：132-139.