簡(jiǎn)潔高效的鋼筋優(yōu)化下料方法

芮繼東 姚 剛

(中國(guó)建筑標(biāo)準(zhǔn)設(shè)計(jì)研究院，北京 100048)

1 前言

鋼筋優(yōu)化下料就是通過(guò)對(duì)大量待加工鋼筋進(jìn)行篩選比較、優(yōu)化組合，達(dá)到更多地節(jié)省鋼筋原材料的目的，其優(yōu)化目標(biāo)值是使用的鋼筋原料最少。鋼筋優(yōu)化下料問(wèn)題是個(gè)典型的一維優(yōu)化組合問(wèn)題。目前解決方法主要分三類(lèi):確定型最優(yōu)解［1］、啟發(fā)式法［2］、和逼近最優(yōu)解法。目前相關(guān)文獻(xiàn)研究較多的優(yōu)化方法有一維線性規(guī)劃法［3］，遺傳算法［4］、混合遺傳算法、模擬退火算法等［5］。實(shí)際工程建設(shè)中，由于待加工鋼筋有成千上萬(wàn)根，長(zhǎng)短不一，其組合數(shù)目將是天文數(shù)字，因此無(wú)法使用確定型最優(yōu)解法，要想達(dá)到高效、快速的優(yōu)化目的，必須采用更加簡(jiǎn)潔、更加高效的優(yōu)化方法。本文作者經(jīng)過(guò)長(zhǎng)時(shí)間研究及實(shí)際算例分析，提出了一種簡(jiǎn)潔高效的鋼筋優(yōu)化下料方法——“智能篩”優(yōu)化下料技術(shù)，既模擬篩子的工作過(guò)程，經(jīng)過(guò)設(shè)置合適的“篩孔”及“搖篩”方法達(dá)到優(yōu)化斷料的目的。該方法在“平法鋼筋下料軟件”中實(shí)際應(yīng)用多年，取得了良好的應(yīng)用效果。

2 “智能篩”優(yōu)化下料方法

本文首次提出了“智能篩”優(yōu)化技術(shù)進(jìn)行斷料優(yōu)化，取得了顯著的優(yōu)化效果。所謂智能篩，是一個(gè)十分生動(dòng)、形象的比喻。想到篩子，我們會(huì)聯(lián)想到兩點(diǎn)，一是篩選原料時(shí)要確定合適的篩孔，二是掌握搖篩子的技巧。“智能篩”優(yōu)化技術(shù)正是通過(guò)兩個(gè)步驟完成鋼筋下料的優(yōu)化過(guò)程。

第一步是通過(guò)對(duì)待下料鋼筋的分析判斷，自動(dòng)對(duì)“篩孔”大小進(jìn)行動(dòng)態(tài)調(diào)節(jié)，初步篩選出一組較優(yōu)的組合方案;第二步是通過(guò)智能“搖篩”方法，對(duì)初步篩選出來(lái)的方案進(jìn)一步進(jìn)行優(yōu)化組合，完成最終優(yōu)化。

具體解釋一下，優(yōu)化過(guò)程是這樣的:通常原料的長(zhǎng)度是固定的，9m或12m原料居多，也可能有幾種原料供選擇。待加工鋼筋則長(zhǎng)短不一，有各種各樣的組合結(jié)果，挑選某一組優(yōu)選鋼筋組合的原則是幾根待加工鋼筋組合起來(lái)總長(zhǎng)不超過(guò)一根原材的長(zhǎng)度，而且其長(zhǎng)度越接近原材長(zhǎng)度越好。組合鋼筋總長(zhǎng)與原材長(zhǎng)度的差值我們稱其為“縫隙”。例如，原材長(zhǎng)度是12m，某一組鋼筋組合是6m+4m+1．8m，總長(zhǎng)是11．8m，與 12m 比較差值是 0．2m，既“縫隙”是0．2m。一般認(rèn)為，得到的“縫隙”越小，組合方案越好。但經(jīng)過(guò)我們的研究分析發(fā)現(xiàn)事實(shí)并非如此，例如，原材長(zhǎng)度為12m時(shí)，我們將待下料鋼筋中所有的6m長(zhǎng)的鋼筋選出，組合成6m+6m的零縫隙鋼筋組合(人工優(yōu)化最常用的方式)，再組合其它的待下料鋼筋，這樣得到的總體優(yōu)化效果并不一點(diǎn)很好。換句話說(shuō)，我們初步篩選組合方案時(shí)，將篩子的孔徑設(shè)為0，只有零縫隙的鋼筋組合或當(dāng)前能得到的最小縫隙的鋼筋組合可以被篩選出來(lái)，這樣就可以得到優(yōu)化過(guò)程中某一時(shí)刻的最優(yōu)組合，但這樣得到的結(jié)果其整體優(yōu)化效果并不是最好，原因是級(jí)配可能不合理。如果調(diào)整篩孔的大小，先篩選出縫隙小于篩孔的組合，會(huì)得到不同的整體組合結(jié)果，因此篩孔的大小直接影響到初步但對(duì)某一批鋼筋最合適的篩孔，對(duì)另一批鋼筋并不一定是最佳的。只有通過(guò)分析、比較，動(dòng)態(tài)調(diào)整篩子孔徑的大小，才能獲得一組縫隙級(jí)配合理，更為優(yōu)化的組合方案。這就是“智能篩”優(yōu)化技術(shù)的第一個(gè)步驟――智能設(shè)置篩孔大小，并可以動(dòng)態(tài)調(diào)節(jié)。

