简洁高效的钢筋优化下料方法

芮继东 姚 刚

(中国建筑标准设计研究院，北京 100048)

1 前言

钢筋优化下料就是通过对大量待加工钢筋进行筛选比较、优化组合，达到更多地节省钢筋原材料的目的，其优化目标值是使用的钢筋原料最少。钢筋优化下料问题是个典型的一维优化组合问题。目前解决方法主要分三类:确定型最优解［1］、启发式法［2］、和逼近最优解法。目前相关文献研究较多的优化方法有一维线性规划法［3］，遗传算法［4］、混合遗传算法、模拟退火算法等［5］。实际工程建设中，由于待加工钢筋有成千上万根，长短不一，其组合数目将是天文数字，因此无法使用确定型最优解法，要想达到高效、快速的优化目的，必须采用更加简洁、更加高效的优化方法。本文作者经过长时间研究及实际算例分析，提出了一种简洁高效的钢筋优化下料方法——“智能筛”优化下料技术，既模拟筛子的工作过程，经过设置合适的“筛孔”及“摇筛”方法达到优化断料的目的。该方法在“平法钢筋下料软件”中实际应用多年，取得了良好的应用效果。

2 “智能筛”优化下料方法

本文首次提出了“智能筛”优化技术进行断料优化，取得了显著的优化效果。所谓智能筛，是一个十分生动、形象的比喻。想到筛子，我们会联想到两点，一是筛选原料时要确定合适的筛孔，二是掌握摇筛子的技巧。“智能筛”优化技术正是通过两个步骤完成钢筋下料的优化过程。

第一步是通过对待下料钢筋的分析判断，自动对“筛孔”大小进行动态调节，初步筛选出一组较优的组合方案;第二步是通过智能“摇筛”方法，对初步筛选出来的方案进一步进行优化组合，完成最终优化。

具体解释一下，优化过程是这样的:通常原料的长度是固定的，9m或12m原料居多，也可能有几种原料供选择。待加工钢筋则长短不一，有各种各样的组合结果，挑选某一组优选钢筋组合的原则是几根待加工钢筋组合起来总长不超过一根原材的长度，而且其长度越接近原材长度越好。组合钢筋总长与原材长度的差值我们称其为“缝隙”。例如，原材长度是12m，某一组钢筋组合是6m+4m+1．8m，总长是11．8m，与 12m 比较差值是 0．2m，既“缝隙”是0．2m。一般认为，得到的“缝隙”越小，组合方案越好。但经过我们的研究分析发现事实并非如此，例如，原材长度为12m时，我们将待下料钢筋中所有的6m长的钢筋选出，组合成6m+6m的零缝隙钢筋组合(人工优化最常用的方式)，再组合其它的待下料钢筋，这样得到的总体优化效果并不一点很好。换句话说，我们初步筛选组合方案时，将筛子的孔径设为0，只有零缝隙的钢筋组合或当前能得到的最小缝隙的钢筋组合可以被筛选出来，这样就可以得到优化过程中某一时刻的最优组合，但这样得到的结果其整体优化效果并不是最好，原因是级配可能不合理。如果调整筛孔的大小，先筛选出缝隙小于筛孔的组合，会得到不同的整体组合结果，因此筛孔的大小直接影响到初步但对某一批钢筋最合适的筛孔，对另一批钢筋并不一定是最佳的。只有通过分析、比较，动态调整筛子孔径的大小，才能获得一组缝隙级配合理，更为优化的组合方案。这就是“智能筛”优化技术的第一个步骤――智能设置筛孔大小，并可以动态调节。

“智能筛”技术的第二个优化步骤是智能选择“摇筛”方法，对初步筛选出来的组合方案进行再次调整，缝隙重新组合，以达到进一步优化的目的。大家都知道这样一个常识，通常我们往一个竹筐里装砂石，装满一筐后，如果我们反复摇动、振动竹筐，砂石表面就会往下沉降。满满一竹筐砂石又会腾出一些空间来。这是因为经过反复摇动、振动，砂石的孔隙率减小了，密实度高了，因此更加节省了空间。本文作者正是由此得到启发，开始研究“摇筛”的方法。

