吳優(yōu)，李智璞，陳富，李增軍，張乃受

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

0 引言

一維下料問題在工程建設中普遍存在，在目前工地施工過程中，由于沒有先進的技術(shù)指導，工人切割斷料大多憑個人經(jīng)驗，導致大量原材在斷料切割過程中被浪費，目前鋼筋行業(yè)平均浪費率水平為4%～6%。針對鋼筋一維下料優(yōu)化組合問題，有兩大類解決方法，一類是在分支定界算法基礎上，根據(jù)多長度切割問題特點來設計啟發(fā)函數(shù)和剪枝方法。Hemmelmayr V等[1]提出了變量鄰居搜索元啟發(fā)方法；Brando等[2]使用前綴樹表征分割模式以加快算法搜索速度。另一類是使用智能演化算法來處理此類問題，遺傳算法[3]、模擬退火算法[4]、蜂群算法[5]、蟻群算法[6-7]等被應用于一維下料問題中。但以上方法仍存在不足，基于分支定界類的方法計算時間較長；而智能演化算法雖能夠快速收斂，但容易出現(xiàn)早熟收斂現(xiàn)象。因此，有必要針對以上不足，依據(jù)工程需求及料場原材情況，將一維下料優(yōu)化問題作為智能決策任務在眾多排樣方案中快速選擇最優(yōu)方案，實現(xiàn)一維下料優(yōu)化，降低殘料浪費，使成本降至最低。

此外，目前針對鋼筋分揀過程的研究內(nèi)容較少，若采用傳統(tǒng)人工手動下料的方式不僅原材浪費率較高，現(xiàn)場工人操作也費時費力；若針對鋼筋下料進行優(yōu)化，下料優(yōu)化結(jié)果料單切出的成品往往較為雜亂，現(xiàn)場工人的分揀壓力較大；此外，不當?shù)脑募庸ろ樞颍瑢斐闪蟼}容量浪費，大幅降低生產(chǎn)效率。因此，有必要針對下料優(yōu)化結(jié)果，生成最優(yōu)原材加工順序，并進行料倉優(yōu)化布置，在用料最省的基礎上保證生產(chǎn)效率。

綜上，本文在現(xiàn)有成果基礎上，以保證生產(chǎn)質(zhì)量為前提，在考慮加工設備對成品影響的基礎上，重點研究切割以及分揀過程中的優(yōu)化，以期從現(xiàn)場施工角度，實現(xiàn)對鋼筋一維材料加工成本、質(zhì)量、效率的有效保證；以工程施工中鋼筋為研究對象，利用計算機程序強大的計算能力，將不同優(yōu)化算法應用于鋼材生產(chǎn)過程，建立切割與分揀的優(yōu)化數(shù)學模型，并進行了工程應用實例分析。

1 基于梯度提升決策樹及整數(shù)規(guī)劃的一維下料優(yōu)化

由于各工程中一維材料數(shù)量繁多、長度參差不齊，下料方案存在無限的可能性，想要降低生產(chǎn)成本，就必須在眾多的下料方案中選擇最優(yōu)或接近最優(yōu)的方案，提高原材料利用率，這是一個典型的智能決策任務。

1.1 一維下料優(yōu)化模型

假設某構(gòu)件需要加工后的成品規(guī)格共q種，長度分別為l1，l2，…，lq，記為li，對應數(shù)量分別為b1，b2，…，bq，記為bi（i=1，2，…，q）。假設采購長度Lx和Ly原材，分別為X和Y根。其中，長度Lx的原材有m種切割方案，每種切割方案重復Xj次（j=1，2，…，m），該方案中成品li的個數(shù)為axij；長度Ly的原材有n種切割方案，每種切割方案重復Yk次（k=1，2，…，n）；該方案中成品li的個數(shù)為axik，數(shù)學模型參數(shù)表如表1所示。

表1 一維下料數(shù)學模型參數(shù)表Table 1 Parameters of one-dimensional cutting model

