基于SAGA鐵路工程施工進度-成本動態優化研究

張飛漣，何媛媛，吳科一，胡所亭，韓鵬輝

(1.中南大學 土木工程學院，湖南 長沙 410075；2.紐約大學 阿布扎比分校 S.M.A.R.T.建筑研究組，阿聯酋 阿布扎比 129188；3.中國鐵道科學研究院集團有限公司 鐵道建筑研究所，北京 100081；4.中鐵第四勘察設計集團有限公司 工程經濟設計研究院，湖北 武漢 430063)

近年來，隨著中西部發展戰略的提出，鐵路網規模不斷向中西部擴大，為有效應對中西部復雜建設環境，保證鐵路運行的安全性，鐵路工程建設目標向高起點、高質量、高標準方向轉變，致使鐵路工程的施工成本也不斷上漲，極大制約了鐵路的發展[1]，如何對鐵路工程施工成本進行優化成為鐵路建設過程中亟待解決的問題。進度和成本是工程建設兩大重要目標，且兩者互相聯系互相影響，專家學者們通常把施工進度調整和成本優化聯系在一起，在保證工程建設質量要求的前提下，通過調整進度計劃來實現對成本的優化。對于施工進度-成本優化的研究，主要分為兩大流派：第1個流派考慮通過對進度計劃的調整，來實現對有限資源的最大化利用，從而實現對成本的優化。如HEGAZY等[2]提出一種確定單個施工作業成本最低，生產率最高的資源量的優化方法。GHODDOUSI 等[3]提出多模式資源約束離散進度成本資源優化模型，在資源配置和均衡方面提供使用的解決方案。李英攀等[4]針對資源優化模型特點，提出基于SAGA 的項目資源優化方法。第2個流派提出：通過調整進度計劃，控制工期，來實現對成本的直接優化。如ZHENG 等[5]提出基于遺傳算法的多目標進度成本優化模型。AI HAJ等[6]提出一種進度-成本-風險的均衡模型，在進行進度-成本優化時，考慮對工程總時差的影響，避免工期延誤風險的提高。黃良輝等[7]通過研究工序持續時間與成本的關系，建立了工程項目成本-工期均衡優化數學模型，通過調整關鍵線路建設活動持續時間，來實現進度-工期的優化。雖然施工進度-成本優化模型的研究受到了一定的關注，但大多數研究都集中在優化資源利用或縮短工期的模型開發上，且以中小型工程項目為主，很少有研究考察大型鐵路工程建設周期內的由資金成本和時間因素引起的潛在費用成本問題。當工程費用不高，資金成本較小，建設周期較短時，利用上述模型安排施工進度計劃，對施工成本的控制是非常有效的。但由于大型鐵路工程的施工費用高，建設周期較長，隨著時間的推移資金成本所引起潛在費用的增加是大型鐵路工程不可忽視的成本問題，此時，實現資源的最優化利用或最短的工期并不一定能保證施工成本的最小，因此，在進行鐵路工程進度安排時，需考慮費用發生時點[8]，把每一筆資金用在關鍵節點，最大限度地減少鐵路工程施工過程中潛在費用成本的上漲，發揮有限資金最佳效能。本研究為提高鐵路工程施工過程中資金的利用效率，在構建鐵路工程施工進度-成本優化模型的同時，考慮資金成本和費用發生時點的，并提出與本模型具有高適配性的模擬退火遺傳算法(SAGA)，降低了模型在計算過程中陷入局部陷阱的概率，提高了計算結果的準確率。以某鐵路橋梁工程為案例驗證了鐵路工程施工進度-成本優化的可行性以及SAGA 算法的可操作性。本研究成果可為鐵路工程施工進度-成本動態優化提供借鑒和參考。

1 鐵路工程施工成本優化模型建立[9]

1.1 鐵路工程施工成本構成

鐵路工程施工成本，一般按性質分為直接成本和間接成本[10]。直接成本是指直接用于施工的人工、材料、機械等直接費用，間接成本是指為保證項目正常施工但不直接用于項目施工的企業管理費、規費等間接費用[11-12]。

1.2 前提假設

