基于NSGA-II算法的寒區河道清淤工程工期成本優化

豐小華 FENG Xiao-hua

（中鐵十七局集團第三工程有限公司，石家莊 050000）

0 引言

近年來，隨著國家對環境治理的重視，河道綜合治理工程項目逐漸增多。河道綜合治理工程項目涉及水利、水運、環境、生態和城市景觀等多個領域，具有規模大、投資多、涉及面廣、工序多、周期長、技術復雜等特點，且受到當地氣候、施工環境和社會等非技術因素的影響，如何在諸多因素的影響下，組織安排好施工進度計劃與資金、機械及人員之間的投入是實現工程建設項目效益的關鍵。

施工工期和成本的優化主要是通過建立優化數學模型，求得在限定約束條件下的最優解。河道綜合整治工程施工的工期-成本優化屬于多目標組合優化問題，在保證工程可持續運行，各工序安全有序施工的同時，實現工期最短和成本最優，達到提高施工企業經濟效益的目的。

隨著優化算法和計算機技術的發展，基于數學模型的多目標優化控制理論，特別是遺傳算法以計算速度快、容易求得最優解而在大型工程建設項目中得到廣泛應用。胡良明等[1]基于遺傳算法對農村供水管網進行了優化設計。游健[2]針對傳統大壩安全綜合評價指標算法的局限性，提出基于改進的遺傳算法建立大壩安全評價模型。李斌[3]以某實際水利工程為研究對象，基于多目標優化遺傳算法對工程工期，成本與質量優化的方法，驗證了該算法工程實際施工進度計劃優化中應用的可行性；李競克等[4]從投資最少，工期最短和最佳質量三個方面建立多目標工程施工進度目標函數，對某實際工程仿真，進一步驗證了多目標遺傳算法能較好地求解施工進度目標函數最優解，且能夠提供多種優化方案。劉東海等[5]以某高心墻堆石壩為例，運用遺傳和聲算法對其施工進度進行綜合優化，從而實現了工程質量，安全與施工進度的均衡安排。

基于以上分析，本文將改進的GA算法運用到河道清淤工程實例中，通過引入帶精英策略的非支配排序遺傳算法NSGA-II進行工期-成本的多目標優化和方案優選，實例應用表明本文方法的有效性與合理性，可為實際工程施工進度優化控制提供一定指導和借鑒。

1 工程概況

伊通河北北段南起四化閘，北至萬寶攔河閘，河道長度約13公里。通過現場調查研究，發現河道上游及支流來水水質較差為劣五類水質，周圍還存在多處點源污染、面源污染、內源污染匯入量大，同時全河段還存在不同程度的淤積情況，造成河道內大量底泥淤積的堆積，污染狀況的惡化，嚴重影響了周邊環境，給社會經濟、環境的可持續發展帶來嚴峻挑戰。

2 工期-成本數學優化模型的建立

2.1 優化原理概述

本文確定以河道清淤施工進度最快，施工成本最低為目標，以每個工序的工作持續時間和消耗的成本上下限為約束條件，建立一種基于多目標優化的數學模型，并采用多目標遺傳算法NSGA-II進行求解，實現河道清淤工程工期-成本的優化，從而盡可能的提高施工質量，加快施工進度，降低施工成本。

2.2 目標函數

以清淤施工工期最短，成本最低為優化目標，構造如下目標函數：

式中，T為優化工期；C為優化成本；i為工序；k為每個工序的選擇方案；xik為0-1二元決策變量；di為作業i的工作時間；Cd為間接成本。

2.3 約束條件

以各工序的持續時間和消耗的費用上下限為約束條件，建立如下約束方程：

式中，i為工序；k為每個工序的選擇方案；K為總方案的數量；xik為0-1二元決策變量；j為作業i的緊后作業；ti為作業i的工作開始時間；tj為作業的開始時間；IC為間接成本；di為i作業的工作時間；B為成本預算。

3 帶精英策略的非支配排序遺傳算法

3.1 算法原理

NSGA-II算法自2000年被Deb K等[6]提出以來，廣泛應用到工程的各個領域解決多目標優化問題，它是在遺傳算法實現選擇交叉變異的基礎上加入非支配排序，降低了計算非支配序的復雜度，擴大了采樣空間，以此保留種群中好的個體，利用適應度函數保持群體父代的多樣性，盡量縮短目標函數的個數。該算法的核心就是協調各個目標函數之間的關系，找到使得各個目標函數都盡可能達到期望值的最優解集。

3.2 算法設計

根據上節所描述的目標函數和約束條件，對于工期-成本多目標優化問題，一般情況下需要對算子進行設計。因組合方案多為非支配解，如果利用非支配排序的方法進行計算，計算效率極低還不利于算法收斂。本文在此以傳統遺傳算法為基礎，引入精英策略算子，擴大采樣空間，同時進行擁擠度和擁擠度比較算子計算，提高計算效率，加快算法收斂速度，提高算法的魯棒性，保證了計算結果的穩定性。NSGA-II算法的流程圖如圖1所示。其中gen為進化代數，N為種群數量。

