周國華，馬依婷

(西南交通大學 經(jīng)濟管理學院，四川 成都 610031)

近年來，為深入貫徹黨的十九大作出的建設交通強國重大決策部署，我國鐵路路網(wǎng)規(guī)模持續(xù)擴大，投資力度不斷增強[1]。面對如此大規(guī)模、高投資的鐵路建設項目，科學高效的項目管理是保障鐵路建設工程高質(zhì)量發(fā)展的關鍵。因此，研究鐵路項目的工期費用優(yōu)化問題至關重要。

因項目中各活動不斷重復進行，鐵路項目在建設工程領域被稱為重復性項目?，F(xiàn)有研究指出傳統(tǒng)計劃方法對于重復性項目的不適用性，并提出了針對重復性項目設計的調(diào)度方法和技術。其中，最具代表性的是重復性調(diào)度法(repetitive scheduling method，RSM)[2]。RSM方法利用二維坐標呈現(xiàn)出項目的時間進度和空間進度，能夠較好地滿足重復性項目對資源連續(xù)性的要求，具有更強的生動性、可讀性，對鐵路項目具有獨特的適用性[3]。

重復性項目時間費用權(quán)衡問題 (time-cost tradeoff problem with repetitive projects,TCTPRP) 是一類離散時間費用權(quán)衡問題 (discrete time-cost tradeoff problem,DTCTP)，屬于NP難問題[4]。因此，目前大多數(shù)研究已應用諸如遺傳算法等智能算法來解決TCTPRP問題。Hyari等[5]依據(jù)Pareto原理提出能夠同時最小化工期和費用的遺傳算法；Long等[6]把費用和工期整合到一個目標函數(shù)，設計遺傳算法求解；相似地，王偉鑫等[7]以效用函數(shù)將工期費用整合為一個目標函數(shù)，設計滿足軟邏輯關系約束的云遺傳算法；張立輝[8]和Huang等[9]提出采用三段式整數(shù)編碼和雙層交叉算子的遺傳算法，通過horizon-varying方法得到了Pareto曲線；Shahriari等[10]和Heravi等[11]使用多目標算法同時對工期和費用進行優(yōu)化。

相較一般重復性項目，鐵路項目施工里程較長，涉及到的活動類型更復雜，往往存在逆向施工線性活動 (如架梁)、條狀活動 (如深水橋梁基礎、橋塔)、塊狀活動 (如長大隧道) 等特殊活動。因此，考慮多種活動類型，拓展施工場景，能夠提高模型對于鐵路項目的適用性。然而，目前幾乎所有TCTPRP研究均將研究對象聚焦于正向施工線性活動。劉仍奎等[3]雖然在模型中考慮條狀活動和逆向施工線性活動，但是未考慮與項目不同方面相關的若干成本要素，并且缺少可行的智能算法進行求解，無法實現(xiàn)大規(guī)模鐵路項目優(yōu)化。

綜上所述，本文的主要研究貢獻體現(xiàn)在以下兩點。1) 在模型方面，現(xiàn)有研究僅考慮了正向施工線性活動，施工場景單一，雖然簡化了求解過程，但是降低了模型對鐵路項目的適用性。針對鐵路項目施工計劃優(yōu)化在施工場景及約束表達等方面存在的欠缺，本文基于RSM完善鐵路施工計劃方法的數(shù)學表達和約束體系，在傳統(tǒng)重復性項目時間費用優(yōu)化問題的基礎上增加對于條狀活動、塊狀活動、逆向施工線性活動的優(yōu)化，以總工期最短和總費用最低為目標建立考慮多模式的多目標優(yōu)化模型。2) 在算法方面，現(xiàn)有文獻尚未針對包含特殊活動的大規(guī)模鐵路項目提出智能優(yōu)化算法，為填補這一空缺，本文提出適用于鐵路項目的改進NSGA-II算法。首先，針對鐵路項目特征設計活動調(diào)度流程；然后，為提高算法尋優(yōu)能力，設計均勻進化的精英選擇策略，并引入差分進化算法的變異、交叉算子，構(gòu)造出分層多策略自適應的變異、交叉算子；最后，用一個算例驗證模型的合理性和算法的有效性，并通過與傳統(tǒng)NSGA-II對比，證明改進后的算法性能更加優(yōu)越穩(wěn)定。