筛选组合的结果，如图1所示，我们将12m定长的钢筋原料看作一个上下等宽的竹筐，待下料钢筋比作砂石，经过第一步“筛选”后装满了竹筐。然后进入第二步“摇筛”过程，首先，选择某一个钢筋组合作为“目标组合”，通过不同的钢筋组合之间的不等长度的钢筋置换，获取较大的空隙，然后将“目标组合”中的某根钢筋填入这个空隙。按此方法不断进行钢筋置换，直到将“目标组合”中的所有钢筋都填入腾出来的空隙中，一根钢筋原料就被节约出来了。再选定某个钢筋组合作为“目标组合”，重复这个“摇筛”过程，直到无法将“目标组合”中的所有钢筋腾空为止。

3 与基于遗传算法等优化方法比较

目前基于遗传算法进行改进的优化方法较多，这些方法大多是采用随机编码方法挑选一些染色体，并通过FFD、BFD等方法对染色体进行调整，使之成为有效染色体，然后通过选择遗传算子、杂交概率Pc，变异概率Pm进行遗传进化。这种方法遗传进化过程繁琐，且存在一定的随机性，优化结果受初始染色体群组的选择、相关参数的设定、进化方式选择等因素的影响。

本文提出的“智能筛”优化方法在第一步挑选染色体时既与NP装箱问题中常用的FFD、BFD方法不同。后者只是顺序拾取下一个待装箱的物品，选择最合适的箱子装进去，若无法放入现有的非空箱中则新打开一个空箱;本文方法是打开一个箱子，然后将所有待装箱物品进行优化组合，筛选出当前最优组合，放入箱子，然后关上这个箱子，再打开下一个箱子。关箱的标准箱是所剩空间已经小于设定的“空隙”，或者是当前能够找到的最小空隙的组合。

图1 “摇筛”优化过程示意图

在钢筋下料问题中，一个箱子就是一根原料，装箱物品就是待加工钢筋，一个组合就是一根原料上的待加工钢筋的组合，也称为基因。当所有的待加工钢筋装箱后，一个染色体产生了。通过设置适当的“空隙”，使得该染色体具有可进化特性。第二步遗传进化过程则是在染色体内部通过基因的变异完成的。该方法具有非常理想的鲁棒性。

4 实际算例比较

下面我们通过一组实例说明一下利用“智能筛”技术进行下料优化的步骤及优化效果。

4．1 本文实例，假设待下料钢筋为3 600×96，2 255×48，1 555×48，原材长度9m。

表1 通过步骤一得到的初步优化组合方案

表2 通过步骤二最后确定的优化方案

通过这个实例，我们可以清楚的看到经过第二步“摇筛”过程，使钢筋组合进一步优化了，用料根数从66根减少到62根，效果很明显。

4．2 与理论最优解比较

文献［6］中所用的算例:用长度为4m的圆钢，下长度为698mm的零件4 000个和长度为518mm的零件3 600个。如何下料才能使消耗的圆钢数量最少?

由于该例子下料种类只有两种，原材长度只有一种，所以很容易由线性规划方法得到理论最优解。首先穷举所有下料组合，共6种:

1:5×6982:4×698+2×518

3:3×698+3×518

4:2×698+5×518

5:1×698+6×518

6:7×518

假设某个组合数依次为 X1、X2、X3、X4、X5、X6，可以得出

5X1+4X2+3X3+2X4+X5＞=4 000

2X1+3X3+5X4+6X5+7X6＞=3 600

同时要满足 X1＞=0、X2＞=0、X3＞=0、X4＞ =0、X5＞ =0、X6＞ =0

目标值:minS=X1+X2+X3+X4+X5+X6

解得该示例的理论最优解为 X2=800，X4=400总共用料1 200根。

用本文所创的“智能筛”优化方法，设定“筛孔”为200mm，得到第一步“筛选”优化组合结果(表1):

表3 通过步骤一得到的初步优化组合方案

A组合:4×698+2×518组合，共1 000根(X2=1 000)

B组合:7×518组合，共228根(X6=228)

4×518组合，共1根

总计用料1 229根，比理论值多出29根，多用原料2．36%，结果较优。

再进入第二步“摇筛”过程，得到进一步优化结果(表4):

表4 通过步骤一得到的初步优化组合方案

用料总根数1 201总计用料1 201根，多用的一根原料剩余1 928mm，还有利用价值。由此可见，用“智能筛”优化方法所得优化结果非常逼近理论值。

该算例很好地诠释了“智能筛”优化方法的工作原理:第一步通过“筛孔”调节选出一组级配合理，可进化的染色体，其中包含组合A(698×4+518×2)的基因1 000只，和组合B(518×7)的基因228只;第二步通过“摇筛”置换过程使优化结果不断进化。

