基于NSGA-Ⅱ與BIM5D的工期-成本優化

王緒民， 王 琪

(湖北工業大學土木建筑與環境學院， 湖北 武漢 430068)

對于工期-成本優化問題，國內外學者主要從兩方面探討：1)求解算法的選擇。啟發式算法引入傳統生物學概念，相較于傳統數學方法具有更強全局把控性，為多目標優化問題提供新的思路。Kyung Kim等在蟻群算法上提出改進，以避免尋優效率低的問題[1-2]。Zalmai LM考慮確定性的項目值，采用和聲算法進行尋優[3]。申建紅選擇電子優化算法，引入精英檔案存儲，著重于尋找最優成本的最優工期[4]。盡管很多新算法被證明可以在工期-成本優化問題中得以運用，但難以滿足整個尋優過程中種群多樣性和穩定性。2)實施過程的優化。考慮到工期-成本優化問題是一個復雜度高且影響因素多的問題，簡單算法優化缺乏指導性和實踐性。BIM(Building Information Modeling)信息模型可視化功能可以彌補單一算法尋優的缺陷，為實際施工提供可行性指導。黃良輝建立基于BIM的成本優化信息模型，并采用微粒子群算法優化求解[5]。何威提出將遺傳算法和BIM碰撞技術結合，使優化方案更具實踐性[6]。Hyounseok Moon將遺傳算法和BIM環境結合，最大程度地減少高風險活動的重疊[7]。但以上研究對于BIM的應用還十分狹隘，僅停留在三維建筑層面，缺少對進度、成本信息集成和管理。

基于此，本文采用NSGA-Ⅱ算法進行求解，為擴大算法尋優搜索空間和提高收斂性，在進行遺傳操作時，引入動態交叉、變異概率，對NSGA-Ⅱ算法進行改進，使Pareto解集更具有效性。利用BIM5D信息集成化和三維可視化的特點，對求得的解集進行施工方案模擬，有效避免工序安排、資源安排以及資金安排不合理問題。

1 工期-成本優化數學模型

1.1 問題描述

工期和成本存在著一定制約關系，即縮短工期會引起成本增加，成本降低又會引起工期延長。這種以一個函數目標值降低來提高另一個函數目標值的問題被稱作多目標優化問題[8]，該問題又可以表示為圖論中最小點成本最短路徑問題(MCSP)，其有向圖如圖1所示。通過為每個工序確定持續時間，編制施工方案，在應急狀態和正常狀態中尋求一個平衡狀態，達到工期-成本的綜合最優。圖1中，每個工序由一個節點表示，其中該節點內英文字母表示該工序的編號。本文所研究的工期-成本優化問題目的在于尋找A節點到F節點的一種最短路徑，使所有節點成本達到最低。

圖 1 工期-成本優化有向圖

1.2 數據建模

為減少算法迭代次數，得到的最優解更加精確和客觀，需要在建立工期-成本優化模型時做相應假設：

假設一：不存在其他資源約束且各工序無返工問題。

假設二：工程項目施工組織設計方案已經確定，所涉及到計劃工期及成本目標確定，在完成所有工序之前，方案不會做出重大調整。

假設三：工序持續時間和成本具有一定函數關系。表1是本文所用符號的注解。

表1 符號解釋

工程項目成本主要由直接成本和間接成本構成，但考慮到投產階段工期對成本的影響，加入了工程竣工后的投產效益。采用非線性函數描述各成本要素和工序持續時間的關系。

1)直接成本 工程項目中一旦對工期進行調整，成本也會發生相應變化。加快施工進度同時，需要投入更多人工和機械設備。人工費和機械設備使用費是項目直接成本重要組成部分，即工序持續時間增加導致直接成本增加。但考慮某個工序所需投入的人材機總量是一定的，趕工費用并不會隨著工期增加而一直減少，因此直接成本的下降速度也會減緩。即：

C1i=C1imin+k1(Dil-Di)2

(1)

其中

2)間接成本 工程項目間接成本主要由稅金、管理費、辦公費等固定費用構成，與某個工序持續時間不具有明顯關聯性，可近似將單個工作日的間接費用視為固定值。

C2i=M*Di

(2)

其中

3)投產效益 單個活動工序持續時間越短，工期也相應加快，項目投產運行越早，產生的資金時間價值越大。