1 問題描述

一個鐵路項目中有I個活動J個單元。各活動在施工范圍內(nèi)具有重復性特征，即相同活動在不同施工單元內(nèi)重復進行?；赗SM框架，項目中包含線性、塊狀和條狀活動。線性活動在施工范圍內(nèi)連續(xù)施工 (如無砟道床、架梁)；條狀活動在一個固定里程點進行施工 (如深水橋梁基礎、橋塔)；塊狀活動在一段固定區(qū)間內(nèi)進行施工 (如長大隧道、特殊結(jié)構(gòu)橋梁)。其中，線性活動可逆向施工或正向施工，逆向施工指從項目終點方向向起點方向施工，反之，即為正向施工。

本問題包含以下關鍵決策：1) 線性活動施工方向；2) 各活動各單元施工模式；3) 各活動開工時間和結(jié)束時間。

1.1 基本假設

1) 活動間優(yōu)先關系為“開始-開始”型、“結(jié)束-結(jié)束”型、“結(jié)束-開始”型和“開始-結(jié)束”型；

2) 線性活動在各單元間連續(xù)施工，且在全施工段落內(nèi)僅能選擇一個施工方向;

3) 各活動施工模式可選，在同一單元內(nèi)只能選擇一種施工模式。

1.2 符號定義

本文符號定義如表1所示。

表1 符號定義Table 1 Symbol definitions

決策變量定義如下。

2 數(shù)學模型

2.1 目標函數(shù)

1) 項目總工期最短。

項目總工期D為第1個活動開始時間到最后1個活動結(jié)束時間，目標函數(shù)如下。

2) 項目總費用最低。

項目總費用由直接費用 DC和 間接費用 IC組成，其中直接費用包括人工費用、材料費用和設備費用，間接費用為間接費用率和工期的乘積。目標函數(shù)如下。

2.2 約束分析

由于模型考慮了逆向施工線性活動、條狀活動和塊狀活動，因此各個活動之間的時間約束可以根據(jù)緊前關系、施工方向及活動類型分為多種場景。本文基于RSM法，針對可能出現(xiàn)的情況構(gòu)造相應的約束。

1) 首日施工約束。

保證項目第一個活動的開始時間為0。本文以活動i的緊前活動集合Pi為空作為判斷活動i為首日施工活動的依據(jù)。

2) 施工連續(xù)性約束。

重復性項目通常需要施工人員在各個單元間頻繁移動，重復進行相同的工作。保持工作連續(xù)性能夠提高人員工作效率、減少閑置費用[10]。因此，為保證各活動在施工過程中不發(fā)生間斷，作如下約束。

3) 最小時間間隔約束。

根據(jù)本文提出的假設，活動間的時間間隔約束包含多種類型，具體約束類型需根據(jù)相鄰活動的活動類型、施工區(qū)段來確定。由于條狀活動可以看成一個跨度為0的塊狀活動 (bi=ei)，因此本文主要分析線性活動和塊狀活動之間的約束關系?；顒觔與其緊前活動a之間的最小時間間隔約束如下 (圖1為最小時間間隔示意圖，具體時間和里程的單位還需要根據(jù)具體工程項目確定)。

圖1 活動間最小時間間隔約束Figure 1 Minimum time interval constraints between activities

當活動a和活動b均為線性活動時 (對應圖1中場景1～ 4)，

當活動a為線性活動，活動b為條狀活動時 (對應圖1中場景5～ 6)，

當活動a為塊狀活動，活動b為線性活動時 (對應圖1中場景7～ 8)，

當活動a、活動b為塊狀活動時 (對應圖1中場景9) 。

4) 施工模式約束。

每個活動在各單元僅能采取一種施工模式。

5) 優(yōu)先關系約束。

優(yōu)先關系描述的是同一個單元中不同活動的施工先后順序，優(yōu)先關系約束要求任意活動i必須在其緊前活動全部結(jié)束后才能開始。

3 基于NSGA-II的算法設計

本文研究的問題屬于NP難問題，因此選擇帶精英策略的非支配排序遺傳算法 (non-dominated sorting genetic algorithm II，NSGA-II) 進行求解[12]。在標準NSGA-II的基礎上，根據(jù)問題的特點開發(fā)了調(diào)度流程，并對遺傳操作進行了改進，使新算法能夠適用于大規(guī)模鐵路進度計劃優(yōu)化。