將廢料最少作為目標函數(shù)，鋼筋下料問題可抽象成數(shù)學模型如式（1）。

方程已知數(shù)有2+2q個，未知數(shù)共m+n+q×（m+n）+1個，方程等式q個，不等式2q個，未知數(shù)均為大于等于0的整數(shù)，實際用量最少問題的轉(zhuǎn)化為求目標函數(shù)最小值的問題。

1.2 基于梯度提升決策樹及整數(shù)規(guī)劃的模型求解方法

若采用傳統(tǒng)整數(shù)規(guī)劃方法進行優(yōu)化，則需統(tǒng)計出全部原材的切割方案，由于工程中往往成品種類需求眾多，其組合數(shù)更是成指數(shù)型增長，大大降低了計算效率，因此針對建立的一維下料優(yōu)化模型，即式（1），本文采用梯度提升決策樹（Gradient Boosting Decision Tree，GBDT）構(gòu)建有限的優(yōu)選切割方案集，再結(jié)合整數(shù)規(guī)劃進行優(yōu)化求解，GBDT是以決策樹為弱學習器的提升方法，在參數(shù)反演[8]、評估預測[9-10]、數(shù)據(jù)分析[11]、圖像識別[12]等方面具有廣泛應用，本文基于梯度提升決策樹及整數(shù)規(guī)劃的模型求解方法，具體步驟如下：

步驟1：模型的初始化，初始化估計函數(shù)：

式中：P為一維切割方案集，由多個切割方案組成P={p1，p2，…}，即有多組不同{β，α}；β為每種成品的數(shù)量；α為每種成品的長度。

步驟2：計算其在模型F（z；{β，α}）下的損失函數(shù)L（l，F(xiàn)（z；P）），并設定迭代次數(shù)D，其中l(wèi)表示原材長度。

步驟3：通過梯度計算公式：

式中：t={1，2，…，T}，T表示設定樣本點個數(shù)（zt，lt），由此計算損失函數(shù)的負梯度，得到梯度下降的方向。

步驟4：利用步驟3得到的負梯度值擬合殘差，并由此更新決策樹h（z；αd）。

步驟5：更新估計函數(shù)F（z；P），令Fd（z）=Fd-1（z）+βdh（z；αd）。

步驟6：令d=d+1，循環(huán)步驟1～5，直到達到迭代次數(shù)上限。

步驟7：得到最終回歸樹FD（z；P）。

步驟8：針對有限的一維切割方案集P按式（1）模型進行整數(shù)規(guī)劃得下料優(yōu)化結(jié)果。

2 基于動態(tài)貪心算法的胚料分揀優(yōu)化

根據(jù)所得多種一維切割方案，需按一定順序加工，針對分揀設備有限的料倉空間，不同的方案加工順序會導致加工進度差異。因此，基于課題組自主研發(fā)的智能自動分揀設備，在考慮眾多限制因素的前提下，應選擇最優(yōu)的加工順序并對切割成品進行優(yōu)化布置。

2.1 胚料分揀優(yōu)化模型

以分揀設備為依據(jù)，將胚料分揀問題建立數(shù)學模型如下：

設切割所得q種成品長度分別為l1，l2，…，lq，數(shù)量分別為b1，b2，…，bq，切割設備的加工能力為g根（即一次性最多同時切割g根原材），分揀設備共w個料倉，長度分別為L1，L2，…，Lw，各料倉可容納胚料根數(shù)分別為c1，c2，…，cw，生產(chǎn)過程中經(jīng)過切割的胚料按加工順序自動進入料倉中，在不超過每個料倉的限制容量和長度的條件下，使最終所需總料倉數(shù)N最小。當分揀設備w個料倉存滿無法再放入新的胚料后清倉，清倉后繼續(xù)按順序放入胚料，直至胚料全部放入料倉，共清倉s次。數(shù)學模型參數(shù)表見表2。由于分揀過程需考慮限制因素眾多，可整理如下：

表2 胚料分揀數(shù)學模型參數(shù)表Table 2 Parameters of production sorting model

