李文杰， 黃 春， 劉占省， 藺宏遠(yuǎn)， 何 陽

(1.北京工業(yè)大學(xué) 建筑工程學(xué)院，北京 100124；2.山東省建筑設(shè)計研究院有限公司，山東 濟(jì)南 250001)

建筑業(yè)是支撐我國經(jīng)濟(jì)發(fā)展的重要傳統(tǒng)產(chǎn)業(yè)，但近十年我國建筑企業(yè)的平均利潤率一直徘徊在3.37%～3.50%之間[1]。全球范圍內(nèi)建筑業(yè)勞動生產(chǎn)率的增長僅為1%，而制造業(yè)則為3.6%[2]。行業(yè)發(fā)展的要求與相對落后的管理和生產(chǎn)水平之間的矛盾已經(jīng)日益突出，迫切需要利用現(xiàn)代信息技術(shù)實現(xiàn)建筑業(yè)的轉(zhuǎn)型升級與持續(xù)健康發(fā)展[3]。針對于此，各國相繼提出建筑業(yè)發(fā)展戰(zhàn)略計劃，如《美國基礎(chǔ)設(shè)施重建計劃》、英國的《建造2025》、德國的《數(shù)字化設(shè)計與建造發(fā)展路線圖》[4]、我國的《建筑業(yè)信息化發(fā)展綱要》和《中國建造2035戰(zhàn)略研究》等計劃[5]。

建筑業(yè)的發(fā)展與四次工業(yè)革命的典型創(chuàng)新技術(shù)緊密結(jié)合，經(jīng)歷了人力、機(jī)械化、自動化及數(shù)字化等階段[6]。尤其在第四次工業(yè)革命中，以數(shù)字化、網(wǎng)絡(luò)化和智能化為標(biāo)志的新一代信息技術(shù)，正在與各產(chǎn)業(yè)深度融合[4]。雖然施工現(xiàn)場具備數(shù)字化基礎(chǔ)，但智能化建造過程目前仍處于起步階段。相對于制造業(yè)的生產(chǎn)過程，傳統(tǒng)工程項目施工過程需要大量的人員參與，具有較高的復(fù)雜性和不確定性。而目前的智能算法則側(cè)重于優(yōu)化具有較高規(guī)律性和重復(fù)性的工序。相對于其他施工工序，塔吊吊裝過程中所涉及的因素較為單一，建筑材料在施工場地中的存儲位置及種類、塔吊位置和塔司等一般不會發(fā)生較大變動，促成了吊裝過程的規(guī)律性與可預(yù)測性。

塔吊是施工現(xiàn)場中最重要的吊裝設(shè)備，其吊裝效率很大程度上決定了現(xiàn)場的施工效率，而吊裝效率則很大程度上取決于塔吊的調(diào)度方案。在施工現(xiàn)場，塔吊調(diào)度方案是按照物料需求出現(xiàn)的時間先后進(jìn)行排序，然后憑借信號工個人經(jīng)驗，通過對講機(jī)指揮塔司運行。但是傳統(tǒng)的調(diào)度方法缺乏對各個物料需求空間位置的系統(tǒng)考慮，造成了塔吊運輸路徑的不合理規(guī)劃以及重復(fù)運輸。因此，本研究擬以塔吊的調(diào)度方案為研究對象，建立優(yōu)化模型，制定塔吊的調(diào)度計劃，提升塔吊運輸效率并由此促進(jìn)智能化建造的發(fā)展。

1 裝配式構(gòu)件吊裝問題分析

研究假定塔吊每次運輸單個構(gòu)件，且塔吊的布置可以覆蓋作業(yè)面，并滿足構(gòu)件的起吊重量。圖1描述了裝配式構(gòu)件吊裝過程中吊鉤的運行軌跡，首先由初始位置D1移動至物料存儲位置S2，裝載物料M2，而后將物料運輸?shù)叫枨笪恢肈1，卸載物料M2，完成首個運輸任務(wù)；然后吊鉤由需求位置D1出發(fā)，移動至物料存儲位置S3，裝載物料M1，運輸并卸載于需求位置D2；以此類推，吊鉤完整的路徑為：D1→S2→D1→S3→D2→S1→D2。

