裝配式構件施工現場吊裝調度建模與優化

李文杰， 黃 春， 劉占省， 藺宏遠， 何 陽

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

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

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

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

1 裝配式構件吊裝問題分析

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

圖1 吊鉤運行路徑

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

盡管MILP算法可以得到最優解，但傳統的分支定界算法(Branch-and-Bound)求解時間會隨著問題規模的增大而呈指數趨勢增加，并且模型忽略了吊裝物料次序對施工工序的影響。尤其以裝配式建筑為例，若模型忽略了施工順序對構件吊裝順序的要求，則造成優化后的調度方案不合理。例如，預制梁若在預制墻體安裝前被運輸到物料需求點，則將導致工序無法搭接，引起構件的二次運輸，造成運輸資源浪費。

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

2 裝配式構件吊裝調度模型構建

2.1 塔吊運行時間估算模型

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

圖2 塔吊水平向運動

(1)

(2)

(3)

(4)

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

0≤arccos(·)≤π

(5)

(6)

圖3 塔吊豎向運動

(7)

(8)

2.2 裝配式構件吊裝調度模型

2.2.1 參數與決策變量

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

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

2.2.2 目標函數

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

(9)

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

2.2.3 限制條件

(1)選擇物料供應位置

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

(10)

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

(11)

(2)排序物料運輸任務

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

(12)

(13)

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

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

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

(14)

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

(15)

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

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

(16)

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

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

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

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由物料供應位置i運輸至需求位置o，即ys+1,i,o,u=1，那么吊鉤在順序s+1的任務銜接路徑為由需求位置j至物料供應位置i，即zs+1, j,i=1。式(18)限制了任務銜接路徑最多只能選擇一個的物料供應位置。

(18)

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

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

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

(19)

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

(20)

3 裝配式構件吊裝調度模型的求解

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

圖4 改進遺傳算法計算流程

3.1 確定編碼方式

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

圖5 染色體基因組成

3.2 生成初始種群

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

(21)

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

3.3 染色體處理機制

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

3.4 計算個體適應度

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

ft=D/Obj(t)

(22)

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

3.5 種群進化

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

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

3.5.2 交叉算子

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

(23)

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

圖6 交叉算子示例

3.5.3 變異算子

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

圖7 執行順序基因段的變異算子

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

圖8 供應位置基因段的變異算子

3.6 終止條件

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

3.7 算法表現

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

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

表1 Gurobi與GA的比較

4 案例分析

4.1 案例背景

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

圖9 場地平面布置

表2 物料供應位置坐標及存儲材料種類

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

表3 物料需求位置坐標及吊裝任務信息

4.2 案例結果

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

圖10 GA計算過程

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

5 結 語

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

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

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

(3)通過遺傳算法與商業求解器的比較，驗證了改進遺傳算法可以在較短時間內將大規模問題求解，并得出近似最優的調度方案。

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