“智能篩”技術(shù)的第二個(gè)優(yōu)化步驟是智能選擇“搖篩”方法，對(duì)初步篩選出來(lái)的組合方案進(jìn)行再次調(diào)整，縫隙重新組合，以達(dá)到進(jìn)一步優(yōu)化的目的。大家都知道這樣一個(gè)常識(shí)，通常我們往一個(gè)竹筐里裝砂石，裝滿一筐后，如果我們反復(fù)搖動(dòng)、振動(dòng)竹筐，砂石表面就會(huì)往下沉降。滿滿一竹筐砂石又會(huì)騰出一些空間來(lái)。這是因?yàn)榻?jīng)過(guò)反復(fù)搖動(dòng)、振動(dòng)，砂石的孔隙率減小了，密實(shí)度高了，因此更加節(jié)省了空間。本文作者正是由此得到啟發(fā)，開(kāi)始研究“搖篩”的方法。

篩選組合的結(jié)果，如圖1所示，我們將12m定長(zhǎng)的鋼筋原料看作一個(gè)上下等寬的竹筐，待下料鋼筋比作砂石，經(jīng)過(guò)第一步“篩選”后裝滿了竹筐。然后進(jìn)入第二步“搖篩”過(guò)程，首先，選擇某一個(gè)鋼筋組合作為“目標(biāo)組合”，通過(guò)不同的鋼筋組合之間的不等長(zhǎng)度的鋼筋置換，獲取較大的空隙，然后將“目標(biāo)組合”中的某根鋼筋填入這個(gè)空隙。按此方法不斷進(jìn)行鋼筋置換，直到將“目標(biāo)組合”中的所有鋼筋都填入騰出來(lái)的空隙中，一根鋼筋原料就被節(jié)約出來(lái)了。再選定某個(gè)鋼筋組合作為“目標(biāo)組合”，重復(fù)這個(gè)“搖篩”過(guò)程，直到無(wú)法將“目標(biāo)組合”中的所有鋼筋騰空為止。

3 與基于遺傳算法等優(yōu)化方法比較

目前基于遺傳算法進(jìn)行改進(jìn)的優(yōu)化方法較多，這些方法大多是采用隨機(jī)編碼方法挑選一些染色體，并通過(guò)FFD、BFD等方法對(duì)染色體進(jìn)行調(diào)整，使之成為有效染色體，然后通過(guò)選擇遺傳算子、雜交概率Pc，變異概率Pm進(jìn)行遺傳進(jìn)化。這種方法遺傳進(jìn)化過(guò)程繁瑣，且存在一定的隨機(jī)性，優(yōu)化結(jié)果受初始染色體群組的選擇、相關(guān)參數(shù)的設(shè)定、進(jìn)化方式選擇等因素的影響。

本文提出的“智能篩”優(yōu)化方法在第一步挑選染色體時(shí)既與NP裝箱問(wèn)題中常用的FFD、BFD方法不同。后者只是順序拾取下一個(gè)待裝箱的物品，選擇最合適的箱子裝進(jìn)去，若無(wú)法放入現(xiàn)有的非空箱中則新打開(kāi)一個(gè)空箱;本文方法是打開(kāi)一個(gè)箱子，然后將所有待裝箱物品進(jìn)行優(yōu)化組合，篩選出當(dāng)前最優(yōu)組合，放入箱子，然后關(guān)上這個(gè)箱子，再打開(kāi)下一個(gè)箱子。關(guān)箱的標(biāo)準(zhǔn)箱是所剩空間已經(jīng)小于設(shè)定的“空隙”，或者是當(dāng)前能夠找到的最小空隙的組合。

圖1 “搖篩”優(yōu)化過(guò)程示意圖