3.1 染色體編碼

染色體采用自然編碼方式，隨機生成初始種群。染色體第1部分表示施工模式ki,j，當工作量為零時 (Qi,j=0)，施工模式為0；反之，則在當前活動對應的施工模式集合Ki中隨機選取。第2部分表示線性活動的施工方向ci，0為逆向施工，1為正向施工。染色體結(jié)構(gòu)如圖2所示。

圖2 染色體編碼方式Figure 2 Chromosome coding

3.2 適應度值

算法采用基于目標函數(shù)的非支配排序和擁擠度排序的適應度賦值策略，目標函數(shù)計算過程如下。

1) 工期計算。

通過調(diào)度流程計算得到各活動在各單元的開工時間Si,j、完工時間Fi,j和項目工期D。具體流程如下。

步驟1計算最早開工時間 ESi,j和最早完工時間EFi,j。首先根據(jù)施工模式計算各活動各單元的工期di,j，然后假設所有活動均在第0天開工，依據(jù)式(6)～ (7) 計算各子活動滿足工作連續(xù)性的E Si,j和EFi,j。此時，根據(jù)首日開工約束，可直接依據(jù)式 (3)～(5) 得到首日開工活動Si,j和Fi,j。

步驟2計算最大推遲時間 MAXi，即各活動為滿足與其緊前活動的最小時間間隔約束，需要在ESi,j、EFi,j的基礎上往后推遲的時間。如圖3所示，首先依據(jù)式 (8)～ (14) (不同場景的計算方式不同)，計算各單元節(jié)點處滿足最小時間間隔約束的最早施工時間tlogic[b,j]，然后計算各單元節(jié)點推遲時間 ?b,j，取最大值作為 MA。根據(jù)優(yōu)先關系約束，當活動b存在多個緊前活動時，依次計算針對各緊前活動a(a∈Pb) 的M A，選取其中最大值作為M AXb。

圖3 活動調(diào)度過程圖Figure 3 Activity scheduling process diagram

步驟3計算各活動各單元最終開始時間Si,j和結(jié)束時間Fi,j。各活動在最早開工時間 ESi,j和最早完工時間E Fi,j的基礎上推遲M AXi，得到Si,j、Fi,j、D。

以圖1中場景1為例的活動調(diào)度流程偽代碼如下。

2) 費用計算。

根據(jù)給定的任意施工方案，計算直接費用和間接費用。計算方法見式 (2)。

3.3 改進均勻進化精英選擇策略

標準NSGA-II通過擁擠度和非支配排序，運用錦標賽法選擇1/2的個體進入下一代[12]。為了保證種群對解的空間的充分探索，提高算法收斂性，本文將其改進為：前期在各支配層均抽取一定數(shù)量的個體，對各支配層由低到高選擇種群個體數(shù)量依次遞減，隨著迭代次數(shù)的增加，選擇個體的范圍逐漸縮減，直到迭代至最后選取種群前1/2個體進入下一代。每一代選取個體數(shù)量的計算方式如式 (17)～ (18) 所示。

其中，r popr,g為從第g代第r個支配層選取的個體數(shù)量；npopg為第g代可選取的個體數(shù)量；θ為縮減比例，設置為0.8；Ng為第g代可選取的支配層級總數(shù)；pop為 種群規(guī)模；G為最大迭代次數(shù)；g為當前迭代次數(shù)；e表示自然對數(shù)函數(shù)的底數(shù)。

3.4 改進分層多策略自適應變異、交叉算子

NSGA-II采用了遺傳算法的交叉、變異方式，在一定程度上降低了算法的收斂速度和效率。為提高算法性能，本文將差分進化算法 (differential evolution,DE) 的變異、交叉算子引入NSGA-II中。DE已被證明在大多數(shù)基準測試中，其性能優(yōu)于遺傳算法、自適應模擬退火和粒子群優(yōu)化等算法[13]。

1) DE算法的變異、交叉算子。

差分進化算法利用N維向量表示一個種群Xg=[x1,g,x2,g,···,xpop,g]。目前常見的3種變異算子Rand/1、Best/1、Current to best/1，其變異方式為