本模型假設各建設活動所花費的費用在持續時間內平均分布。

1.3 目標函數

建設資金由于受時間、風險等因素的影響，在使用期間是有一定成本的，通常稱之為資金成本[13]。隨著施工工期的加長，施工費用的增大，資金成本對資金的使用效率的影響也在逐漸增大，是項目不可忽視的潛在成本。本模型以提高鐵路工程建設資金使用效率為目標，以資金成本率為折現率，考慮鐵路工程各建設活動施工費用發生時點，以施工工期末為計算基點，通過調整進度計劃，尋求工期末最小施工總成本。

施工直接成本在工期末的成本終值可表示為：

施工間接成本在工期末的成本終值可表示為：

故，目標函數可表示為：

式中：Fα為考慮資金成本后的施工直接成本在工期末的成本終值；Fβ為考慮資金成本后的施工間接成本在工期末的成本終值；TC為鐵路建設項目在工期末的施工總成本終值；I為項目建設活動數量；i表示第i項建設活動；k為某一時間點；Di為第i項建設活動的持續時間，可為根據成本與建設活動持續時間關系或歷史經驗，所得到的各建設活動的最佳持續時間；r為資金成本率；Cαi為采用施工組織設計方案的第i項建設活動的直接成本,本模型假設該費用在第i項建設活動工期內平均分布，如果需要更精確表達，具體分布也可以根據類似項目歷史數據確定；Cβi為按一定的間接費費率所得到的第i項建設活動的建設管理的間接成本，本模型假設該費用在第i項建設活動工期內平均分布，如果需要更精確表達，具體分布也可以根據類似項目歷史數據確定；STi為第i項建設活動的計劃開始時間；FTi為第i項建設活動的計劃結束時間。

1.4 約束條件

在本模型中，成本的優化主要是通過調整各建設活動的進度計劃來實現的。項目在進行進度安排時需滿足工期要求、建設活動邏輯關系要求、有限資源使用要求。

1) 工期約束。所得工期不可超過合同規定的最大工期。

式中：Tr為合同規定工期。

2) 邏輯關系約束。需滿足施工組織設計中的前后任務的邏輯關系要求，考慮其與前置任務是否滿足F-S(或S-S,S-F,F-F)+搭接時間ΔT的邏輯關系：

式中：i′是第i項建設活動的前置任務；ΔTi′為第i項建設活動和第i′項建設活動的搭接時間。

3) 資源約束。每日資源需求量不可超過各類資源的每日使用限定量。資源每日使用限量是管理者根據庫存、工程采購條件、運輸能力等對各類資源所制定的每日最大使用量，后管理者可根據優化后的進度計劃進行資源的采購和分配。

式中：Rl為l類資源每日需求總量；Sl為l類資源每日限定總量；L為所有資源的集合。

2 模擬退火遺傳算法

2.1 模擬退火算法

模擬退火算法(Simulated Annealing,SA)是一種較為典型的概率算法，其優點在于：它在搜索過程中既接受“好”解，也能以一定概率接受“壞”解，以此跳出局部陷阱，從而找到全局最優解。此優點的實現主要依靠模擬退火算法引入的Metropolis 準則，并將其作為接受新解的主要依據。設目標函數為miny(x)，自變量為x，假設當前解為xi，通過一定規則產生的新解為xj，依據Metropolis準則，新解的接受與否由以下關系式決定[14]：

其中：T表示溫度，為重要控制參數。在模擬退火算法中T以一定方式遞減，通常為：

其中，α為遞減系數，其取值通常為0.85<α<1，目前較多的α取值為0.95。k為迭代次數。在一定程度上溫度T決定著接受新解的概率，在計算過程中，溫度與接受新解的概率呈正比，隨著溫度的遞減，接受新解的概率也在逐漸降低，是一種從全局到局部的計算方法。

2.2 遺傳算法