1）切割過程不可間斷。

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

3）同型號胚料需共同儲存。

4）各料倉有長度限制。

5）分揀裝置料倉容量固定，可放置胚料根數(shù)有限，當料倉裝滿同型號胚料需放入新料倉。

6）分揀設備料倉數(shù)固定，當下一加工單位無法全部放入料倉中，需全部清倉。

在考慮以上全部因素的同時須盡可能將料倉數(shù)降至最低，對加工單位進行排序以提高生產(chǎn)效率。其中同種原材單批次料倉的優(yōu)化模型如下，由于料倉數(shù)量求解無法用確定的數(shù)學計算公式求得，故料倉總數(shù)用清倉次數(shù)表達。

其中[bxij/ci]為bxij/ci的向上取整函數(shù)，ws為最后一批次所占用料倉個數(shù)。

2.2 基于動態(tài)貪心算法的模型求解方法

針對建立的胚料分揀優(yōu)化模型，即式（4），采用貪心策略求解，基于動態(tài)貪心策略的模型求解方法流程如圖1所示。具體步驟如下：

圖1 分揀優(yōu)化流程圖Fig.1 Flow chart for sorting optimization

步驟1：輸入原材切割方案集，并按直徑和長度進行分類，由于不同種類的原材不能穿插加工，將不同種類的鋼筋按不同順序形成不同組合，同時初始化最少料倉數(shù)Nmin。

步驟2：由于切割設備針對不同直徑原材的最大加工能力有所差異，按切割設備生產(chǎn)能力將切割方案拆解為加工單元ai（i=1，2，…，u），u為當前加工方案產(chǎn)出的成品段數(shù)。

步驟3：針對當前料倉存儲情況，通過動態(tài)貪心算法確定不同切割方案各加工單元ai有效新增容量Vi，其中：為加工單元ai針對當前料倉存儲情況下的成品新增長度。

步驟4：將加工單元按有效新增容量Vi排序，并判斷最小有效新增容量對應加工單元能否放入料倉內(nèi)，若可以則放入料倉，否則清空料倉，并更新料倉信息。

步驟5：重復執(zhí)行步驟3～4，直至全部加工單位全部加工完畢。

步驟6：計算最優(yōu)解，根據(jù)式（2）計算當前組合的目標函數(shù)最優(yōu)值N，若N小于Nmin，則將N對應的加工順序和料倉信息替換當前最優(yōu)解。

步驟7：重復執(zhí)行步驟2～6，直至全部組合計算完畢，最終輸出優(yōu)化結(jié)果，包括加工順序及料倉信息等內(nèi)容。

3 工程應用

以天津某地鐵線L環(huán)的鋼筋生產(chǎn)為例，應用本文算法內(nèi)容，開展應用生產(chǎn)。工程構(gòu)件φ25號鋼筋需求如表3。原材長度為9 m、12 m和10.15 m三種（其中10.15 m為定尺原材），通過簡單統(tǒng)計可以得到成品種類34種，成品數(shù)量總計1 036根，成品總長3 268.56 m，重約50.38 t。如果采用手工排布下料，顯然難度大，鋼筋利用率低。

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

為節(jié)省人力物力，大大減少工作量，本文采用第1節(jié)內(nèi)容進行優(yōu)化，并通過Visual studio C#編程語言進行程序開發(fā)并以接口形式與自動切割設備對接。為了分析本研究優(yōu)化方法與其他算法的優(yōu)劣，選取決策樹法（Decision Tree，DT）、遺傳算法（Genetic Algorithm，GA）和蜂群算法（Simu lated Annealing Algorithm，SAA）與本研究算法進行對比分析，結(jié)果顯示，決策樹在成品種類較少，數(shù)量也較少的情況下，效果較好，但成品數(shù)量超過300或成品種類超過10種以后，計算時間大幅增加；遺傳算法、模擬退火算法通過引入變異等隨機參數(shù)來解決問題，近優(yōu)率偏低，不同算法計算結(jié)果見表4。

