吴优，李智璞，陈富，李增军，张乃受

（1.中交第一航务工程局有限公司，天津300461；2.中交天津港湾工程研究院有限公司，天津300222）

0 引言

一维下料问题在工程建设中普遍存在，在目前工地施工过程中，由于没有先进的技术指导，工人切割断料大多凭个人经验，导致大量原材在断料切割过程中被浪费，目前钢筋行业平均浪费率水平为4%～6%。针对钢筋一维下料优化组合问题，有两大类解决方法，一类是在分支定界算法基础上，根据多长度切割问题特点来设计启发函数和剪枝方法。Hemmelmayr V等[1]提出了变量邻居搜索元启发方法；Brando等[2]使用前缀树表征分割模式以加快算法搜索速度。另一类是使用智能演化算法来处理此类问题，遗传算法[3]、模拟退火算法[4]、蜂群算法[5]、蚁群算法[6-7]等被应用于一维下料问题中。但以上方法仍存在不足，基于分支定界类的方法计算时间较长；而智能演化算法虽能够快速收敛，但容易出现早熟收敛现象。因此，有必要针对以上不足，依据工程需求及料场原材情况，将一维下料优化问题作为智能决策任务在众多排样方案中快速选择最优方案，实现一维下料优化，降低残料浪费，使成本降至最低。

此外，目前针对钢筋分拣过程的研究内容较少，若采用传统人工手动下料的方式不仅原材浪费率较高，现场工人操作也费时费力；若针对钢筋下料进行优化，下料优化结果料单切出的成品往往较为杂乱，现场工人的分拣压力较大；此外，不当的原材加工顺序，将会造成料仓容量浪费，大幅降低生产效率。因此，有必要针对下料优化结果，生成最优原材加工顺序，并进行料仓优化布置，在用料最省的基础上保证生产效率。

综上，本文在现有成果基础上，以保证生产质量为前提，在考虑加工设备对成品影响的基础上，重点研究切割以及分拣过程中的优化，以期从现场施工角度，实现对钢筋一维材料加工成本、质量、效率的有效保证；以工程施工中钢筋为研究对象，利用计算机程序强大的计算能力，将不同优化算法应用于钢材生产过程，建立切割与分拣的优化数学模型，并进行了工程应用实例分析。

1 基于梯度提升决策树及整数规划的一维下料优化

由于各工程中一维材料数量繁多、长度参差不齐，下料方案存在无限的可能性，想要降低生产成本，就必须在众多的下料方案中选择最优或接近最优的方案，提高原材料利用率，这是一个典型的智能决策任务。

1.1 一维下料优化模型

假设某构件需要加工后的成品规格共q种，长度分别为l1，l2，…，lq，记为li，对应数量分别为b1，b2，…，bq，记为bi（i=1，2，…，q）。假设采购长度Lx和Ly原材，分别为X和Y根。其中，长度Lx的原材有m种切割方案，每种切割方案重复Xj次（j=1，2，…，m），该方案中成品li的个数为axij；长度Ly的原材有n种切割方案，每种切割方案重复Yk次（k=1，2，…，n）；该方案中成品li的个数为axik，数学模型参数表如表1所示。

表1 一维下料数学模型参数表Table 1 Parameters of one-dimensional cutting model

将废料最少作为目标函数，钢筋下料问题可抽象成数学模型如式（1）。

方程已知数有2+2q个，未知数共m+n+q×（m+n）+1个，方程等式q个，不等式2q个，未知数均为大于等于0的整数，实际用量最少问题的转化为求目标函数最小值的问题。

1.2 基于梯度提升决策树及整数规划的模型求解方法

若采用传统整数规划方法进行优化，则需统计出全部原材的切割方案，由于工程中往往成品种类需求众多，其组合数更是成指数型增长，大大降低了计算效率，因此针对建立的一维下料优化模型，即式（1），本文采用梯度提升决策树（Gradient Boosting Decision Tree，GBDT）构建有限的优选切割方案集，再结合整数规划进行优化求解，GBDT是以决策树为弱学习器的提升方法，在参数反演[8]、评估预测[9-10]、数据分析[11]、图像识别[12]等方面具有广泛应用，本文基于梯度提升决策树及整数规划的模型求解方法，具体步骤如下：

步骤1：模型的初始化，初始化估计函数：