圖1 吊鉤運行路徑

國內(nèi)外學(xué)者將塔吊的調(diào)度問題抽象為運籌學(xué)中經(jīng)典的旅行商問題(Travel Salesman Problem，TSP)。通過將物料存放點和需求點視為TSP問題中的一個個城市，以減少塔吊完成所有物料運輸任務(wù)的距離為目標(biāo)，最終得到塔吊完成任務(wù)的順序，即吊鉤經(jīng)過物料存放點和需求點的順序[7,8]。Zavichi等[8]將此類問題定義為吊機(jī)服務(wù)排序問題(Crane Service Sequencing Problem，CSSP)，并通過整數(shù)規(guī)劃(Integer Programming，IP)建模。隨后，Tork[9]又將物料需求任務(wù)的截止時間衡量物料需求任務(wù)的緊急程度，并利用遺傳算法求解。Monghasemi等[10]認(rèn)為優(yōu)化物料需求任務(wù)的等待時間對實際建設(shè)產(chǎn)生的效果更好，并基于博弈論(Game Theory)與和聲搜索算法(Harmony Search)均衡了吊裝任務(wù)的等待時間。Huang等[11]利用混合整數(shù)線性規(guī)劃(Mixed-Integer Linear Programming，MILP)，將物料存儲位置和塔吊位置作為優(yōu)化模型的決策變量，并考慮了吊鉤的初始位置、吊機(jī)的運輸能力等因素，得到了CSSP問題的全局最優(yōu)解，極大地減少了塔吊運輸時間。

盡管MILP算法可以得到最優(yōu)解，但傳統(tǒng)的分支定界算法(Branch-and-Bound)求解時間會隨著問題規(guī)模的增大而呈指數(shù)趨勢增加，并且模型忽略了吊裝物料次序?qū)κ┕すば虻挠绊?。尤其以裝配式建筑為例，若模型忽略了施工順序?qū)?gòu)件吊裝順序的要求，則造成優(yōu)化后的調(diào)度方案不合理。例如，預(yù)制梁若在預(yù)制墻體安裝前被運輸?shù)轿锪闲枨簏c，則將導(dǎo)致工序無法搭接，引起構(gòu)件的二次運輸，造成運輸資源浪費。

因此，本研究在前人研究基礎(chǔ)上，針對裝配式構(gòu)件吊裝調(diào)度問題，基于MILP建立優(yōu)化模型。在考慮施工順序的前提下，優(yōu)化塔吊的吊運順序，減少塔吊吊裝構(gòu)件的運輸時間，并考慮吊鉤初始位置與物料供應(yīng)位置的影響。研究隨后設(shè)計一種改進(jìn)遺傳算法(Improved Genetic Algorithm)對優(yōu)化模型進(jìn)行求解，大幅減少求解時間，同時保證優(yōu)化結(jié)果的質(zhì)量，增強(qiáng)了整個優(yōu)化模型的工程實用性。

2 裝配式構(gòu)件吊裝調(diào)度模型構(gòu)建

2.1 塔吊運行時間估算模型

相關(guān)研究[8～11]采用了Zhang等[12]提出的簡化模型來估算塔吊在兩點間的運行時間。吊鉤運行軌跡分解為：吊臂的切向運動、吊鉤沿吊臂的徑向運動以及吊鉤的豎向運動，其中吊臂的切向運動與吊鉤的徑向運動組成了水平方向的運動。如圖2所示，當(dāng)物料供應(yīng)點、物料需求點以及塔吊位置坐標(biāo)已定的情況下，根據(jù)式(1)～(3)計算出三者之間的直線距離ρ(Si,Dj)，ρ(Si,Tck)，ρ(Dj,Tck)。

圖2 塔吊水平向運動

(1)

(2)

(3)

(4)

根據(jù)余弦定理，式(5)計算得到了吊臂的切向運動時間。

0≤arccos(·)≤π

