基于遺傳-剩余矩形算法的裝配式預制構件堆場優化

金 睿，丁宏亮，沈西華，劉東海

(1. 天津大學水利工程仿真與安全國家重點實驗室，天津 300350；2.浙江省建工集團有限責任公司，浙江 杭州 310012)

隨著裝配式建筑的發展，預制構件在施工現場堆場的堆放優化問題隨之產生[1-2]。現場管理人員憑借經驗對預制構件堆放方案進行人工規劃，但經驗堆放方案往往優化程度低，導致構件的堆放缺乏整體性，影響吊裝效率；同時目前還存在對預制構件的信息化管理不足、構件信息不全和信息不可追溯等問題[3-4]。

預制構件在堆場的合理堆放問題，其實是在有限的空間內實現構件的優化排布，可通過優化排樣算法進行計算求解。常用的優化算法有遺傳算法、粒子群算法、貪心算法、模擬退火算法、蟻群算法等[5-7]。遺傳算法[8]是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，其特點是具有良好的全局尋優性能[9]。遺傳算法結合剩余矩形算法[10]、BL算法[11]、下臺階算法[12]、最低水平線算法[13-14]等排樣算法，可以有效求解矩形件排樣問題。劉海明等[13]通過改進最低水平線方法，并與基于分階段遺傳算子的遺傳算法相結合，共同求解矩形件排樣問題，其提出的優化算法能夠有效改善排樣效果，提高材料利用率。Charalambous等[10]提出一種剩余矩形算法，將板材可用區域不斷劃分為矩形塊并逐個排入矩形零件，以盡可能減少板材浪費。韓喜君等[15]利用遺傳算法并結合剩余矩形排樣算法求解矩形件正交排樣問題，實例驗證表明混合遺傳算法具有較高的準確性、有效性和可行性。然而，上述研究成果主要面向矩形件的排樣領域，用于提高排樣后材料的利用率，而預制構件的現場堆放還需考慮后續的吊裝成本，所以現有算法難以直接應用于預制構件在堆場的堆放排布問題。

本文采用遺傳算法和剩余矩形算法對預制構件堆場優化問題進行研究，建立優化模型并提出求解方法，并開發了堆場優化系統，為預制構件的現場堆放提供優化排布方案，以提高堆場管理水平，減少吊裝成本。

1 堆場優化數學模型

1.1 問題描述

預制構件在施工現場的堆放優化問題，本質上是在滿足構件堆放位置和堆放順序要求的情況下進行構件堆放，達到盡可能減少構件吊裝成本的目的。對于構件吊裝，塔吊單次往返時間包括掛鉤、就位、小車平移提升、大臂轉動和摘鉤返回下一吊的時間，塔吊工作距離越短則塔吊單次往返時間越少。而減少構建吊裝距離，可以減少塔吊小車平移提升和摘鉤返回下一吊的工作距離，從而減少塔吊單次往返的時間。當進行多次構件吊裝作業時可以節省大量時間，從而提高吊裝效率，降低構件的吊裝成本。因此，本文將堆場優化問題轉化成以構件吊裝距離最小為優化目標的數學問題，建立堆場優化數學模型。

按照構件是否可以堆疊，可分為：(a)不可堆疊的構件，如預制柱、預制外墻等；(b)可堆疊的構件，如疊合板、疊合梁、預制樓梯等。對于不可堆疊的構件，其在二維空間的優化排布問題其實就是求解在已知寬度的堆場上，使得吊裝距離最小、同時占用堆場長度盡可能小的堆放所有構件的方案。對于可堆疊的構件，可利用最小包絡矩形法先將堆疊的構件看成一個整體，形成最小包絡矩形集，再將問題轉化為不可堆疊的構件優化排布問題。

1.2 建模前準備

設堆場優化數學模型的堆場寬為W，長為L，堆場的面積足以排下所有的預制構件。要排的預制構件共有N個，構件i的高度為hi，寬度為wi。以堆場左下角為原點建立平面直角坐標系(圖1)，構件在堆場上的位置可以由該構件左下角和右上角的坐標完全確定，即第i個構件位置關系可以通過式(1)或(2)確定。

圖1 預制構件與堆場坐標示意圖Fig.1 Schematic diagram of precast components and yard coordinates

(1)

(2)

式中：xl,i——第i個構件左下角橫坐標；yl,i——第i個構件左下角縱坐標；xr,i——第i個構件右上角橫坐標；yr,i——第i個構件右上角縱坐標。

1.3 模型目標函數