在鋼筋下料問(wèn)題中，一個(gè)箱子就是一根原料，裝箱物品就是待加工鋼筋，一個(gè)組合就是一根原料上的待加工鋼筋的組合，也稱為基因。當(dāng)所有的待加工鋼筋裝箱后，一個(gè)染色體產(chǎn)生了。通過(guò)設(shè)置適當(dāng)?shù)摹翱障丁保沟迷撊旧w具有可進(jìn)化特性。第二步遺傳進(jìn)化過(guò)程則是在染色體內(nèi)部通過(guò)基因的變異完成的。該方法具有非常理想的魯棒性。

4 實(shí)際算例比較

下面我們通過(guò)一組實(shí)例說(shuō)明一下利用“智能篩”技術(shù)進(jìn)行下料優(yōu)化的步驟及優(yōu)化效果。

4．1 本文實(shí)例，假設(shè)待下料鋼筋為3 600×96，2 255×48，1 555×48，原材長(zhǎng)度9m。

表1 通過(guò)步驟一得到的初步優(yōu)化組合方案

表2 通過(guò)步驟二最后確定的優(yōu)化方案

通過(guò)這個(gè)實(shí)例，我們可以清楚的看到經(jīng)過(guò)第二步“搖篩”過(guò)程，使鋼筋組合進(jìn)一步優(yōu)化了，用料根數(shù)從66根減少到62根，效果很明顯。

4．2 與理論最優(yōu)解比較

文獻(xiàn)［6］中所用的算例:用長(zhǎng)度為4m的圓鋼，下長(zhǎng)度為698mm的零件4 000個(gè)和長(zhǎng)度為518mm的零件3 600個(gè)。如何下料才能使消耗的圓鋼數(shù)量最少?

由于該例子下料種類(lèi)只有兩種，原材長(zhǎng)度只有一種，所以很容易由線性規(guī)劃方法得到理論最優(yōu)解。首先窮舉所有下料組合，共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

假設(shè)某個(gè)組合數(shù)依次為 X1、X2、X3、X4、X5、X6，可以得出

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

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

同時(shí)要滿足 X1＞=0、X2＞=0、X3＞=0、X4＞ =0、X5＞ =0、X6＞ =0

目標(biāo)值:minS=X1+X2+X3+X4+X5+X6

解得該示例的理論最優(yōu)解為 X2=800，X4=400總共用料1 200根。

用本文所創(chuàng)的“智能篩”優(yōu)化方法，設(shè)定“篩孔”為200mm，得到第一步“篩選”優(yōu)化組合結(jié)果(表1):

表3 通過(guò)步驟一得到的初步優(yōu)化組合方案

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

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

4×518組合，共1根

總計(jì)用料1 229根，比理論值多出29根，多用原料2．36%，結(jié)果較優(yōu)。

再進(jìn)入第二步“搖篩”過(guò)程，得到進(jìn)一步優(yōu)化結(jié)果(表4):

表4 通過(guò)步驟一得到的初步優(yōu)化組合方案

用料總根數(shù)1 201總計(jì)用料1 201根，多用的一根原料剩余1 928mm，還有利用價(jià)值。由此可見(jiàn)，用“智能篩”優(yōu)化方法所得優(yōu)化結(jié)果非常逼近理論值。

該算例很好地詮釋了“智能篩”優(yōu)化方法的工作原理:第一步通過(guò)“篩孔”調(diào)節(jié)選出一組級(jí)配合理，可進(jìn)化的染色體，其中包含組合A(698×4+518×2)的基因1 000只，和組合B(518×7)的基因228只;第二步通過(guò)“搖篩”置換過(guò)程使優(yōu)化結(jié)果不斷進(jìn)化。

下面我們描述一下典型的“搖篩”過(guò)程，首先選定一個(gè)組合作為“目標(biāo)組合”，也可以稱之為目標(biāo)基因?！皳u篩”的目標(biāo)是要將該目標(biāo)基因中的所有鋼筋填入置換出來(lái)的“空隙”中。料長(zhǎng)較短的基因作為優(yōu)選目標(biāo)，因此我們選擇某個(gè)B組合作為目標(biāo)基因C。下面開(kāi)始置換過(guò)程，在A組合中選擇一個(gè)基因A，在B組合中選擇一個(gè)基因B，將基因A中的料長(zhǎng)698的鋼筋與基因B中的料長(zhǎng)為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

經(jīng)過(guò)兩次置換，基因A2獲得了532mm的空隙，這樣就可以將目標(biāo)基因C中的一根料長(zhǎng)518的鋼筋填入基因A2中，基因C中的鋼筋由7根減少到6根。重復(fù)7次這樣的過(guò)程后，基因C中的所有鋼筋都被填入空隙中，一根原料就被節(jié)省出來(lái)。

4．3 多規(guī)格一維下料方案比較