(5)

(6)

圖3 塔吊豎向運動

(7)

(8)

2.2 裝配式構(gòu)件吊裝調(diào)度模型

2.2.1 參數(shù)與決策變量

(1)參數(shù)：αi,m∈{0，1}表示物料供應(yīng)位置i存儲有物料m；εr,j,m∈{0，1}表示物料需求任務(wù)r為需求位置j需要物料m；λj∈{0，1}表示吊鉤初始位置位于需求位置j。

(2)決策變量：xs,r∈{0，1}表示物料運輸任務(wù)r的執(zhí)行順序為s；δr,i,j,m∈{0，1}表示物料需求任務(wù)r的運輸路徑為由供應(yīng)位置i運輸物料m至需求位置j；ys,i,j,m∈{0,1}表示吊鉤在執(zhí)行順序s下將物料m由物料供應(yīng)位置i運輸至物料需求位置j；χs,j,m∈{0，1}表示吊鉤在執(zhí)行順序s下將物料m運輸至物料需求位置j；zs,j,i∈{0，1}表示塔吊在執(zhí)行順序s下的任務(wù)銜接路徑為由物料需求位置j至物料供應(yīng)位置i。

2.2.2 目標(biāo)函數(shù)

塔吊完成所有物料需求任務(wù)所花費的總時間為所有物料運輸路徑與任務(wù)銜接路徑之和計算所得，其表達(dá)式為：

(9)

式中：R為塔吊執(zhí)行任務(wù)總數(shù)；I為物料供應(yīng)位置總數(shù)；J為物料需求位置總數(shù)；M為物料種類總數(shù)；Ti,j為物料運輸時間；TUnloading為物料卸載操作時間；TLoading為物料裝載操作時間。

2.2.3 限制條件

(1)選擇物料供應(yīng)位置

式(10)限制了選擇的物料供應(yīng)位置必須存儲有需求任務(wù)所需要的物料種類。

(10)

若物料存儲位置i沒有存儲有物料種類m的構(gòu)件，即αi,m=0，則該存儲位置不能成為需求任務(wù)r(需要物料種類m)的備選供應(yīng)位置，即δr,i, j,m=0。式(11)限制了物料運輸路徑只選擇一個物料供應(yīng)位置。

(11)

(2)排序物料運輸任務(wù)

式(12)限制了塔吊每次運輸都完成一個物料需求任務(wù)；式(13)限制了每個物料需求任務(wù)必定會被滿足。

(12)

(13)

(3)確定執(zhí)行順序下的物料運輸路徑

式(14)表示了每個執(zhí)行順序下的物料運輸路徑。

2-xs,r-δr,i, j,m≥1-ys,i, j,m，

(14)

若物料需求任務(wù)r的執(zhí)行順序為s，即xs,r=1，且該物料需求任務(wù)r的運輸路徑為由供應(yīng)位置i運輸物料m至需求位置j，即δr,i, j,m=1，那么吊鉤在執(zhí)行順序s下將物料m由物料供應(yīng)位置i運輸至需求位置j，即ys,i, j,m=1。式(15)表示了每個執(zhí)行順序下的運輸目的地j以及運輸物料種類m；

(15)

(4)限制構(gòu)件運輸順序符合安裝順序

式(16)限制了同一物料需求點的物料運輸順序必須滿足裝配式構(gòu)件安裝次序。例如吊鉤在順序s將物料m運輸至需求位置j，即χs, j,m=1，在此后順序t(t>s)不能運輸施工順序靠前的物料u(m>u)，即χt, j,u=0。

(16)

式中：J*為存在多個物料需求任務(wù)的需求位置。物料種類序號與構(gòu)件安裝順序一致。

(5)確定執(zhí)行順序下的任務(wù)銜接路徑

式(17)表示了兩個物料運輸任務(wù)之間的銜接路徑。

2-χs, j,m-ys+1,i,o,u≥1-zs+1, j,i，

(17)