求解在已知長和寬的堆場上堆放N個預制構件，在滿足構件堆放位置和堆放順序要求的情況下，使得構件吊裝距離最小，同時占用堆場長度盡可能小的方案。在堆場上堆放構件后，構件中心距離塔吊中心的距離之和為

(3)

式中：S——所有預制構件中心與塔吊中心距離之和，m；x0——塔吊相對于堆場的橫坐標；y0——塔吊相對于堆場的縱坐標。

1.4 約束條件

a. 預制構件在堆場堆放時不出界：

(4)

在構件堆放時，從左下角向右上角依次堆放，任一構件要滿足不出界的約束。

b. 預制構件坐標關系：

(5)

式中:ri——變量，取值0或1。當ri=1時表示構件i橫放，ri=0時表示構件i豎放。任一構件的位置完全由其左下角坐標和其擺放方式(橫放或豎放)決定，因此該構件坐標滿足上述約束關系。

c. 鄰接預制構件之間高度和寬度的限制條件：

(6)

式中：tij、sij——變量，取值0或1。構件i和j為任意2個構件，當sij=1時說明構件i在j的左側；當sij=0時說明構件i在j的右側；當tij=1時說明構件i在j的下方，當tij=0時說明構件i在j的上方。構件堆放時相鄰構件之間高度和寬度需滿足上述限制條件。

d. 預制構件位置不出現重疊：