遺傳算法(Genetic Algorithm,GA)被大多數學者認為是較為高效的隨機搜索算法，常被應用于組合優化類問題。該算法模仿種群進化過程，傳統的算法中會隨機產生一個解集，并將其作為初代父代，一般稱此“父代”為初始種群，在該初始種群中，將各解視為染色體，通常通過二進制轉化方式將各個染色體上化作一組變量并將其看作基因，模仿基因的選擇、交叉、變異過程，后通過綜合適應度值(目標函數值)對每條染色體進行評價，多次進化直到滿足迭代結束條件，從而提供問題最優解的一種模型求解方法[15-16]。

2.3 模擬退火遺傳算法

無論是模擬退火算法還是遺傳算法在某種程度上都屬于啟發式算法，是一種概率算法，并不能保證每次運行的解相同，且都是最優解，對于復雜的問題來說，易陷入局部陷阱。由于本模型的變量較多，約束條件較多，問題較為復雜，該兩種算法單獨使用容易跳入局部陷阱[4]。因此，需要更為精確的算法進行最優解的搜索。

本文選用模擬退火算法和遺傳算法相結合的模擬退火遺傳算法(SAGA)：模擬退火算法的核心在于利用溫度P來加大搜索范圍，幫助算法跳出局部最優解。遺傳算法的核心在于利用各解之間選擇、交叉、變異循環迭代過程找到最優解，需要指出的是，其復制、交叉、變異過程都是以初始種群為基礎，初始種群作為父代，對子代有較大影響，在傳統的遺傳算法中，初始種群是隨機生成的，由于本模型解的多元化，約束條件的強約束性，隨機產生的初始種群大多不能滿足約束條件，由此會使模型求解效率大大降低。故本文選擇將模擬退火算法和遺傳算法的優點相結合，一方面，可以利用Metropolis 準則，擴大解的搜索范圍，找出所有符合約束條件的解；另一方面，將模擬退火算法找到的全部滿足約束條件的可行解作為遺傳算法的初始種群，并通過復制、交叉、變異等過程再一次對最優解進行迭代搜索，幫助算法能夠最大概率的找到最優解。

2.4 SAGA求解步驟

由模型中的式(1)可知，模型的最終目的是實現總成本的最小，故此算法以成本為因變量，由于本模型的核心是考慮時間因素，各建設活動的開始時間對求解結果具有重要的影響，且具有較大的可變動性，故選擇以各建設活動的開始時間為自變量，進行算法的編制。具體實現步驟如下。

步驟1 讀取數據。讀取各建設活動的直接費、間接費、邏輯關系、每日資源限定量等重要數據。

步驟2 參數初始化。各參數的初始值應是在反復試驗中所找到的效率較高的數值。

步驟3 構建function函數。Function函數即為目標函數。

步驟4 設定初始最優解。以初始方案作為初始解x0，并儲存在新解集合pop 中，計算對應的目標函數y0，并將x0作為初始最優解best_x，y0作為初始最優值min_y。

步驟5 建立循環。外循環采用最大迭代次數，內循環表示在某一溫度下的迭代次數。主要流程為：

①產生新解x。在所接受解的附近生成新解x，新解應為最早開始時間和最晚開始時間之間的整數。

②是否滿足約束條件。在本模型中約束條件主要考慮工期、邏輯關系、資源約束，若新解滿足約束條件，則繼續，若不滿足，則返回①；

③是否接受新解。以式(10)作為是否接受新解的主要依據。其中若p=1，則更新最優解best_x和最優值min_y并儲存新解在pop 解集中；否則，則以一定的概率接受新解并儲存新解在pop 解集中，但不更新最優解，返回①，直至達到該溫度下的迭代次數，即跳出本次內循環，繼續④；

④溫度下降。當某一溫度下的內循環結束時，則溫度按式(11)下降，重復①～③；

⑤退出迭代。在本模型式中設定2 種情況：一種是迭代次數達到最大迭代次數；另一種是當最優解連續重復cf 次后，則結束模擬退火的迭代，開始步驟6。

步驟6 建立遺傳算法初始種群。將模擬退火算法儲存的滿足工期、資源、邏輯關系約束條件pop 解集作為遺傳算法的初始種群，并進入遺傳算法選擇-交叉-變異的種群迭優化過程。

步驟7 設置最大迭代代數ds，對初始種群進行選擇-交叉-變異迭代優化：