若吊鉤在順序s下將物料m運輸至需求位置j，即χs, j,m=1，而且吊鉤在順序s+1的物料運輸路徑為將物料u由物料供應(yīng)位置i運輸至需求位置o，即ys+1,i,o,u=1，那么吊鉤在順序s+1的任務(wù)銜接路徑為由需求位置j至物料供應(yīng)位置i，即zs+1, j,i=1。式(18)限制了任務(wù)銜接路徑最多只能選擇一個的物料供應(yīng)位置。

(18)

(6)根據(jù)吊鉤初始位置確定首個任務(wù)銜接路徑

式(19)表示了首個執(zhí)行順序的任務(wù)銜接路徑。

2-λj-ys=1,i,o,m≥1-zs=1, j,i，

(19)

若吊鉤初始位置在需求位置j，即λj=1，首個執(zhí)行順序的物料運輸路徑為將物料m由物料供應(yīng)位置i運輸至需求位置j，即ys=1,i,o,m=1，因此首個執(zhí)行順序的任務(wù)銜接路徑為由需求位置j至物料供應(yīng)位置i，即zs=1, j,i=1。式(20)限制了首個任務(wù)銜接路徑起始點為吊鉤初始位置。

(20)

3 裝配式構(gòu)件吊裝調(diào)度模型的求解

遺傳算法(Genetic Algorithm，GA)來源于進(jìn)化論和群體遺傳學(xué)[13]，是一種尋求全局最優(yōu)解的隨機(jī)并行搜索算法。由于具有較強(qiáng)的全局尋優(yōu)能力、魯棒性以及易用性，遺傳算法在工程優(yōu)化[14～6]領(lǐng)域得到了廣泛應(yīng)用。本文提出的遺傳算法對染色體編碼方式進(jìn)行了改進(jìn)，而且加入了染色體處理機(jī)制，考慮了構(gòu)件施工次序的限制。圖4顯示了改進(jìn)遺傳算法計算流程。

圖4 改進(jìn)遺傳算法計算流程

3.1 確定編碼方式

本文染色體編碼長度為2N(N為物料需求任務(wù)數(shù))，由兩部分組成：第一部分由N個物料需求任務(wù)的執(zhí)行順序組成，第二部分由選擇的N個物料供應(yīng)位置編號組成。以5個物料需求任務(wù)為例，如圖5所示，該染色體前5個基因為執(zhí)行順序，按照需求任務(wù)R3→R1→R5→R4→R2的順序完成；后5個基因為物料供應(yīng)點S位置，表示需求任務(wù)R1的供應(yīng)位置為S3，任務(wù)R2的供應(yīng)位置為S1，依此類推。

圖5 染色體基因組成

3.2 生成初始種群

由于塔吊物料運輸特殊性，因此需要保證生成的初始種群必須是可行的，即滿足式(10)～(13)的限制。因此，執(zhí)行順序基因段通過M次(種群數(shù)量)隨機(jī)生成N個(物料需求任務(wù)數(shù)量)不重復(fù)的正整數(shù)，即滿足式(12)(13)。良好的初始種群會加速尋優(yōu)的進(jìn)度，優(yōu)化模型的目的是尋求構(gòu)件吊運時間最短的調(diào)度方案。所以每個物料需求任務(wù)所匹配的供應(yīng)位置應(yīng)在滿足限制式(10)(11)的基礎(chǔ)上，若與需求位置的距離越近，則被選擇的概率越大。根據(jù)式(21)計算符合條件的物料供應(yīng)位置被選擇的概率Pb。

(21)

式中：Tb為符合條件的供應(yīng)位置與需求位置的運輸時間；B為符合條件的供應(yīng)位置總數(shù)；D為常數(shù)。

3.3 染色體處理機(jī)制

染色體處理機(jī)制是為了保證生成的染色體符合施工次序的要求，即滿足式(16)的限制。如上述所述，當(dāng)同一物料需求位置存在多個物料需求任務(wù)時，任務(wù)間的優(yōu)先級按照物料種類劃分。以預(yù)制構(gòu)件吊裝為例，物料吊裝順序為預(yù)制墻體→疊合梁→疊合板→樓梯，如果順序出現(xiàn)差錯，就會導(dǎo)致施工任務(wù)無法正常進(jìn)行。因此，染色體處理是在生成初始種群和新一代種群后，檢驗同一需求位置的不同需求任務(wù)的執(zhí)行順序是否滿足約束條件，如果不滿足則進(jìn)行調(diào)整。