式中：P为一维切割方案集，由多个切割方案组成P={p1，p2，…}，即有多组不同{β，α}；β为每种成品的数量；α为每种成品的长度。

步骤2：计算其在模型F（z；{β，α}）下的损失函数L（l，F（z；P）），并设定迭代次数D，其中l表示原材长度。

步骤3：通过梯度计算公式：

式中：t={1，2，…，T}，T表示设定样本点个数（zt，lt），由此计算损失函数的负梯度，得到梯度下降的方向。

步骤4：利用步骤3得到的负梯度值拟合残差，并由此更新决策树h（z；αd）。

步骤5：更新估计函数F（z；P），令Fd（z）=Fd-1（z）+βdh（z；αd）。

步骤6：令d=d+1，循环步骤1～5，直到达到迭代次数上限。

步骤7：得到最终回归树FD（z；P）。

步骤8：针对有限的一维切割方案集P按式（1）模型进行整数规划得下料优化结果。

2 基于动态贪心算法的胚料分拣优化

根据所得多种一维切割方案，需按一定顺序加工，针对分拣设备有限的料仓空间，不同的方案加工顺序会导致加工进度差异。因此，基于课题组自主研发的智能自动分拣设备，在考虑众多限制因素的前提下，应选择最优的加工顺序并对切割成品进行优化布置。

2.1 胚料分拣优化模型

以分拣设备为依据，将胚料分拣问题建立数学模型如下：

设切割所得q种成品长度分别为l1，l2，…，lq，数量分别为b1，b2，…，bq，切割设备的加工能力为g根（即一次性最多同时切割g根原材），分拣设备共w个料仓，长度分别为L1，L2，…，Lw，各料仓可容纳胚料根数分别为c1，c2，…，cw，生产过程中经过切割的胚料按加工顺序自动进入料仓中，在不超过每个料仓的限制容量和长度的条件下，使最终所需总料仓数N最小。当分拣设备w个料仓存满无法再放入新的胚料后清仓，清仓后继续按顺序放入胚料，直至胚料全部放入料仓，共清仓s次。数学模型参数表见表2。由于分拣过程需考虑限制因素众多，可整理如下：

表2 胚料分拣数学模型参数表Table 2 Parameters of production sorting model

1）切割过程不可间断。

2）同加工批次不同原材不得穿插加工。

3）同型号胚料需共同储存。

4）各料仓有长度限制。

5）分拣装置料仓容量固定，可放置胚料根数有限，当料仓装满同型号胚料需放入新料仓。

6）分拣设备料仓数固定，当下一加工单位无法全部放入料仓中，需全部清仓。

在考虑以上全部因素的同时须尽可能将料仓数降至最低，对加工单位进行排序以提高生产效率。其中同种原材单批次料仓的优化模型如下，由于料仓数量求解无法用确定的数学计算公式求得，故料仓总数用清仓次数表达。

其中[bxij/ci]为bxij/ci的向上取整函数，ws为最后一批次所占用料仓个数。

2.2 基于动态贪心算法的模型求解方法

针对建立的胚料分拣优化模型，即式（4），采用贪心策略求解，基于动态贪心策略的模型求解方法流程如图1所示。具体步骤如下：

图1 分拣优化流程图Fig.1 Flow chart for sorting optimization

步骤1：输入原材切割方案集，并按直径和长度进行分类，由于不同种类的原材不能穿插加工，将不同种类的钢筋按不同顺序形成不同组合，同时初始化最少料仓数Nmin。

步骤2：由于切割设备针对不同直径原材的最大加工能力有所差异，按切割设备生产能力将切割方案拆解为加工单元ai（i=1，2，…，u），u为当前加工方案产出的成品段数。

步骤3：针对当前料仓存储情况，通过动态贪心算法确定不同切割方案各加工单元ai有效新增容量Vi，其中：为加工单元ai针对当前料仓存储情况下的成品新增长度。

步骤4：将加工单元按有效新增容量Vi排序，并判断最小有效新增容量对应加工单元能否放入料仓内，若可以则放入料仓，否则清空料仓，并更新料仓信息。

步骤5：重复执行步骤3～4，直至全部加工单位全部加工完毕。

步骤6：计算最优解，根据式（2）计算当前组合的目标函数最优值N，若N小于Nmin，则将N对应的加工顺序和料仓信息替换当前最优解。