①選擇：利用經典的輪盤賭的經典遺傳算法選擇策略，對初始種群pop進行選擇，生成新種群newpop。

②交叉：采用單點交叉。在種群newpop 中，根據交叉概率，隨機選擇相鄰解，生成1 到19 的隨機整數cpoint，從第cpoint 位置開始與選擇的相鄰解進行交叉迭代，并生成新種群newpop1。

③變異：在種群newpop1 中，根據變異概率，隨機選擇某個或幾個解進行變異，用xi表示，生成1到19的隨機整數mpoint，對xi的第mpoint位置進行在定義域內的隨機變異，生成種群newpop2。

步驟8 約束條件檢驗。根據約束條件，對種群newpop3 中的解檢驗，通過，進入下一步，否則，淘汰。

步驟9 更新最優解。計算該種群中的最優值bestfit，及其對應的最優解bestindividual，并與之前的最優解進行比較，若更優，則對最優解best_x和最優值min_y進行更新并儲存于新的初始種群newpop3 中，否則僅儲存于新的初始種群newpop3中，輸入pop=newpop3，將新的初始種群復制給原初始種群中，返回步驟7。

步驟10 退出迭代。重復步驟7～步驟8，直到滿足種群最大迭代次數ds，或迭代的種群中無滿足約束條件的解為止，退出迭代。

步驟11 輸出best_x，min_y。主要流程如圖1所示。

圖1 模擬退火遺傳算法(SAGA)主要流程Fig.1 SAGA main flow chart

3 案例分析

3.1 案例概況

某鐵路橋梁工程項目X，為雙線大橋，周圍地勢起伏大，植被茂盛，具有高墩較多，質量標準高，安全風險高，地勢復雜等工程特點，工期共計20 個月。該橋梁工程主要包括3 類梁型，分別為：掛籃懸臂澆筑連續梁、道岔連續梁及簡支現澆梁、其他孔跨梁，分別簡稱為Ⅰ類梁、Ⅱ類梁、Ⅲ類梁。依據不同種類的梁，共劃分了15 個主要建設活動，且各建設活動之間具有較強的邏輯約束關系。某資源是各建設活動所需的主要資源，每日限定量設定為5 臺，各建設活動的進度安排，建設活動之間的邏輯關系、費用及每日資源使用情況如表1所示。各項建設活動的開始時間從第一項建設活動的開始時間算起，以“日”為單位。

表1 各建設活動的開始時間要求、邏輯關系、費用及資源使用情況Table 1 Start time requirements,logical relationship,cost and resource usage of each construction activity

3.2 方案優化

1) 項目X施工進度-成本優化

為使每一筆資金都用在關鍵時點上,提高資金使用效率，在考慮資金成本以及費用發生時點的條件下，基于SAGA 對項目X 進行施工進度-成本動態優化。在綜合考慮了資金籌集方式、資金使用成本后，設定資金成本率為r=14.4%。結合案例數據的復雜性和約束性，為維持較高的準確率和相對較低的運算時間，經多次試算后，對SAGA算法中各參數的設定值如表2所示。基于此，對項目X成本優化結果如表3所示。

表2 SAGA參數設定值Table 2 Parameter setting value of SAGA

表3 優化后方案及成本Table 3 Optimized plan and cost

2) 方法對比

傳統多目標最優值模型的計算方法多基于模擬退火算法或者是遺傳算法，本文采用模擬退火遺傳算法的優點在于得到最優解的概率相較于單獨使用模擬退火算法或者是遺傳算法的概率大，即所得結果的準確率高。在此，分別利用模擬退火算法、遺傳算法以及模擬退火遺傳算法對該例進行施工進度-成本的優化，由于案例成本較大，且SA，GA和SAGA均為概率算法，故設定程序運行結果與最優結果的誤差在0.5 以內為運行成功，即為有效運行。在進行50 次優化迭代后，分別統計各算法運行10次、20次、30次、40次、50次后的有效運行次數，并做出相應的運行效率對比圖，如圖2所示。

圖2 SA，GA和SAGA運行結果對比Fig.2 Comparison of SA,GA and SAGA operation results

3.3 結果分析

1) 優化前后施工進度對比分析