3.4 計算個體適應(yīng)度

在遺傳算法中，適應(yīng)度用來衡量解的優(yōu)劣程度，同時也作為選擇算子執(zhí)行功能的依據(jù)。在計算適應(yīng)度前要將染色體解碼為問題的解，重新將遺傳算法空間映射到問題空間。本文的解碼操作為：(1)按照染色體中的供應(yīng)位置編號與物料需求任務(wù)所對應(yīng)的位置編號匹配，作為物料運輸路徑，即式(11)；(2)按照染色體中的執(zhí)行順序，將物料運輸路徑進(jìn)行排序，即式(14)；(3)按照排序好的物料運輸路徑，得到所有的任務(wù)銜接路徑，即式(17)～(19)；(4)計算該染色體對應(yīng)的目標(biāo)函數(shù)，即式(9)。在本模型中所對應(yīng)的目標(biāo)函數(shù)為物料運輸時間，物料運輸總時間越短，則代表了該調(diào)度方案越優(yōu)，其適應(yīng)度值越大。因此，適應(yīng)度ft按式(22)計算。

ft=D/Obj(t)

(22)

式中：D為常數(shù)；Obj(t)為個體的目標(biāo)函數(shù)值。

3.5 種群進(jìn)化

3.5.1 選擇算子與精英保留策略

本文采用輪盤賭法作為選擇算子，并以精英保留策略輔助種群的進(jìn)化。若個體的適應(yīng)度越大，則被輪盤賭法選擇的幾率越大，被保存至下一代種群的幾率越大。精英保留策略通過保留種群中適應(yīng)度最大的個體作為精英個體，在交叉算子與變異算子執(zhí)行完畢后，用精英個體替換適應(yīng)度最小的個體。因此保證了優(yōu)良個體的基因結(jié)構(gòu)不會被破壞。

3.5.2 交叉算子

為保證交叉后的染色體仍為可行的，本文使用自適應(yīng)交叉概率調(diào)節(jié)機(jī)制下的部分映射交叉(Partially-Mapped Crossover, PMX)和兩點交叉(Two-Point Crossover)作為交叉算子，并使用自適應(yīng)參數(shù)調(diào)整機(jī)制，根據(jù)個體的適應(yīng)度對交叉概率進(jìn)行調(diào)整[17,18]。式(23)表示若當(dāng)前個體的適應(yīng)度大于種群的平均適應(yīng)度，則表明當(dāng)前個體屬于較優(yōu)個體，為了保證其優(yōu)良的基因結(jié)構(gòu)不會被破壞，降低其交叉概率；若當(dāng)前個體的適應(yīng)度較小，則保持交叉概率不變，促進(jìn)該個體與其他個體的交叉，以期產(chǎn)生更好的個體，發(fā)揮全局尋優(yōu)的功能。

(23)

PMX算子針對執(zhí)行順序基因段進(jìn)行交叉操作，使子代個體的執(zhí)行順序不會出現(xiàn)重復(fù)或缺少。PMX算子要求隨機(jī)產(chǎn)生兩個交叉點，兩個父代個體交叉點之間確定一個匹配段，利用匹配段的基因建立映射關(guān)系，生成兩個子代個體。雙點交叉算子則針對供應(yīng)位置基因段進(jìn)行交叉。兩點交叉算子與PMX算子所產(chǎn)生的交叉點一致，通過交換父代個體中交叉點之間的基因段，產(chǎn)生子代個體新的基因段。如圖6所示，假設(shè)隨機(jī)產(chǎn)生的交叉點為2，4，PMX算子將兩個父代個體中2～4位置的基因匹配段建立映射關(guān)系：R1-R3，R4-R2，R5-R4，依次將父代P1中基因值R1-R3，R4-R2，R5-R4的順序互換，得到子代C1的執(zhí)行順序為R1-R3-R2-R4-R5；同理，交換父代P2的執(zhí)行順序，得到子代個體C2。雙點交叉也選擇2～4位置的基因為交換段S1-S2-S2，S2-S1-S3，互換父代個體P1，P2的交換段，得到子代個體C1，C2的物料供應(yīng)位置為S3-S2-S1-S3-S1，S2-S1-S2-S2-S3。

