基于遺傳-剩余矩形算法的裝配式預(yù)制構(gòu)件堆場優(yōu)化

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

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

隨著裝配式建筑的發(fā)展，預(yù)制構(gòu)件在施工現(xiàn)場堆場的堆放優(yōu)化問題隨之產(chǎn)生[1-2]?，F(xiàn)場管理人員憑借經(jīng)驗對預(yù)制構(gòu)件堆放方案進(jìn)行人工規(guī)劃，但經(jīng)驗堆放方案往往優(yōu)化程度低，導(dǎo)致構(gòu)件的堆放缺乏整體性，影響吊裝效率；同時目前還存在對預(yù)制構(gòu)件的信息化管理不足、構(gòu)件信息不全和信息不可追溯等問題[3-4]。

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

本文采用遺傳算法和剩余矩形算法對預(yù)制構(gòu)件堆場優(yōu)化問題進(jìn)行研究，建立優(yōu)化模型并提出求解方法，并開發(fā)了堆場優(yōu)化系統(tǒng)，為預(yù)制構(gòu)件的現(xiàn)場堆放提供優(yōu)化排布方案，以提高堆場管理水平，減少吊裝成本。

1 堆場優(yōu)化數(shù)學(xué)模型

1.1 問題描述

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

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

1.2 建模前準(zhǔn)備

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

圖1 預(yù)制構(gòu)件與堆場坐標(biāo)示意圖Fig.1 Schematic diagram of precast components and yard coordinates

(1)

(2)

式中：xl,i——第i個構(gòu)件左下角橫坐標(biāo)；yl,i——第i個構(gòu)件左下角縱坐標(biāo)；xr,i——第i個構(gòu)件右上角橫坐標(biāo)；yr,i——第i個構(gòu)件右上角縱坐標(biāo)。

1.3 模型目標(biāo)函數(shù)

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

(3)

式中：S——所有預(yù)制構(gòu)件中心與塔吊中心距離之和，m；x0——塔吊相對于堆場的橫坐標(biāo)；y0——塔吊相對于堆場的縱坐標(biāo)。

1.4 約束條件

a. 預(yù)制構(gòu)件在堆場堆放時不出界：

(4)

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

b. 預(yù)制構(gòu)件坐標(biāo)關(guān)系：

(5)

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

c. 鄰接預(yù)制構(gòu)件之間高度和寬度的限制條件：

(6)

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

d. 預(yù)制構(gòu)件位置不出現(xiàn)重疊：

sij+sji+tij+tji≥1 (i

(7)

為防止構(gòu)件位置出現(xiàn)重疊，各構(gòu)件之間必須滿足上或者下，左或者右的關(guān)系。

e. 各個變量的約束：

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

(8)

1.5 可堆疊構(gòu)件情況分析

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

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

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

(9)

2 優(yōu)化算法及堆放策略

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

圖2 優(yōu)化算法流程Fig.2 Flow chart of optimization algorithm

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

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

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

第4步：采用十進(jìn)制編碼，以排樣順序中的N個構(gòu)件編號Ri對應(yīng)wi的大小，產(chǎn)生w1、w2、…、wN序列編碼組成染色體，當(dāng)wi>0時，判斷為豎放，否則為橫放。

第5步：種群初始化，隨機(jī)產(chǎn)生初始種群，獲得pop_size個染色體。

第6步：優(yōu)化目標(biāo)為吊裝距離最小，適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù)，計算種群適應(yīng)度值fi=1/S。對個體適應(yīng)度值升序排序，找出最優(yōu)個體并保留。

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

第8步：重復(fù)驗算，達(dá)到預(yù)定的進(jìn)化代數(shù)時結(jié)束，保存最佳個體。

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

3 堆場優(yōu)化系統(tǒng)

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

圖3 預(yù)制構(gòu)件堆場優(yōu)化系統(tǒng)構(gòu)成示意圖Fig.3 Schematic diagram of packing optimization system of precast concrete components

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

圖4 堆場優(yōu)化系統(tǒng)界面Fig.4 User interface of packing optimization system

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

圖5 堆場優(yōu)化系統(tǒng)移動端Fig.5 Mobile terminal of packing optimization system

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

4 系統(tǒng)應(yīng)用分析

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

表1 構(gòu)件及其吊裝優(yōu)先級

目前，構(gòu)件的現(xiàn)場堆放方案由管理人員人工規(guī)劃，在有限時間內(nèi)所得的經(jīng)驗方案優(yōu)化程度低。根據(jù)經(jīng)驗，一般需要對堆場情況和構(gòu)件大小信息進(jìn)行初步判斷，然后按照卸車順序?qū)?gòu)件逐個堆放，因此管理人員需要對構(gòu)件進(jìn)行多次判斷并堆放，消耗時間多，吊裝效率低，堆放方案不能達(dá)到減少吊裝距離、節(jié)約吊裝成本的目的。

現(xiàn)采用堆場優(yōu)化系統(tǒng)來指導(dǎo)構(gòu)件的現(xiàn)場堆放。先將堆場、構(gòu)件等信息導(dǎo)入系統(tǒng)。

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

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

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

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

表2 構(gòu)件的堆放順序

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

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

圖8 優(yōu)化算法收斂曲線Fig.8 Iterative convergence curves of optimization algorithm

5 結(jié) 語

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