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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟3：通過梯度計(jì)算公式：

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

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

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

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

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

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

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

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

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

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

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

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

1）切割過程不可間斷。

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

3）同型號(hào)胚料需共同儲(chǔ)存。

4）各料倉有長度限制。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 工程應(yīng)用

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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