文獻(xiàn)［7］中提到，原料的尺寸有6m，8m，9m三種，原料根數(shù)不受限制，所需加工的零件尺寸及規(guī)格見(jiàn)表5。

文獻(xiàn)［7］在解決多規(guī)格原材下料問(wèn)題時(shí)，采用了混合遺傳算法，既在基本遺傳算法中增加了解碼—局部搜索—編碼變化的操作。將局部搜索得到的最優(yōu)解重新編碼組成新的個(gè)體，從而獲得一個(gè)可行的且性能較為優(yōu)良的新群體。表6是用文獻(xiàn)［7］的方法得到的下料方案，表7是本文方法得到的下料方案。比較兩個(gè)方案發(fā)現(xiàn)，文獻(xiàn)［7］的下料方案需要215m長(zhǎng)的原材料，本文方法使用210m原材料。本文方法不僅節(jié)約了5m長(zhǎng)的原材，而且絕大多數(shù)的原材都達(dá)到了100%的利用率，優(yōu)化效果非常理想。

表5 文獻(xiàn)［7］中實(shí)例

表6 文獻(xiàn)［7］下料方案

續(xù)表

續(xù)表

表7 本文方法下料方案

續(xù)表

4．4 文獻(xiàn)［4］實(shí)例比較

母材長(zhǎng)度3m，需下長(zhǎng)2．2m的棒材3件 ，長(zhǎng)1．8m的棒材3件，長(zhǎng)1．2m的棒材4件，長(zhǎng)0．5m 的棒材6件，長(zhǎng)0．3m的棒材6件。

文獻(xiàn)［4］采用了基于遺傳算法的優(yōu)化方法。文獻(xiàn)［8］采用啟發(fā)式多級(jí)序列線性優(yōu)化方法，并通過(guò)同一實(shí)例與文獻(xiàn)［4］進(jìn)行比較。本文同樣用此實(shí)例與上述兩個(gè)文獻(xiàn)的優(yōu)化結(jié)果進(jìn)行比較。三種方法的優(yōu)化結(jié)果在表8中給出。

表8 文獻(xiàn)［4］、文獻(xiàn)［8］及本文方法優(yōu)化結(jié)果比較

從表8的優(yōu)化斷料方案比較中看出，雖然三種方法所得的結(jié)果都是使用8根原料，但本文方法所得的結(jié)果沒(méi)有一點(diǎn)原材浪費(fèi)，最后一根原材剩下2．4m，還可以繼續(xù)使用。顯然本文的下料方案是最優(yōu)的。

本文還比較了其它幾個(gè)文獻(xiàn)的優(yōu)化實(shí)例結(jié)果，都獲得了相當(dāng)滿意的優(yōu)化結(jié)果，鑒于篇幅原因，本文不再贅述。

5 結(jié)語(yǔ)

本文依據(jù)日常生活中使用的篩子工作原理，首次提出了“智能篩”優(yōu)化下料方法，使得復(fù)雜的優(yōu)化數(shù)學(xué)理論問(wèn)題變得直觀易懂，且具有非常理想的魯棒性。通過(guò)與其它文獻(xiàn)中使用的實(shí)例比較看出，優(yōu)化效果十分顯著。該方法應(yīng)用于平法鋼筋下料計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)中，實(shí)現(xiàn)鋼筋優(yōu)化下料、加工、庫(kù)存一體化計(jì)算機(jī)管理，非常好的解決了由于優(yōu)化組合帶來(lái)的待加工鋼筋變得無(wú)序的問(wèn)題，在實(shí)際應(yīng)用中取得了顯著效果。

［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］華中平，張立．基于線性規(guī)劃的角鋼優(yōu)化下料算法研究［J］．湖北工業(yè)大學(xué)學(xué)報(bào)，2005，20(5):15-18．

［4］賈志新，殷國(guó)富，胡曉兵，等．一維下料方案的遺傳算法優(yōu)化［J］．西安交通大學(xué)學(xué)報(bào)，2002，36(9):967-970．

［5］盧仁甫，馮剛．混合遺傳算法求解一維優(yōu)化下料問(wèn)題［J］．中國(guó)水運(yùn)(理論版)，2006，4(4):205-206．

［6］孫玉霞，姜德芳，渠國(guó)慶，等．機(jī)械零件優(yōu)化下料方法實(shí)踐［J］．煤礦機(jī)械，2001，11:43-45．

［7］多規(guī)格一維型材優(yōu)化下料［J］．機(jī)械科學(xué)與技術(shù)，2003，22(增刊):80-86．

［8］李剛，韓鋒，歐宗瑛，等．棒材下料優(yōu)化新算法及網(wǎng)格鋼窗 CAD［J］．大連輕工業(yè)學(xué)院學(xué)報(bào)，2003，22(3):206-210．