下面我们描述一下典型的“摇筛”过程，首先选定一个组合作为“目标组合”，也可以称之为目标基因。“摇筛”的目标是要将该目标基因中的所有钢筋填入置换出来的“空隙”中。料长较短的基因作为优选目标，因此我们选择某个B组合作为目标基因C。下面开始置换过程，在A组合中选择一个基因A，在B组合中选择一个基因B，将基因A中的料长698的钢筋与基因B中的料长为518的钢筋置换。

基因A:4×698+2×518空隙172

基因B:7×518空隙381

第一次置换得

基因A1:3×698+3×518空隙352

基因B1:1×698+6×518空隙201

第二次置换得

基因A2:2×698+4×518空隙532

基因B2:2×698+5×518空隙201

经过两次置换，基因A2获得了532mm的空隙，这样就可以将目标基因C中的一根料长518的钢筋填入基因A2中，基因C中的钢筋由7根减少到6根。重复7次这样的过程后，基因C中的所有钢筋都被填入空隙中，一根原料就被节省出来。

4．3 多规格一维下料方案比较

文献［7］中提到，原料的尺寸有6m，8m，9m三种，原料根数不受限制，所需加工的零件尺寸及规格见表5。

文献［7］在解决多规格原材下料问题时，采用了混合遗传算法，既在基本遗传算法中增加了解码—局部搜索—编码变化的操作。将局部搜索得到的最优解重新编码组成新的个体，从而获得一个可行的且性能较为优良的新群体。表6是用文献［7］的方法得到的下料方案，表7是本文方法得到的下料方案。比较两个方案发现，文献［7］的下料方案需要215m长的原材料，本文方法使用210m原材料。本文方法不仅节约了5m长的原材，而且绝大多数的原材都达到了100%的利用率，优化效果非常理想。

表5 文献［7］中实例

表6 文献［7］下料方案

续表

续表

表7 本文方法下料方案

续表

4．4 文献［4］实例比较

母材长度3m，需下长2．2m的棒材3件 ，长1．8m的棒材3件，长1．2m的棒材4件，长0．5m 的棒材6件，长0．3m的棒材6件。

文献［4］采用了基于遗传算法的优化方法。文献［8］采用启发式多级序列线性优化方法，并通过同一实例与文献［4］进行比较。本文同样用此实例与上述两个文献的优化结果进行比较。三种方法的优化结果在表8中给出。

表8 文献［4］、文献［8］及本文方法优化结果比较

从表8的优化断料方案比较中看出，虽然三种方法所得的结果都是使用8根原料，但本文方法所得的结果没有一点原材浪费，最后一根原材剩下2．4m，还可以继续使用。显然本文的下料方案是最优的。

本文还比较了其它几个文献的优化实例结果，都获得了相当满意的优化结果，鉴于篇幅原因，本文不再赘述。

5 结语

本文依据日常生活中使用的筛子工作原理，首次提出了“智能筛”优化下料方法，使得复杂的优化数学理论问题变得直观易懂，且具有非常理想的鲁棒性。通过与其它文献中使用的实例比较看出，优化效果十分显著。该方法应用于平法钢筋下料计算机辅助设计系统中，实现钢筋优化下料、加工、库存一体化计算机管理，非常好的解决了由于优化组合带来的待加工钢筋变得无序的问题，在实际应用中取得了显著效果。

［1］Carvalho V．LP models for bin packing and cutting stock problem［J］．European Journal of Operational Research，2002，141(2):253-273．

［2］Gradisar M．Resinovic G，Jesenko J．etc．A sequential procedure for one dimensional cutting［J］．European Journal of Operational Research，1999，114(3):557-568．

［3］华中平，张立．基于线性规划的角钢优化下料算法研究［J］．湖北工业大学学报，2005，20(5):15-18．

［4］贾志新，殷国富，胡晓兵，等．一维下料方案的遗传算法优化［J］．西安交通大学学报，2002，36(9):967-970．

［5］卢仁甫，冯刚．混合遗传算法求解一维优化下料问题［J］．中国水运(理论版)，2006，4(4):205-206．

［6］孙玉霞，姜德芳，渠国庆，等．机械零件优化下料方法实践［J］．煤矿机械，2001，11:43-45．

［7］多规格一维型材优化下料［J］．机械科学与技术，2003，22(增刊):80-86．

［8］李刚，韩锋，欧宗瑛，等．棒材下料优化新算法及网格钢窗 CAD［J］．大连轻工业学院学报，2003，22(3):206-210．