表4 不同算法計算結(jié)果對比Table 4 Comparison between different algorithms calculation results

通過整數(shù)規(guī)劃與決策樹算法求解得到優(yōu)化料單，其中共形成44種切割方案，共需12 m原材86根、10.15 m原材230根，鋼筋利用率達到97.09%，遠超傳統(tǒng)下料方式，此外本項程序還具備自動計算鋼筋重量、計算鋼筋利用率、一鍵出單、數(shù)據(jù)庫存儲、軟件加密等功能。

基于上述下料優(yōu)化結(jié)果，由于優(yōu)化料單鋼筋成品較為雜亂，人工分揀工作量極大，影響生產(chǎn)效率。為節(jié)省人力物力，采用第2節(jié)內(nèi)容進行計算，并通過Visual studio C#編程語言進行程序開發(fā)，程序內(nèi)容與課題組研發(fā)自動分揀裝置對接，實現(xiàn)現(xiàn)場一鍵自動分揀。本應用項目自動分揀裝置共設置6個料倉，分布于運輸線兩側(cè)，料倉長度14 m，現(xiàn)場應用情況見圖2。

圖2 鋼筋生產(chǎn)現(xiàn)場應用Fig.2 Field application of rebar production

為了分析本研究優(yōu)化方法與傳統(tǒng)人工分揀方式的優(yōu)劣，經(jīng)對比分析結(jié)果顯示，本章方法只需一人操作控制柜即可，而傳統(tǒng)方式需額外增加人力進行分揀；此外，本優(yōu)化算法結(jié)果僅需3批次共占用13個料倉完成整個料單，而人工方式需4批次共占用19個料倉，本優(yōu)化算法效率大大提升。此外本程序自動生成加工料單，便于指示工人操作，料倉分配情況同步生成，方便后續(xù)吊裝儲存?zhèn)溆谩?/p>

4 結(jié)語

本文在現(xiàn)有成果基礎上，以保證生產(chǎn)質(zhì)量為前提，在考慮切割設備對成品影響的基礎上，重點研究一維下料以及分揀過程中的優(yōu)化，以期從現(xiàn)場施工的角度，實現(xiàn)對加工成本、質(zhì)量、效率的有效保證；以工程施工中鋼材為研究對象，利用計算機程序強大的計算能力，將整數(shù)規(guī)劃、梯度提升決策樹、動態(tài)貪心策略等應用于鋼材生產(chǎn)過程，建立下料與分揀的優(yōu)化數(shù)學模型，并進行了工程應用實例分析。主要的研究成果和結(jié)論概括如下：

1）在考慮工程鋼筋翻樣結(jié)果及料場原材情況的基礎上，建立了鋼筋切割下料優(yōu)化數(shù)學模型，結(jié)合整數(shù)規(guī)劃和梯度提升決策樹，對鋼筋切割方案進行了優(yōu)化，并編制了程序，實現(xiàn)了自動計算鋼筋重量、計算鋼筋利用率、一鍵出單、軟件加密等功能。實例應用表明，通過本文鋼筋下料優(yōu)化算法，優(yōu)化切割方案鋼筋利用率達到97.09%，且相較其他算法，本算法不會陷入局部最優(yōu)解，計算效率更高，從而為鋼筋下料提供了新的優(yōu)化途徑，可大幅節(jié)省成本。

2）在采取本文鋼筋下料優(yōu)化的基礎上，針對課題組自主研發(fā)的智能分揀裝置，結(jié)合動態(tài)貪心策略，對鋼筋切割方案進行了優(yōu)化，并編制了程序，實現(xiàn)了一鍵操作智能分揀、自動生成加工料單、料倉自動分配等功能。實例應用表明，通過本文鋼筋分揀優(yōu)化算法，僅需清倉2次，共占用料倉13個，相較傳統(tǒng)分揀大大提升了分揀效率，同時減輕了現(xiàn)場人員工作強度，且可以使下料優(yōu)化更好地應用于現(xiàn)場。