其中，V為變異因子；xp1,g、xp2,g、xp3,g為從第g代種群中隨機選擇的3個個體，且p1 ≠p2 ≠p3；xbest,g為從第g代優(yōu)秀個體中隨機選擇的個體，本文選取排序后種群的前10%作為優(yōu)秀個體。Best/1傾向于探索能力，Rand/1傾向于開采能力，Current to best/1能夠兼顧兩種特性。變異因子V值越大，種群變異的步長越大，有利于提高種群多樣性，增強全局搜索能力。V越小則開采能力越好，局部搜索能力越強。

交叉方式表示為

2) 多策略自適應變異、交叉算子。

為了平衡整個種群的開采能力和探索能力，本文依托上述變異算子的不同特性，設計了一種分層次、多策略、自適應的變異策略，來實現(xiàn)搜索能力的互補。首先，將種群根據(jù)支配等級和擁擠度排序等分為3層：精英層、普通層、劣勢層，然后針對不同層次選取不同的變異策略和參數(shù)控制因子。

針對精英層，主要需要保持當前個體的優(yōu)勢，同時增強其局部探索能力，因此選擇策略Best/1，設置V=0.8，C R=0.9。

針對普通層，主要目的在于探尋一些有潛力的解，進而增強種群的全局搜索能力，避免種群陷入早熟收斂，因此選擇Rand/1，設置V=1.2，C R=0.8。

針對劣勢層，其適應度較差，一方面應使其向優(yōu)秀個體的方向進化，同時在一定程度上避免其陷入局部最優(yōu)，因此選取策略Best/1、Rand/1混合使用，同時設置自適應參數(shù)。策略表示為

其中，αi為當前第i個個體對應的擁擠度。隨著迭代次數(shù)不斷增大，V、CR減小，加快種群收斂；同時引入擁擠度α，α較小時，當前個體周圍解較為密集，此時提高V、CR有利于跳出局部最優(yōu)，相反α較大時，適當降低V、CR以提高探索能力。

3.5 改進NSGA-II 算法框架

綜上，具體計算步驟如下。

步驟1根據(jù)染色體編碼規(guī)則生成種群規(guī)模為pop的初始種群。

步驟2依據(jù)活動調(diào)度和費用計算規(guī)則，計算各方案S適應度值。

步驟3進行非支配排序并計算擁擠度，依據(jù)均勻進化精英選擇策略，選擇p op/2個個體作為父代種群。

步驟4依據(jù)分層多策略自適應變異、交叉因子進行變異、交叉操作，得到子代種群。

步驟5合并父代種群和子代種群，得到合并種群，計算所有個體的適應度值，執(zhí)行選擇操作，得到下一代父代種群。

步驟6判斷是否達到最大迭代次數(shù)G，若是，篩選得到非支配解集，算法結(jié)束；若否，轉(zhuǎn)至步驟4。

4 實例分析

4.1 實例數(shù)據(jù)

某鐵路工程十標段DK404+867～ DK432+908全長28 km，施工范圍劃分為6個單元，各單元起點分別為DK404+867、DK408+936、DK415+210、DK419+072、DK424+100、DK428+595。該項目中包含27個活動，各活動基本信息如表2所示，施工模式及費用信息如表3所示。對于鐵路工程中的橋隧工程，由于其施工量和施工技術難度的限制，其施工工期基本固定，因此在表2中直接給出了工期數(shù)據(jù)，在表3中省略了施工速率。項目間接費用率為24 000 元/d。

表2 活動基本信息Table 2 Basic information of activities

表3 活動各施工模式速率及費用率Table 3 Rates and cost rates of various construction modes of activities

4.2 優(yōu)化方案

利用改進的NSGA-II算法，采用Matlab2016b實現(xiàn)，在操作系統(tǒng)為Windows10，處理器為Intel Core i5-8250U，CPU主頻為1.80 GHz的環(huán)境下運算，取種群數(shù)量 pop=90，迭代次數(shù)G=900，得到7個工期-費用權(quán)衡最優(yōu)的進度計劃方案S1～ S7，各方案對應的項目總工期和總費用如表4所示。

表4 Pareto解集Table 4 Pareto solution set