P=α(T-Tmax)

(3)

其中

綜上，成本與工序持續時間的關系可表示為：

Ci=C1i+C2i+P

(4)

建立數學模型式。目標函數(1)

MinC=∑Ci

(5)

目標函數(2)

MinT=∑Di

(6)

約束條件為

Die≤Di≤Dil

(7)

T≤Tmax

(8)

2 模型的求解與分析

2.1 改進NSGA-Ⅱ算法尋優模塊

NSGA-Ⅱ算法是一種引進精英策略、采用了擁擠度和擁擠度比較算子的快速非支配算法，能得到包含多組工期-成本序列的Pareto解集，是目前最常用的多目標遺傳算法之一。相較于傳統遺傳算法，降低了計算復雜程度，保留了種群多樣性，提高了結果精度。盡管該算法做了很大改進，但仍然存在搜索空間過小或尋優準確度不高問題。為避免該問題，本文在進行遺傳操作時引進動態交叉和變異概率對算法進行改進，并用Matlab軟件來實現。

2.1.1 改進的遺傳操作

1)遺傳操作的基本形式 遺傳操作中交叉和變異操作是產生新個體的主要方式[9]。交叉操作即將兩個父代染色體隨機進行交換，產生新個體，常見交叉方法有單點交叉和多點交叉，本文采用單點交叉。變異操作不同于交叉操作，是針對基因層面，通過隨機對個體中一個或幾個基因隨機進行更改，產生新個體。在進行交叉和變異操作時，通常采用一個固定概率值，以致于出現搜索空間過小或尋優準確度不高等問題。

2)改進的遺傳操作 針對上述問題，本文提出一種新方法，來提高傳統NSGA-Ⅱ算法速度和準確度。具體的交叉和變異策略如下：

第一，采用輪盤選擇方法對初始化種群進行選擇操作，產生n個變量X1-Xn。

第二，將選擇的變量根據Pc進行交叉操作，然后由X1-Xn變成X′1-X′n。

第三，將交叉產生的X′1-X′n根據Pv進行變異操作，產生子代X″1-X″n。

與傳統遺傳操作不同，新的交叉和變異策略中引進了兩個動態參數Pc和Pv，早期將Pc和Pv值設置為較大的值，大多數變量就有機會參與交叉操作，加強對搜索空間的探索，后期將Pc和Pv設置為較小的值，有利于在搜索后期將總體收斂到高適應性個體。其中，Pc和Pv的動態取值見下式：

(9)

其中，Pc應滿足條件0.2

(10)

其中，Pv應滿足條件0.001

2.1.2 算法流程及要點

1)初始化種群 從待分類的點中隨機選擇K個點作為問題的一個解并編碼為一個染色體。重復進行這個操作直到種群中所有個體全部被初始化。

2)非支配排序 假設種群中所有可以被支配個體的集合為Sp，個體被其他個體支配的數量為Np。首先，計算出每個個體的Sp和Np，將Np=0的個體組成F1。在Fi中對每個個體的Sp集合的個體滿足Np-1=0,則將該個體加入到Fi+1。以此類推，求得該種群中所有個體的Pareto等級。

3)遺傳操作 遺傳操作是算法中種群產生新個體的方式，主要通過選擇、交叉和變異。本文將根據改進的遺傳操作進行種群迭代。

4)擁擠度計算 擁擠度計算是NSGA-Ⅱ算法為解決局部最優問題在原有遺傳算法上做出的改善，基于前期非支配排序結果進行。假設將種群中首個個體和末端個體擁擠距離設置為無窮大，則第i個個體的擁擠距離為第i+1個個體的適應度值與第i個個體的適應值差值。

5)算法終止標準 迭代次數是否達到規定值是算法終止的標準。種群迭代過程就是個體不停進行遺傳操作，通過有限次數循環，尋找滿足限制條件的最優Pareto解集。

2.2 BIM模型