圖1 NSGA-II算法的流程圖

4 工程實例

根據方格網布置勘探點，經計算，四化閘至萬寶閘段水利高程以上淤泥量約240萬m3，采用干式清淤+半干式清淤結合的方式，總體施工工序分為施工準備、施工圍堰、排水導流、淤泥開挖、淤泥倒運、外運處置、工程驗收等，計劃投資7600萬，工期365天。結合施工組織安排以及業主對現場的一些相關節點要求，同時綜合考慮進度、成本、工期要求，進行不同條件下的人員、設備、材料、機械的投入的推演，得到不同工期下的成本，形成表1所列的相關施工參數。

表1 伊通河北北段清淤施工相關參數

4.1 優化目標

優化問題三要素是決策變量、目標函數、約束，單目標和多目標和優化問題的不同之處是單目標的解是單一的是可明確的，得到的最終解能夠達到最值，而對于多目標優化，目標函數和約束條件可能存在多個共存，且相互之間會存在沖突，它的解并非唯一，無法直接比較優劣性，最優解是一組由眾多Pareto最優解組成的最優解集合，工期和成本在一定意義上就是相互矛盾的，要使兩者同時達到最優幾乎不存在，很難找到一個最理想的解。在面對實際的工程情況下，我們的決策方案要結合實際，不能脫離現實環境，因此最終求解的工期和成本不一定是最優，還要面臨很多實際存在一些問題，所以我們要合理的決策工期和成本之間的關系。針對伊通河北北段清淤施工問題，更是會受到諸多因素的影響，因此我們采用多目標優化數學函數，將工期最短，成本最低設定為優化的目標。

4.2 優化原理

對于本清淤工程項目的工期是各個施工工序所持續時間之和。在整個河道生態治理工程中，清淤工程是首當其沖的一個施工任務，是后續各項工程展開施工的基礎，其進展快慢將直接影響項目總工期。清淤工程的施工能直接解決淤泥引起的一系列環境問題，對于生態環境的治理能達到立竿見影的效果。我們希望用最短的工期完成清淤工程的施工，從而降低各種施工成本，創造更大的綜合經濟效益。

按照工程成本構成劃分，將河道清淤工程成本分解為直接成本和間接成本，直接成本包括人工費、材料費、施工機械使用費和其它費用等，間接成本包括施工管理成本和其它成本。

構成施工成本的各項工作內容，完成任務的工期越短，直接成本與之對應增加；間接成本則隨著工期的延長相應增加。工期和成本之間相互影響，互相制約，存在一定的聯系，直接費和工期呈現反比例關系，間接費和工期呈現正比例關系，因此兩者之間必存在一個點使得直接費和間接費之和達到最低谷，這就是我們要研究的工期和成本的優化，在實際施工中，如何通過合理的施工組織安排，配置資源，確定各工序的施工時間，從而找出工期和成本的均衡點。在構建的工期成本模型中，利用遺傳算法，進行非支配排序，對伊通河清淤施工的工序各個模式進行了篩選，在巨大的搜索空間內尋找這個最佳點，圖2中所示的A點即為要優化求解的點。

圖2 工程項目施工成本的構成

4.3 優化結果

以表1中所列數據為基礎，應用MATLAB軟件編制NSGA-II相關算法程序，最終所得優化結果如圖3~圖5所示，工期成本綜合優化的滿意解部分的結果見表2。

圖3 工期-迭代曲線

圖5 多目標算法優化得到的作業甘特圖

表2 工期-成本優化計算結果（部分）

從NSGA-II算法優化計算所得的工期-迭代曲線結果可知，在資源配置均衡條件下，工期隨著迭代次數的增加最終趨于穩定，說明該算法能搜索到工期的最小值。

圖4和圖5分別為工程-成本權衡圖和多目標算法優化得到的作業甘特圖。從工期成本的權衡圖可看出工期與成本二者之間呈反比，縮短工期則會引起費用增加，這個結論是符合工程實際情況的。從解得搜索效率可知，搜索空間中有56個可行解，NSGA-II算法能夠得到一系列分布均勻、多樣性較好的最優解集，最優解為工期315天，相比較計劃工期節省56天，優化后的成本為6801萬元，相比較計劃投資節約了11%費用。由此可見，運用NSGA-II算法進行河道清淤工程工期-成本的多目標優化求解，具有可觀的經濟效益和實用性。

圖4 工期-成本權衡圖

5 結論

本文將NSGA-II算法應用到河道清淤施工工期和成本優化中，優化結果符合工程實際，解決了工程的工期和成本的優化問題，NSGA-II算法的應用提高效率，同時也驗證了工期-成本均衡優化模型的合理性和可操作性，可為實際工程提供理論的依據和較好的指導作用。