根據優化前后各建設活動的開始時間及持續時間，做出優化前后施工進度安排對比圖，如圖3所示。從圖中可看出，在各建設活動之間邏輯關系、資源條件、最早開始時間和最遲開始時間的強約束條件之下，優化后的方案工期與原方案相同，這是由于受Ⅰ類梁棧橋及鉆孔平臺、Ⅰ類梁合攏段施工、Ⅱ類梁上部結構、Ⅲ類梁上部結構施工、橋面系及附屬工程等關鍵節點的影響。

圖3 優化前后施工進度安排對比Fig.3 Comparison of construction schedule before and after optimization

從圖3亦可看出，部分建設活動的開始時間在約束范圍內有了一定的改變，根據模型構建原理分析可得,在資金成本不變的條件下，可通過縮短各建設活動開始時間與最大施工結束時間的時間跨度，來減小由于資金成本所帶來的成本上漲，在此同時需滿足工期、邏輯關系、資源以及開始時間等約束條件。故相比于原方案中各建設活動的開始時間，優化后的方案中大多建設活動的開始時間往后有所推遲，其中，Ⅱ類梁下部結構推遲時差跨度最大，一方面是因為其費用較大，另一方面是由于其最早開始時間和最遲開始時間跨度較大，相對于其他建設活動而言，其進度安排的可變動性大。

2) 優化前后成本對比

由表1 計算可得，在不考慮資金成本的情況下，項目X 靜態施工成本為136 474.914 1 萬元，在考慮資金成本后，原方案的施工成本上升為137 769.941 9 萬元，與項目X 靜態施工成本相比，上漲了1 295.027 8 萬元，金額較大，說明在計算本項目成本時，考慮資金成本是非常必要的。

從表3優化結果可看出，當考慮資金成本，通過調整費用發生時點進行成本優化，優化后的施工成本為137 703.510 1 萬元，在工期、邏輯關系、有限資源等強約束環境下，優化了66.431 8 萬元，占項目靜態施工成本的0.05%，占原方案中由資金成本造成的成本上漲額的5.13%，如圖4 所示。故，此模型在資金成本不變的情況下，通過調整進度計劃，控制費用發生時點，優化了原方案中由資金成本所帶來施工總成本上漲的5.13%，在其他工程條件不變的情況下，提高了有限資金的使用效率，減小了由時間、風險等因素所引起的施工總成本的潛在上漲。

圖4 優化前后施工成本分析Fig.4 Construction cost analysis diagram before and after optimization

3) 優化方法對比

從圖2 的線性趨勢圖可以看出，SA 的平均運行有效率為84.5%，GA 的平均運行有效率略低于SA，為81.5%，SAGA的平均運行有效率為97.2%，遠高于SA 和GA。由此可見，對于本模型而言，SAGA 相較于SA 或GA 算法，提高了模型求解的準確率，與本模型具有更高的適配性。

4 結論

1) 通過分析鐵路工程施工成本構成，以直接成本和間接成本為計算基礎，考慮資金的時間、風險因素，以最大工期、邏輯關系和有限資源為約束條件，構建了鐵路工程施工進度-成本動態優化模型。

2) 該模型的變量較多，約束條件較多，求解過程較為復雜，為提高求解結果的效率，提出將Metropolis 準則和種群迭代過程相結合的模擬退火遺傳算法(SAGA)模型求解方法。

3) 運用基于SAGA 的鐵路工程施工進度-成本動態優化方法對某鐵路橋梁工程進行優化，通過調整進度，優化了原方案中由資金成本引起的施工成本上漲額的5.13%，印證了該模型的有效性和可行性。

4) 此研究成果可為資金成本較大的鐵路工程施工進度-成本動態優化提供一定的借鑒和參考，且當資金成本越高，動態性越高，施工周期越長時，該模型的優化效果就越明顯。在本研究構建的鐵路工程施工進度-成本動態優化模型中，未深入探討鐵路工程各建設活動的持續時間與施工成本時間之間的關系函數，在下一步的研究中擬對此關系函數進行深入探究，以對本研究中的鐵路工程施工進度-成本動態優化模型加以擴充。