簡潔高效的鋼筋優化下料方法

芮繼東 姚 剛

(中國建筑標準設計研究院，北京 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．