圖6 交叉算子示例

3.5.3 變異算子

本文為增強(qiáng)變異算子的局部搜索能力，采用了逆序變異算子、插入變異算子、交換變異算子和單點變異算子。執(zhí)行順序基因段的變異主要采用逆序變異算子、插入變異算子和交換變異算子。圖7描述了執(zhí)行順序基因段變異算子的操作過程。

圖7 執(zhí)行順序基因段的變異算子

供應(yīng)位置基因段的變異采用單點變異算子，而且為保證變異后個體的可行性，變異后的物料供應(yīng)位置必須存儲有對應(yīng)物料需求任務(wù)所需的物料類型。圖8描述了供應(yīng)位置基因段變異算子的具體操作。

圖8 供應(yīng)位置基因段的變異算子

3.6 終止條件

當(dāng)滿足預(yù)定的終止條件，則終止遺傳算法求解；若不滿足終止條件，則繼續(xù)染色體處理。本文設(shè)定的終止條件為達(dá)到最大迭代次數(shù)時，計算自動停止。

3.7 算法表現(xiàn)

本文采用5個算例對改進(jìn)遺傳算法的表現(xiàn)進(jìn)行了分析，算例的規(guī)模分別為5，10，15個物料需求任務(wù)。商業(yè)求解器Gurobi求得的解為該問題的全局最優(yōu)解，可作為GA算法表現(xiàn)的對比標(biāo)桿。GA中參數(shù)取值如下：最大交叉概率pmax=0.8，自適應(yīng)系數(shù)p=0.3，變異概率pmu=0.018，種群數(shù)量M為50，最大迭代次數(shù)為200次。對于每個算例，將GA在同樣的參數(shù)下計算20次，并取所有計算結(jié)果的平均值作為該算例的計算結(jié)果。實驗基于Python 3.6，計算平臺為Intel Core i5-8279U@2.4 GHz 16 GB RAM。

如表1所示，隨著優(yōu)化問題規(guī)模的擴(kuò)大，使用Gurobi求解該模型的時間呈指數(shù)型增長。特別地，算例5在計算超過7200 s后上下界仍未收斂，其結(jié)果為Gurobi求解器求得的上界。隨著問題規(guī)模的增大，精確算法的計算時間無法達(dá)到實際工程應(yīng)用的要求，而GA則可以在較短計算時間求得近似最優(yōu)解。

表1 Gurobi與GA的比較

4 案例分析

4.1 案例背景

研究應(yīng)用于北京某裝配式建筑施工場地，根據(jù)施工計劃選取了部分物料需求任務(wù)作為本文的案例。該項目采用的場地布置方案是根據(jù)場地建筑面積量、施工條件、工期以及成本等因素綜合考慮確定。塔吊位置與選型方案可以覆蓋整個施工作業(yè)面，并滿足構(gòu)件的起吊重量與吊裝任務(wù)量。在確定初始方案后，利用BIM(Building Informa-tion Modeling)技術(shù)分析了駕駛員的可視角度，確定了最終的塔吊位置，減少了駕駛員的盲區(qū)范圍，增強(qiáng)了吊裝過程的安全性。為了減少構(gòu)件吊裝時間，提升塔吊運輸效率，項目設(shè)置了多個物料供應(yīng)位置。依據(jù)施工場地及周邊空間條件、施工要求、管理人員經(jīng)驗，結(jié)合優(yōu)化算法和BIM技術(shù)的空間分析和可視化功能來制定，保證了吊裝過程的高效性。圖9為該施工場地的平面布置圖，場地布置了1個塔吊和4個物料供應(yīng)位置，物料供應(yīng)位置的詳細(xì)信息如表2所示。