步骤7：重复执行步骤2～6，直至全部组合计算完毕，最终输出优化结果，包括加工顺序及料仓信息等内容。

3 工程应用

以天津某地铁线L环的钢筋生产为例，应用本文算法内容，开展应用生产。工程构件φ25号钢筋需求如表3。原材长度为9 m、12 m和10.15 m三种（其中10.15 m为定尺原材），通过简单统计可以得到成品种类34种，成品数量总计1 036根，成品总长3 268.56 m，重约50.38 t。如果采用手工排布下料，显然难度大，钢筋利用率低。

表3 成品钢筋需求Table 3 Requirement of rebar products

为节省人力物力，大大减少工作量，本文采用第1节内容进行优化，并通过Visual studio C#编程语言进行程序开发并以接口形式与自动切割设备对接。为了分析本研究优化方法与其他算法的优劣，选取决策树法（Decision Tree，DT）、遗传算法（Genetic Algorithm，GA）和蜂群算法（Simu lated Annealing Algorithm，SAA）与本研究算法进行对比分析，结果显示，决策树在成品种类较少，数量也较少的情况下，效果较好，但成品数量超过300或成品种类超过10种以后，计算时间大幅增加；遗传算法、模拟退火算法通过引入变异等随机参数来解决问题，近优率偏低，不同算法计算结果见表4。

表4 不同算法计算结果对比Table 4 Comparison between different algorithms calculation results

通过整数规划与决策树算法求解得到优化料单，其中共形成44种切割方案，共需12 m原材86根、10.15 m原材230根，钢筋利用率达到97.09%，远超传统下料方式，此外本项程序还具备自动计算钢筋重量、计算钢筋利用率、一键出单、数据库存储、软件加密等功能。

基于上述下料优化结果，由于优化料单钢筋成品较为杂乱，人工分拣工作量极大，影响生产效率。为节省人力物力，采用第2节内容进行计算，并通过Visual studio C#编程语言进行程序开发，程序内容与课题组研发自动分拣装置对接，实现现场一键自动分拣。本应用项目自动分拣装置共设置6个料仓，分布于运输线两侧，料仓长度14 m，现场应用情况见图2。

图2 钢筋生产现场应用Fig.2 Field application of rebar production

为了分析本研究优化方法与传统人工分拣方式的优劣，经对比分析结果显示，本章方法只需一人操作控制柜即可，而传统方式需额外增加人力进行分拣；此外，本优化算法结果仅需3批次共占用13个料仓完成整个料单，而人工方式需4批次共占用19个料仓，本优化算法效率大大提升。此外本程序自动生成加工料单，便于指示工人操作，料仓分配情况同步生成，方便后续吊装储存备用。

4 结语

本文在现有成果基础上，以保证生产质量为前提，在考虑切割设备对成品影响的基础上，重点研究一维下料以及分拣过程中的优化，以期从现场施工的角度，实现对加工成本、质量、效率的有效保证；以工程施工中钢材为研究对象，利用计算机程序强大的计算能力，将整数规划、梯度提升决策树、动态贪心策略等应用于钢材生产过程，建立下料与分拣的优化数学模型，并进行了工程应用实例分析。主要的研究成果和结论概括如下：

1）在考虑工程钢筋翻样结果及料场原材情况的基础上，建立了钢筋切割下料优化数学模型，结合整数规划和梯度提升决策树，对钢筋切割方案进行了优化，并编制了程序，实现了自动计算钢筋重量、计算钢筋利用率、一键出单、软件加密等功能。实例应用表明，通过本文钢筋下料优化算法，优化切割方案钢筋利用率达到97.09%，且相较其他算法，本算法不会陷入局部最优解，计算效率更高，从而为钢筋下料提供了新的优化途径，可大幅节省成本。

2）在采取本文钢筋下料优化的基础上，针对课题组自主研发的智能分拣装置，结合动态贪心策略，对钢筋切割方案进行了优化，并编制了程序，实现了一键操作智能分拣、自动生成加工料单、料仓自动分配等功能。实例应用表明，通过本文钢筋分拣优化算法，仅需清仓2次，共占用料仓13个，相较传统分拣大大提升了分拣效率，同时减轻了现场人员工作强度，且可以使下料优化更好地应用于现场。