基于NSGA-II算法的寒區(qū)河道清淤工程工期成本優(yōu)化

豐小華 FENG Xiao-hua

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

0 引言

近年來，隨著國家對環(huán)境治理的重視，河道綜合治理工程項目逐漸增多。河道綜合治理工程項目涉及水利、水運、環(huán)境、生態(tài)和城市景觀等多個領(lǐng)域，具有規(guī)模大、投資多、涉及面廣、工序多、周期長、技術(shù)復(fù)雜等特點，且受到當(dāng)?shù)貧夂颉⑹┕きh(huán)境和社會等非技術(shù)因素的影響，如何在諸多因素的影響下，組織安排好施工進度計劃與資金、機械及人員之間的投入是實現(xiàn)工程建設(shè)項目效益的關(guān)鍵。

施工工期和成本的優(yōu)化主要是通過建立優(yōu)化數(shù)學(xué)模型，求得在限定約束條件下的最優(yōu)解。河道綜合整治工程施工的工期-成本優(yōu)化屬于多目標(biāo)組合優(yōu)化問題，在保證工程可持續(xù)運行，各工序安全有序施工的同時，實現(xiàn)工期最短和成本最優(yōu)，達到提高施工企業(yè)經(jīng)濟效益的目的。

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

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

1 工程概況

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

2 工期-成本數(shù)學(xué)優(yōu)化模型的建立

2.1 優(yōu)化原理概述

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

2.2 目標(biāo)函數(shù)

以清淤施工工期最短，成本最低為優(yōu)化目標(biāo)，構(gòu)造如下目標(biāo)函數(shù)：

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

2.3 約束條件

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

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

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

3.1 算法原理

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

3.2 算法設(shè)計

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

圖1 NSGA-II算法的流程圖

4 工程實例

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

表1 伊通河北北段清淤施工相關(guān)參數(shù)

4.1 優(yōu)化目標(biāo)

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

4.2 優(yōu)化原理

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

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

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

圖2 工程項目施工成本的構(gòu)成

4.3 優(yōu)化結(jié)果

以表1中所列數(shù)據(jù)為基礎(chǔ)，應(yīng)用MATLAB軟件編制NSGA-II相關(guān)算法程序，最終所得優(yōu)化結(jié)果如圖3~圖5所示，工期成本綜合優(yōu)化的滿意解部分的結(jié)果見表2。

圖3 工期-迭代曲線

圖5 多目標(biāo)算法優(yōu)化得到的作業(yè)甘特圖

表2 工期-成本優(yōu)化計算結(jié)果（部分）

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

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

圖4 工期-成本權(quán)衡圖

5 結(jié)論

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