圖9 場地平面布置

表2 物料供應(yīng)位置坐標(biāo)及存儲材料種類

案例中共有12個物料需求任務(wù)，分布于9個物料需求位置，物料運輸任務(wù)的詳細(xì)信息如表3所示。假設(shè)無緊急物料需求，即各物料需求點的優(yōu)先級一致。如上文所述，同一物料需求位置的不同物料需求任務(wù)應(yīng)該按照物料種類進(jìn)行排序，使其符合施工過程的要求。例如物料需求點D4所對應(yīng)的兩個需求任務(wù)為R1和R6，所需物料種類分別為M3(疊合板)和M4(樓梯)，為了施工作業(yè)的正常順序，應(yīng)當(dāng)在吊運并安裝物料M3后才能吊運物料M4，所以需求任務(wù)R6的執(zhí)行順序必然在任務(wù)R1之后。物料需求點D5和D6中存在同樣的情況。本案例的解共包含有827，714，764，800種組合，其中執(zhí)行順序有12!(479001600)種組合，供應(yīng)位置選擇有1728種組合。

表3 物料需求位置坐標(biāo)及吊裝任務(wù)信息

4.2 案例結(jié)果

圖10展示了GA的計算過程，優(yōu)化結(jié)果為62.38 min，計算用時4.32 s。同樣，將該案例使用Gurobi軟件求解MILP模型，優(yōu)化結(jié)果為62.38 min，計算用時6160 s。因此，本文提出的改進(jìn)遺傳算法具有良好的尋優(yōu)能力和工程實用性。

圖10 GA計算過程

表4給出了最優(yōu)調(diào)度方案，表中的第1列給出了物料運輸任務(wù)執(zhí)行順序，第3列與第4列給出了吊鉤運行的詳細(xì)信息，第5列為吊鉤運行時間，第6列為吊鉤的累積運行時間，包含吊鉤運行時間與裝、卸載物料的操作時間(設(shè)置為單位時間/1min)。由表4可知，需求任務(wù)R1和需求任務(wù)R6的執(zhí)行順序分別為1，2，滿足施工方案的要求。同樣地，需求任務(wù)R4，R12，R9，R11也都滿足此限制。

5 結(jié) 語

本文基于MILP算法構(gòu)建了一個裝配式構(gòu)件吊運調(diào)度優(yōu)化模型，并設(shè)計了一種改進(jìn)遺傳算法用于求解該問題。優(yōu)化調(diào)度結(jié)果可以為實際施工中塔吊調(diào)度方案提供參考，以期達(dá)到節(jié)省運輸時間、降低成本及提高施工效率的目的，同時也為工程機(jī)械自動化的實現(xiàn)提供新的思路。本研究取得的主要成果如下：

(1)建立了考慮吊鉤初始位置、物料供應(yīng)位置以及構(gòu)件安裝順序的裝配式場地塔吊調(diào)度優(yōu)化模型；

(2)通過改進(jìn)編碼方式和引入染色體處理機(jī)制，設(shè)計了一個新的改進(jìn)遺傳算法求解該優(yōu)化模型；

(3)通過遺傳算法與商業(yè)求解器的比較，驗證了改進(jìn)遺傳算法可以在較短時間內(nèi)將大規(guī)模問題求解，并得出近似最優(yōu)的調(diào)度方案。

但是該算法在面對求解任務(wù)規(guī)模大于15的調(diào)度問題時，依舊容易陷入局部最優(yōu)解，在未來的研究中應(yīng)當(dāng)加入新的擾動算子或結(jié)合其他優(yōu)化算法輔助跳出局部最優(yōu)解。并且，塔吊的運行時間估算模型是基于經(jīng)驗擬定的，而實際中塔吊運行的制約因素較多，因此在以后的研究中可以利用機(jī)器學(xué)習(xí)方法，提高塔吊運行軌跡與時間的準(zhǔn)確性。