由圖4可知，本文提出的模型和算法在一次運行中自動生成構(gòu)成Pareto前沿 (pareto front，PF) 的所有可能的非支配解，確保了對解空間的充分探索。相較于將工期-費用均衡綜合為一個目標函數(shù)，最后生成一種施工方案，本文提出的方法能夠獲得更加豐富的工期-費用最優(yōu)方案，使決策者能夠根據(jù)需求從中選取合適的方案。例如，若唯一的優(yōu)化目標是工期最小化，則方案S1將是最佳方案，該方案工期最短，總工期為976 d，但對應最高費用647 021.6萬元；若優(yōu)先考慮費用因素，則應選擇方案S7，該方案的總費用646 997.6萬元，對應最長工期1 006 d。表5和表6為方案S1的具體施工方案，表5中的數(shù)據(jù)表示“ (開工時間，完工時間) 施工模式”。圖5為對應的進度計劃圖。

圖4 總工期-總費用Pareto曲線Figure 4 Pareto curve of total costs with the construction periods

圖5 S1進度計劃圖Figure 5 Schedule diagram of S1

表5 S1線性活動施工方案Table 5 Linear activity construction scheme of S1

表6 S1條塊活動施工方案Table 6 Strip and block activity construction scheme of S1

4.3 算法性能比較分析

本文選擇綜合指標超體積 (hyper-volume，HV)作為評價指標，反映算法的收斂速度、PF的均勻性和寬廣性等。HV計算的是參考點和PF構(gòu)成的不規(guī)則圖形的面積，HV越大，則所獲得的PF越接近真實PF[14]。

為進一步測試本文提出算法的優(yōu)化性能，本文將產(chǎn)生不同規(guī)模的算例，對算法進行更深入的分析。本文按照以下步驟隨機生成算例。

步驟1確定問題的規(guī)模，主要為項目活動個數(shù)I與施工單元數(shù)目J;

步驟2隨機生成任意活動i的相關參數(shù)，包括表2、表3所列數(shù)據(jù)。

本文對于不同規(guī)模的4組算例分別使用NSGAII和本文算法以相同種群規(guī)模、迭代次數(shù)及運行環(huán)境進行求解。表7為兩種算法獨立運行25次所得到的實驗結(jié)果，其中，HV平均值反映了求解精度，HV方差反映了算法穩(wěn)定性。可見，改進后的算法得到的PF分布更均勻?qū)拸V，具有良好的穩(wěn)定性。

表7 不同規(guī)模各算法獲得HV平均值及標準差Table 7 The mean and standard deviation of HV obtained by various algorithms of different scales

將不同規(guī)模下各算法獨立執(zhí)行 25 次所獲最大HV時對應的HV收斂曲線進行對比，如圖6所示，可得本文算法收斂速度更快，且針對較大規(guī)模的算例仍能保持良好的收斂性。

圖6 不同規(guī)模各算法HV進化過程Figure 6 Evolution process of HV with various algorithms at different scales

5 結(jié)論

本文基于RSM方法，結(jié)合我國鐵路建設活動的實際特點，考慮了施工方向和特殊活動對施工方案的影響，構(gòu)建了工期-費用多目標優(yōu)化模型。相較以往只考慮正向施工線性活動，本文針對活動類型的拓展，增加了可行施工方案的數(shù)量，大大增強了模型對于鐵路項目的適用性。在模型的求解過程中，設計了均勻進化的精英選擇策略，引入差分進化的變異、交叉算子，構(gòu)造了分層多策略自適應的變異、交叉算子改進NSGA-II算法獲得Pareto解集，決策者可根據(jù)實際情況和需求從中選取合適方案。文中以一個實例驗證了本文所提出模型和算法的有效性。最后，通過求解不同規(guī)模隨機算例，與傳統(tǒng)NSGA-II對比，結(jié)果顯示改進NSGA-II收斂速度更快，解的質(zhì)量更優(yōu)，運行更加穩(wěn)定。

本研究假定所有子活動只能按照一個固定的順序進行施工，而在實際工程中，可能存在活動上各子活動之間的邏輯施工順序是可變的情況[7]。因此，后續(xù)的研究將增加對軟邏輯、多工作隊等因素的考慮，使模型算法能適應情況更加復雜的場景。