芮繼東 姚 剛

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

1 前言

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)際算例比較

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

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

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

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

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

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

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

由于該例子下料種類只有兩種，原材長度只有一種，所以很容易由線性規(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 通過步驟一得到的初步優(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)入第二步“搖篩”過程，得到進(jìn)一步優(yōu)化結(jié)果(表4):

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

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

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

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

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

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

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

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

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

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

續(xù)表

續(xù)表

表7 本文方法下料方案

續(xù)表

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

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

文獻(xiàn)［4］采用了基于遺傳算法的優(yōu)化方法。文獻(xiàn)［8］采用啟發(fā)式多級序列線性優(yōu)化方法，并通過同一實(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é)果沒有一點(diǎn)原材浪費(fèi)，最后一根原材剩下2．4m，還可以繼續(xù)使用。顯然本文的下料方案是最優(yōu)的。

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

5 結(jié)語

本文依據(jù)日常生活中使用的篩子工作原理，首次提出了“智能篩”優(yōu)化下料方法，使得復(fù)雜的優(yōu)化數(shù)學(xué)理論問題變得直觀易懂，且具有非常理想的魯棒性。通過與其它文獻(xiàn)中使用的實(shí)例比較看出，優(yōu)化效果十分顯著。該方法應(yīng)用于平法鋼筋下料計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)中，實(shí)現(xiàn)鋼筋優(yōu)化下料、加工、庫存一體化計(jì)算機(jī)管理，非常好的解決了由于優(yōu)化組合帶來的待加工鋼筋變得無序的問題，在實(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］賈志新，殷國富，胡曉兵，等．一維下料方案的遺傳算法優(yōu)化［J］．西安交通大學(xué)學(xué)報(bào)，2002，36(9):967-970．

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

［6］孫玉霞，姜德芳，渠國慶，等．機(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．