sij+sji+tij+tji≥1 (i

(7)

為防止構件位置出現重疊，各構件之間必須滿足上或者下，左或者右的關系。

e. 各個變量的約束：

W、L、xr,i、yr,i、xl,i、yl,i≥0

(8)

1.5 可堆疊構件情況分析

對于可堆疊構件的堆放情況，每一堆構件就是一個堆區，采用最小包絡矩形法求得各堆區在堆場中的寬度和長度，組成新的矩形集，然后采用不可堆疊的構件優化數學模型進行求解。因此，在解決可堆疊構件優化排布問題前，需要對構件的堆疊順序和堆疊后形成的最小包絡矩形進行預處理。

首先將N個構件分堆，每堆構件可堆疊m層(m≤5)，則可分成n=[N/m]堆([]表示向上取整)。將每堆構件按照吊裝優先級進行排序，優先級較高的構件排在上面，得到構件從上到下的堆疊順序。

采用最小包絡矩形法，取各堆構件中高和寬的最大值生成最小包絡矩形，并形成最小包絡矩形集，矩形數為[N/m]，該矩形集中各矩形大小即代表各堆區大小。然后采用不可堆疊構件優化數學模型進行求解，得到優化方案。因此，對于可堆疊構件，構件吊裝距離最小的優化模型如下：

(9)

2 優化算法及堆放策略

采用遺傳算法結合剩余矩形算法，對優化模型進行Matlab編程[16]，求解在已知長和寬的堆場上堆放完N個預制構件，使得構件吊裝距離最小的方案。優化算法以吊裝距離的倒數為適應度函數，基本步驟見圖2。

圖2 優化算法流程Fig.2 Flow chart of optimization algorithm

第1步：導入所有待堆放構件的信息、堆場的尺寸(寬W，長L)、塔吊相對于堆場的位置坐標(x0，y0)。

第2步：識別現有堆場的堆放情況，確定待堆放構件在堆場中的可堆放空間(最低可堆放位置)。

第3步：設置遺傳算法參數，種群大小pop_size，每個染色體或個體的長度為chromo_size，最大代數G，交叉率Pc，變異率Pm。

第4步：采用十進制編碼，以排樣順序中的N個構件編號Ri對應wi的大小，產生w1、w2、…、wN序列編碼組成染色體，當wi>0時，判斷為豎放，否則為橫放。

第5步：種群初始化，隨機產生初始種群，獲得pop_size個染色體。

第6步：優化目標為吊裝距離最小，適應度函數取目標函數的倒數，計算種群適應度值fi=1/S。對個體適應度值升序排序，找出最優個體并保留。

為求解適應度值，需知道構件在堆場上的排布情況。使用剩余矩形算法，算法如下：(a)建立以W為橫軸、L為縱軸的直角坐標系，定義堆場的左下角為原點(0，0)，右上角坐標為(W，L)，得到初始矩形R1=[(0，0)，(W，L)]。(b)排入構件[(xl,i，yl,i)，(xr,i，yr,i)]，將剩余矩形集合中的每一個矩形都減去此矩形所占的位置，并記錄剩余矩形。(c)去掉面積為0或已無法排下所剩的任何一個構件的剩余矩形；把具有完全包含關系的剩余矩形中面積小的矩形去除，有相交關系的矩形全部保留，得到新的剩余矩形集。(d)向剩余矩形集中繼續排入構件，排放時選擇寬、高均大于等于待排放構件的剩余矩形。該剩余矩形是剩余矩形集中最低且最靠左的剩余矩形，以使待排放構件與剩余矩形的左下角重疊。排放完成后跳轉到c，直到N個構件全部排完。

第8步：重復驗算，達到預定的進化代數時結束，保存最佳個體。

編程求解該遺傳-剩余矩形算法后可以給出堆場優化數學模型的相對最優解，獲得構件堆放的優化方案。使用該算法求解堆場優化問題，具有以下特點：(a)由于構件在堆場的堆放是一個動態過程，因此在算法開始時設置堆場現狀識別功能以迅速確定可堆放空間；(b)始終保留最佳個體遺傳至下一代，避免最佳個體在計算過程中丟失；(c)快速獲得人工在短時間內難以得到的優化方案。

3 堆場優化系統

為實現遺傳-剩余矩形算法的轉化應用，并服務于項目現場構件的管理，在現有“浙江省建工集團工業化項目管理平臺”中進行二次開發，建立堆場優化系統。如圖3所示，該系統由系統輸入模塊、系統優化模塊和系統輸出模塊三部分組成。項目管理人員根據項目信息，采用該系統獲取堆場信息和所有構件編碼信息，從數據庫調取構件類型和構件尺寸等參數信息。系統通過編碼識別、數據提取、堆場分配過程，結合堆場信息對構件的堆放位置和堆放方式進行優化，然后由優化算法產生優化排布方案，管理人員將產生的優化排布方案進行評價并最終確認。最后這些數據由系統輸出模塊從前端展示，指導現場構件堆放。

圖3 預制構件堆場優化系統構成示意圖Fig.3 Schematic diagram of packing optimization system of precast concrete components

堆場優化系統前端界面如圖4所示，該界面展示了構件堆放的位置信息，選中某一構件后還可展示完整的構件屬性信息，如構件編號、構件類型、所屬狀態等。由此，現場和企業管理人員可以快速了解堆場和構件現狀，并使用該信息化的管理手段輔助項目管理。

圖4 堆場優化系統界面Fig.4 User interface of packing optimization system

堆場優化系統移動端如圖5所示，現場管理人員可對構件的進場和堆放進行管理。當預制構件到達現場通過質量驗收并點擊“確認”后(圖5(a))，系統會自動給出優化推薦的堆場(圖5(b))。選擇優化推薦的堆場后，則界面顯示該堆場的現狀(圖5(c))，同時待入庫構件的具體位置也可從移動端獲得，操作人員據此可將預制構件放入指定位置。在移動端查看堆場詳情時，根據構件編號可以直觀看到每個構件所在的堆場、堆區和層(圖5(d))，實現對構件的精確定位和管理。

圖5 堆場優化系統移動端Fig.5 Mobile terminal of packing optimization system

本文開發的堆場優化系統，將堆場優化數學模型和遺傳-剩余矩形算法成果應用于工程實際，經驗只是起輔助作用，復雜的計算和堆放方案由系統提供，人的作用只是判斷系統的優化方案是否合理與可行。利用該系統可提高現場工作效率，減少不必要的時間浪費，降低對經驗的依賴程度，實現降本增效的目的。現場工作人員能快速學會并使用該堆場優化系統，使建筑施工由粗放向精細化方向轉變。

4 系統應用分析

某房建工程樓板和樓梯采用預制裝配式混凝土建造。預制疊合板和預制樓梯與結構同步施工，垂直運輸機械采用塔吊吊運。通過吊運分析，各棟樓的預制疊合板均在塔吊輻射半徑以內，且吊運能力滿足預制疊合板的重量要求，因此全部采用塔吊進行吊裝。現需要在施工現場的堆場堆放預制構件，堆場為寬15 m、長30 m的矩形，堆場初始狀態為無構件堆放狀態，塔吊相對于堆場的坐標位置為(7.5，-9)，待堆放構件的尺寸信息見表1。

表1 構件及其吊裝優先級

目前，構件的現場堆放方案由管理人員人工規劃，在有限時間內所得的經驗方案優化程度低。根據經驗，一般需要對堆場情況和構件大小信息進行初步判斷，然后按照卸車順序對構件逐個堆放，因此管理人員需要對構件進行多次判斷并堆放，消耗時間多，吊裝效率低，堆放方案不能達到減少吊裝距離、節約吊裝成本的目的。

現采用堆場優化系統來指導構件的現場堆放。先將堆場、構件等信息導入系統。

a. 在考慮不可堆疊的情況下進行優化求解，可以快速得到優化后所有構件的堆放順序和堆放位置坐標。系統自動調用Matlab優化算法程序，并集成在工業化項目管理平臺中使用。圖6(a)為構件在堆場的堆放位置排樣。從圖6(a)可以看到每個構件的堆放方式和具體位置。在最優堆放方案下，塔吊最小工作距離為438.3 m。圖6(b)為經驗方案的模擬堆放圖，按照構件卸車順序在堆場堆放。從圖6(b)可以看到，采用經驗方案進行構件堆放，占用空間大，且該方案下的吊裝距離為486.2 m，增加的吊裝距離增加了吊裝成本。采用堆場優化系統得到的優化方案，使構件在堆場中可以合理排布，降低了對現場管理人員經驗的依賴性，同時減少了吊裝距離，提高了吊裝效率，降低了綜合成本。

圖6 不可堆疊情況下構件堆放位置排樣Fig.6 Layout of packing scheme under non-stackable condition

b. 在考慮可堆疊的情況下進行優化求解，得到優化后所有的最小包絡矩形在堆場中的排列順序和堆放位置坐標，自動繪制成預制構件堆疊圖，見圖7。從圖7(a)可以看出最優堆放方案下的構件排布方式，對于各最小包絡矩形，在最優堆放方案下塔吊最小工作距離為342.5 m。圖7(b)是經驗方案的模擬堆放圖，該方案是較優的經驗方案，在考慮各堆區中構件的吊裝順序后進行堆疊。從圖7(b)可以看出，構件在堆場所占用的堆場長度大于優化方案，同時，該方案下的吊裝距離為387.0 m，相比于優化方案，較多的吊裝距離增加了吊裝成本。

圖7 可堆疊情況下構件堆放位置排樣Fig.7 Layout of precast packing scheme under stackable condition

表2 構件的堆放順序

表2為構件在各堆區中從上到下的堆放順序，如堆區1代表第一堆構件，該堆區最小包絡矩形的寬和長分別為4.76 m和2.78 m，構件從上到下的堆疊順序按照吊裝優先級依次為8、14、15、23、28，這種堆疊順序確保了先吊裝構件在上層。在可堆疊情況下采用堆場優化系統得到的優化方案，考慮了構件的吊裝順序后進行合理堆疊，避免了吊裝過程中需要吊裝堆放在下層位置構件的情況，減少了吊裝距離，提高了吊裝效率，降低了管理成本，從而降低了綜合成本。

圖8為在不可堆疊和可堆疊工況下遺傳-剩余矩形算法迭代過程中各代最小吊裝距離和平均吊裝距離隨著迭代次數增加的收斂圖。從圖8(a)可以看出，在不可堆疊工況下，隨著迭代次數的增加，算法逐漸收斂。同時，算法在第50代和第68代時都跳出局部最優，找到更優的解并保持穩定，可以看出該算法在一定迭代次數后得到的結果是穩定準確的。圖8(b)顯示，由于在可堆疊情況下最小包絡矩形整體數量較少，算法迅速收斂并在迭代30代后最小吊裝距離和平均吊裝距離都基本保持穩定，證明該算法得到的結果也是穩定準確的。根據上述收斂情況，遺傳-剩余矩形算法不僅合理、可靠，而且收斂速度快，可求解得到滿足要求的相對最優解。

圖8 優化算法收斂曲線Fig.8 Iterative convergence curves of optimization algorithm

5 結 語

對于預制構件的現場堆放問題，本文提出了基于遺傳-剩余矩形算法的堆場優化數學模型及其求解方法，利用Matlab編程求解得到相對最優解，獲得構件堆放的優化方案。在工業化項目管理平臺上二次開發后形成堆場優化系統，應用于項目堆場管理后可以看出，該系統可以針對可堆疊和不可堆疊類型的構件進行優化，給出的優化方案使得吊裝距離最小，降低了對現場管理人員經驗的依賴程度，提高了現場工作效率，降低了堆放和吊裝綜合成本。該系統解決了對構件管理不足、構件在現場堆放無序等問題，實現了構件的管理信息化，助推裝配式建筑施工向智能化方向發展。