單一算法尋優僅在數學層面進行優化，并不是每組方案都符合實際施工情況。BIM5D技術在三維模型中加入工程項目進度信息和成本信息，相較于以往BIM技術，涵蓋信息更全面，整合度更高，便于進行全過程、多維度項目管理[10]。本文選擇廣聯達BIM5D平臺對Pareto解集對應的施工方案進行模擬，淘汰一部分不符合實際施工情況的方案，并通過比較各方案的資源安排，資金安排的均衡程度篩選出最優方案。具體步驟為：1)根據工程相關文件分析得到相應工期及成本數據; 2)編寫改進NSGA-Ⅱ算法程序，并將工期及成本數據導入，得到文件A; 3)將文件A中所對應的Project文件導入BIM5D;4)進行施工模擬，得出資金、資源曲線; 5)進行方案篩選，得出最優方案進行施工。具體操作如圖2所示。

圖 2 BIM-改進NSGA-Ⅱ算法尋優流程圖

3 案例分析

3.1 項目概況

某工程樓地上建筑面積46640.67 m2，地下建筑面積6995.01 m2，建筑高度32.40 m，其中地下一層，地上八層，結構類型為框架結構。通過對該工程項目合同文件和施工組織設計文件進行分析，工程樓主要分為A、B、C、D四個分區進行施工，并得到該工程項目在基礎施工階段和主體施工階段12項工序在正常施工和緊急施工狀態下的工期和成本，如表2所示。根據合同，該項目在這兩個階段的合同工期為242 d，間接成本總額為20.268萬元。

3.2 結果分析

3.2.1 改進NSGA-Ⅱ算法有效性分析為驗證算法改進的有效性和必要性，基于工程項目基本條件，應用改進算法與標準NSGA-Ⅱ算法進行對比，圖3和圖4為兩種不同算法在Matlab環境下運行得到的Pareto前沿圖。通過選擇固定任一目標函數值，對比另一目標函數數值發現改進NSGA-Ⅱ得到結果更優。例如當工期目標函數值(Objective 1)為275 d時，圖3中成本目標函數(Objective 2)為1325 萬元，而圖四為1360 萬元。結果表明相同工期條件下，改進NSGA-Ⅱ算法求得的方案比原始NSGA-Ⅱ算法求得的方案成本更低。

表2 研究數據

圖 3 改進NSGA-Ⅱ算法pareto前沿圖

圖 4 原始NSGA-Ⅱ算法pareto前沿圖

3.2.2BIM5D應用性分析BIM5D以改進NSGA-Ⅱ算法求得的Pareto解集為依據，進行施工工序及資金、資源曲線模擬，根據方案實施的合理性進行篩選。

1)施工工序模擬 施工方案工序模擬如圖5所示。通過對各個方案進行施工進度模擬，利用其可視化特點發現施工順序安排的沖突，篩選出能夠合理進行施工的方案。

圖 5 施工模擬動畫

2)資源曲線模擬 通過整合模型和進度信息，生成資源曲線，對各個時間段資源量安排狀況進行估計，圖5為施工方案資源模擬曲線。該方案2019年11月人工消耗量為9933.772 工日，預計單日人工容納量需達到300人，從作業空間角度考慮，該方案不合理。其次，人工消耗量曲線走勢陡峭，反映人工安排不均衡，容易出現大量滯工或人工緊缺現象。同人工曲線，水泥消耗量在2019年11月達到峰值13739.123 m3，超出倉庫可儲存水泥量，不利于節約空間資源。

3)資金曲線分析 資金曲線預測了施工方案每月使用資金當前值和累計值，用以比較每個方案資金使用情況。經過篩選，得到最優方案各項工序持續時間如表3所示，總工期為270 d，總成本為1333.71萬元，達到優化目標。

圖 6 資源曲線

圖 7 資金曲線

表3 最優方案工序持續時間 d

4 結束語

工期-成本優化是工程項目管理的重要內容，對于提升工程項目效益十分必要。本文的主要研究方法和結論如下

1)考慮投產效益對成本的影響，以工序持續時間為變量構建多目標優化模型，對以往的工期-成本數據模型進行了完善。

2) 通過引進動態交叉、變異概率，設計了一種改進NSGA-Ⅱ算法對工期-成本數據模型進行求解，提高算法的優化效果和優化速度。

3)利用BIM5D平臺對算法尋優得到的Pareto解集逐一進行模擬并篩選，彌補了單一算法尋優方案與實際施工不符的問題。

經過相關案例分析，改進NSGA-Ⅱ算法在尋優過程中收斂速度更快，具有很好的優化效果，BIM5D的信息模擬功能為施工方案提供了實踐性，同時為BIM技術在工程問題中的應用提供了新的思路。