基于改進(jìn)遺傳算法的工程施工進(jìn)度優(yōu)化

馬國豐， 張靈祉

(同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院, 上海 200092)

當(dāng)前我國建設(shè)產(chǎn)業(yè)正處于由迅猛發(fā)展轉(zhuǎn)向轉(zhuǎn)型升級的關(guān)鍵時期，對于建造工程的進(jìn)度、質(zhì)量和成本都提出了更高的要求。為實現(xiàn)這個目標(biāo)，采用的技術(shù)包括趕工法、替代施工方法、活動搭接法等進(jìn)度管理方法[1]。而前兩種技術(shù)為縮短工期會產(chǎn)生更高的加班費率和更多施工工具，基本上均會增加完工成本。活動搭接則是通過兩種活動平行施工加速工程項目的實施[2]。然而，在不具備完整的上游活動信息時開展下游活動可能導(dǎo)致返工并增加風(fēng)險[3]，而返工將導(dǎo)致不必要的成本并延長工期。如何在優(yōu)化搭接技術(shù)的過程中，理解和分析活動內(nèi)部的關(guān)系，優(yōu)化進(jìn)度管理中的搭接技術(shù)，制定同時滿足進(jìn)度和成本管理的搭接策略，對于項目方和企業(yè)都至關(guān)重要，也值得學(xué)者思考和研究。

Krishnan等[4]用上游活動進(jìn)化率和下游活動敏感度兩種屬性來描述活動，并開發(fā)出活動搭接的詳細(xì)框架。部分學(xué)者進(jìn)一步進(jìn)行開發(fā)，應(yīng)用于工程活動搭接的進(jìn)度-成本均衡問題。搭接程度與返工量直接相關(guān)[5]，Dehghan[6]指出，返工概率會隨著節(jié)省時間和搭接程度的增加而增大，并提出一個在考慮資源約束條件下可以得到最大搭接程度的進(jìn)度-成本均衡模型。吳凌霄等[7]提出進(jìn)度-成本均衡下的調(diào)度優(yōu)化方法。Grèze等[2]將搭接應(yīng)用于資源約束下的項目進(jìn)度計劃問題。Berthaut等[8]也找到一種處理資源約束下項目進(jìn)度計劃問題中搭接情境下的時間-成本均衡問題的方法。除此之外，Hazini等[9,10]利用活動搭接和仿真等其他技術(shù)求解返工概率，并提出一種啟發(fā)式方法，可以獲取用活動搭接和趕工結(jié)合實現(xiàn)進(jìn)度壓縮的最大收益。遺傳算法是在優(yōu)化領(lǐng)域最適用的方法之一，而依賴結(jié)構(gòu)矩陣(Dependency Structure Matrix，DSM)是一種展示活動間依賴關(guān)系的有效方法，被用于Hossain等[11,12]的研究中來預(yù)測設(shè)計活動的變化，避免不必要的返工。將兩種方法結(jié)合應(yīng)用于進(jìn)度管理領(lǐng)域的研究，將為學(xué)者們提供新的研究思路。

雖然進(jìn)度管理和搭接設(shè)計的進(jìn)度-成本均衡方面已有很多研究，但仍存在一定的局限性：(1)已有研究都是根據(jù)專家經(jīng)驗將一個固定的搭接率應(yīng)用于所有搭接的活動，而因活動屬性和實施條件的不同，實際每組進(jìn)行搭接的活動之間的搭接率均有所不同，因此傳統(tǒng)設(shè)定可能導(dǎo)致不可忽視的偏差；(2)大多數(shù)研究人員都基于經(jīng)驗公式來計算搭接時間，而沒有相關(guān)工具可以設(shè)計、計算和評估建筑工程項目中具備精確搭接率的搭接策略。最近，Gwak等[13]提出了一種計算方法，可以確定活動間具體搭接時間、考慮關(guān)鍵活動的動態(tài)變化、處理有多個上游活動或下游活動時活動的搭接問題，并提供了計算返工量和返工成本的數(shù)學(xué)公式。

1 引入搭接矩陣的進(jìn)度-成本均衡模型

1.1 搭接矩陣

圖1描述了活動A到活動F六個活動在三種情況下的簡化甘特圖和關(guān)系矩陣。設(shè)計結(jié)構(gòu)矩陣(Design Structure Matrix，DSM)是一種描述工程活動信息流的有效技術(shù)[14]，本圖中，根據(jù)DSM提取出搭接策略矩陣(Overlapping Strategy Matrix，OSM)。在DSM中，每個數(shù)字“1”代表行中的活動依賴于對應(yīng)列中的活動。但傳統(tǒng)“結(jié)束-開始”的進(jìn)度安排通常遠(yuǎn)超過合同要求的工期。因此需要對存在依賴關(guān)系的活動進(jìn)行搭接來加快進(jìn)度。為便于說明，假定所有活動都能得到其上游活動的初步信息。所有可以搭接的成對活動在矩陣中均用陰影表示，不論最終搭接與否。在這種情況下，OSM中將數(shù)字“1”變?yōu)椤?”來表示，表明上游活動的信息可預(yù)測，下游活動可以在上游初步信息不完整時開展，最終信息會在完工后再比較。

如圖1a所示，有三組活動可以進(jìn)行搭接，因為其中上游活動信息可預(yù)測，下游活動在得到其初步信息后立即開始；其他陰影標(biāo)注的活動組存在相互依賴關(guān)系，但其中上游信息不可預(yù)測，因此無法搭接。在這種情況下，總工期被大幅壓縮，盡管導(dǎo)致大量返工。圖1c中，為避免過多的返工，只有一組活動進(jìn)行了搭接，但這種情況下，工期超過合同約定期限，隨之招致大額的懲罰金。圖1b呈現(xiàn)了項目經(jīng)理最需要的搭接策略，通過最合理的搭接量減少返工，同時使工期控制在合同約定期限內(nèi)。上述分析清晰地闡述了最優(yōu)搭接策略對于滿足合同工期要求的同時控制成本最低的重要性。因此，有必要通過優(yōu)化方法計算哪些活動應(yīng)該被搭接，具體的搭接率又應(yīng)該是多少，從而取得進(jìn)度和成本相對的均衡。

圖1 三種搭接情況

1.2 優(yōu)化模型

因為工期和成本都需要盡量減小，搭接的進(jìn)度-成本均衡問題是一個多目標(biāo)優(yōu)化問題。研究人員曾提出可解決這個問題的一些目標(biāo)函數(shù)[4,5]。本文在已有研究的基礎(chǔ)上進(jìn)行了改進(jìn)，從而制定了一個新的目標(biāo)函數(shù)，如式(1)所示。

(1)

式中：C為項目總成本，包括直接成本、間接成本和超期的懲罰金；CD(i)為不考慮搭接時活動i的直接成本；n為活動個數(shù)；Pij為返工概率，指上游活動i的變化造成下游活動j返工的概率；Rij為由于上游活動i的變化引起下游活動j的返工時間；CI(j)為返工引起的下游活動j的日間接成本，包括每日工資和其他費用；m為下游活動個數(shù)；T為項目總工期，包括活動持續(xù)時間、進(jìn)度壓縮值及返工增加的時間；Tcd為項目的合同約定期限；pc為項目完工時間延遲時的懲罰系數(shù)；bc為項目提前完工時的獎勵系數(shù)；同時滿足約束：00。

式(1)說明精確搭接策略下的項目總成本由直接成本、返工成本和延期懲罰(可能有)構(gòu)成。與其他研究有別，懲罰系數(shù)的設(shè)定是為了避免工期超過約定期限，排除不合適的解。式(1)中，直接成本CD(i)通常針對具體項目，由專家預(yù)估每項活動的直接成本。式(2)基于Gwak等[13]的研究，用于評估下游活動返工概率Pij。

(2)

式中：Oij為兩個活動之間的搭接率，代表活動j與活動i平行施工的百分比；進(jìn)化率AE和敏感度AS的值可以由表1得到，AE取值為S表示活動進(jìn)化率慢，取值為F表示活動進(jìn)化率快，AS取值為L表示活動敏感度低，取值為H表示活動敏感度高。由于不確定性隨著搭接程度增加而增大，返工概率與搭接率也直接相關(guān)。同時，在不同情況下，Pij和Oij的相關(guān)關(guān)系并不總是相同，因此相應(yīng)的計算公式也會因進(jìn)化率和敏感度等屬性的變化而有所不同。如果活動進(jìn)化率很低，在上游活動進(jìn)行過程中，能產(chǎn)生并傳達(dá)到下游活動的準(zhǔn)確信息會很少，導(dǎo)致高風(fēng)險和返工概率。如果活動敏感度很低，則外部變化對活動造成的影響小，返工概率也會小。綜合考慮到搭接率、進(jìn)化率和敏感度，下游活動的返工概率可以用式(2)表示。公式由實際項目經(jīng)驗和數(shù)據(jù)模擬生成。

在表1中，搭接率Oij有上界值OM(最大搭接率)，和下界值ON(最小搭接率)。搭接長度Lij可以是介于0與最大搭接長度之間的任意長度。根據(jù)搭接機(jī)制，返工概率Pij和返工時間Rij均為搭接長度Lij的函數(shù)，如式(3)所示。根據(jù)Dehghan等[1]提供的信息和項目經(jīng)驗，返工函數(shù)用式(4)表示。另外，如式(5)所示，Lij根據(jù)搭接率Oij和下游活動持續(xù)時間Dj相乘得到。

Rij=f(Lij)

(3)

Rij=0.2Lij

(4)

Lij=OijDj

(5)

對應(yīng)的返工量由返工概率Pij和返工時間Rij相乘得到。另外，懲罰系數(shù)pc應(yīng)該足夠大，足以篩除工期超過合同約定期限的策略。

表1 活動屬性相關(guān)信息

2 進(jìn)度搭接策略優(yōu)化算法設(shè)計

本文提出的搭接策略優(yōu)化算法對染色體的表達(dá)方式進(jìn)行了改進(jìn)，從而實現(xiàn)策略中搭接率的細(xì)化。搭接中的進(jìn)度-成本均衡問題分為兩種，第一種是給定項目合同期限Tcd，尋求成本最小的搭接策略；第二種是項目目標(biāo)成本固定時尋求工期最短的搭接策略。本文的主要目的是針對第一種問題，在已有搭接方法的基礎(chǔ)上，得到改進(jìn)的優(yōu)化方法，如圖2所示，并可以在做出少許改動后應(yīng)用于第二種問題。

圖2 搭接策略優(yōu)化算法

2.1 輸入數(shù)據(jù)

在算法開始運行之前，需要輸入關(guān)鍵數(shù)據(jù)，如活動持續(xù)時間和依賴關(guān)系、最小和最大搭接率、活動進(jìn)化率和敏感度值、返工時間函數(shù)、日間接成本、工期延誤懲罰和合同約定工期等變量。種群個體數(shù)(NIND)為100，確保種群規(guī)模足以忽略隨機(jī)選擇導(dǎo)致的誤差。最大迭代次數(shù)(MAXGEN)為1000，足以通過多次迭代得到精確的最優(yōu)解。染色體長度(NVAR)為23，變量的二進(jìn)制位數(shù)(PRECI)為20。另外，代溝(GGAP)設(shè)定為0.9，雜交率px和變異率pm分別為0.7，0.01。

2.2 改進(jìn)遺傳算法生成初始種群

這一階段，算法生成一組隨機(jī)染色體，每個染色體包含的基因數(shù)與項目活動間存在依賴關(guān)系的數(shù)量相同。在以往的研究中，染色體上每個基因都表示一種搭接關(guān)系，均作為一個變量用于計算。但在二進(jìn)制編碼體系中，每個基因只能用“1”或“0”來表示，在這種情況下所得結(jié)果只能代表“搭接”或“不搭接”。因此，以往的研究在得到“搭接”或“不搭接”后，直接對可以搭接的活動賦予一個固定的搭接率用于進(jìn)一步計算。為了使整個計算分析過程更為精確，本研究提出了一種創(chuàng)新的方法來對染色體進(jìn)行表達(dá)。新方法中用數(shù)10個二進(jìn)制數(shù)來代替從前的一個基因。在二進(jìn)制編碼體系中，數(shù)個二進(jìn)制數(shù)可以表達(dá)一個實數(shù)，代表本研究用數(shù)十個二進(jìn)制數(shù)可以輸出每個搭接關(guān)系的精確搭接率，用于進(jìn)一步計算搭接長度等其他變量值。為了便于說明，圖3從表1中選取了案例中的9個活動來展示染色體構(gòu)成。在原始方法中，每個基因表示一組活動的搭接關(guān)系，而用本文所提出的方法中，每個搭接關(guān)系(即陰影所示方格)都用20個基因來表示，用20個二進(jìn)制數(shù)已經(jīng)足夠得到一個具體的搭接率數(shù)值，使算法得以計算每個精確搭接率。

圖3 每條隨機(jī)染色體上的基因表達(dá)

在計算搭接率和搭接時間后，可以通過上述函數(shù)得出相應(yīng)的返工量和成本。如前文所述，每一條染色體都代表了一種獨特的搭接策略，因此，通過目標(biāo)函數(shù)計算，每一條染色體也就對應(yīng)著一個獨特的總成本C和總工期T。隨機(jī)生成染色體的操作將在染色體總數(shù)達(dá)到設(shè)定值時停止，最終生成100條染色體。

2.3 生成子種群

算法從初始種群中隨機(jī)選擇兩個染色體作為母代，在某個單點基因處交換一端的所有基因，通過突變操作避免優(yōu)化過程受限于局部最優(yōu)點[6]。研究人員設(shè)定了活動總時間限制來確保搭接策略對應(yīng)的時間不超過約定工期。

2.4 生成最優(yōu)解

本文設(shè)定終止條件為迭代次數(shù)，迭代過程在滿足終止條件時會自動停止。

3 算例分析

3.1 案例背景

案例來源于一些已有研究并經(jīng)過加工后曾應(yīng)用于Gwak[13]的論文中。表1展示了案例中的18項活動及相關(guān)參數(shù)。原例中活動數(shù)據(jù)來源于專家經(jīng)驗。原案例優(yōu)化前對應(yīng)橫道圖如圖4所示。本文假設(shè)該案例中所有上游活動的信息均可以預(yù)測且信息可以從上游活動傳達(dá)到下游活動。從某種程度上，最大搭接率代表了能得到上游活動信息的最早時間點。例如，當(dāng)一個活動的最大搭接率為0.65時，意味著早期預(yù)測的信息最早能在上游活動已完成35%時傳達(dá)到該活動。本案例中，日間接成本CI(j)設(shè)定為63美元/d，合同要求的工期Tcd為110 d。在優(yōu)化之前，原不含搭接的正常工期為169 d，其中關(guān)鍵路徑為1 → 6 → 10 → 12 → 15 → 17 → 18。相應(yīng)的項目總成本為143967美元，其中直接成本133320美元，間接成本10647美元(63美元/d169 d)。

圖4 案例原計劃橫道圖

3.2 案例結(jié)果

項目依賴關(guān)系可以用如圖5所示的OSM矩陣來直觀表示。由于本案例中所有上游活動的信息都可以預(yù)測，陰影方格中所有元素均為“0”。

圖5 案例OSM矩陣

本項目規(guī)定工期為110 d，懲罰系數(shù)設(shè)定為2。懲罰系數(shù)的設(shè)定將對染色體進(jìn)行篩除，以保證完工時間不超過合同規(guī)定時間。

圖6展示了四種搭接情況下的進(jìn)度安排。第一種代表沒有任何搭接和優(yōu)化的原始進(jìn)度計劃，總工期為169 d，總成本143967美元。第二種情況下，每個活動都在得到上游活動傳達(dá)的初始信息后立刻開始，工期大幅壓縮到80 d，總成本為165006美元。工期實現(xiàn)了52.7%的顯著壓縮比例，但是總成本增幅過大，不符合實際項目要求。第三種情況為原使用該案例的研究中的優(yōu)化結(jié)果，得到完工時間為101.9 d，相較于第一種情況減少了39.7%，對應(yīng)總成本為159,425美元。最后一種情況為本文得到的最優(yōu)搭接策略，遺傳算法優(yōu)化結(jié)果如圖7所示。只有能夠在返工量最少的條件下可以縮短工期的活動才被搭接，并且給定一個精確的搭接率。通過最優(yōu)搭接策略得到的總工期和總成本分別為108.4 d和139539美元，與第一種情況相比分別實現(xiàn)了35.9%和3.1%的減少，工期沒有超過合同規(guī)定期限并且稍微降低了成本。表2展示了該案例的最優(yōu)搭接策略對應(yīng)各個活動的具體參數(shù)值。

圖6 四種搭接方法對比

圖7 優(yōu)化遺傳算法收斂圖

搭接活動搭接率搭接長度/d返工時間/d返工概率返工成本/美元1-50.2186.541.310.10256.691-60.3007.201.440.46388.775-70.2183.920.780.10153.516-80.50012.002.400.411079.866-90.60015.003.000.451619.862-100.80026.395.280.523800.036-100.80026.405.280.523801.217-110.60012.002.400.581295.938-110.60012.002.400.581295.895-120.2858.551.710.10438.699-120.2868.591.720.10442.3510-120.2868.581.720.10441.243-130.50012.002.400.551079.984-140.75013.502.700.501822.069-140.75013.502.700.501822.2612-150.812.82.560.641843.213-160.2176.521.300.10254.7314-160.2186.551.310.10257.5711-170.70016.803.360.482116.6614-170.70016.803.360.482116.7515-170.70016.803.360.482116.8016-180.2173.900.800.10152.0517-180.2193.940.790.10155.09

本文提出的優(yōu)化方法的優(yōu)越性主要表現(xiàn)在兩個方面：(1)總工期遠(yuǎn)比優(yōu)化前的工期短。盡管時長比第二和第三種方法中要長，但仍滿足合同要求，因此該進(jìn)度可以接受。(2)由于優(yōu)化后減少了不必要的返工，總成本少于其他三種情況下的成本。證明該優(yōu)化方法對實際工程項目具有一定的意義。

4 結(jié) 語

針對目前在進(jìn)度管理搭接技術(shù)的研究中存在的不足，即搭接率的固定設(shè)定和參數(shù)計算依賴于專家經(jīng)驗等問題，本文在改進(jìn)遺傳算法內(nèi)染色體的表達(dá)的基礎(chǔ)上，提出基于改進(jìn)遺傳算法的最優(yōu)搭接策略分析方法，并以一個小型工程項目為例進(jìn)行了實證研究，驗證了該方法的有效性和可行性。文中數(shù)學(xué)公式可以輸出最優(yōu)搭接策略中的搭接率、總工期、總成本等數(shù)據(jù)。可以用該優(yōu)化模型優(yōu)化進(jìn)度計劃中的搭接設(shè)置，使搭接活動更精確，保證總工期滿足合同要求。也可以比較輸入不同的信息、屬性、合同要求等條件時，對應(yīng)總工期和總成本的變化。

但是，目前研究中進(jìn)化率、敏感度、最大搭接率等活動屬性都是根據(jù)進(jìn)度管理人員的經(jīng)驗設(shè)定，由于專家文化背景和經(jīng)歷的不同，可能產(chǎn)生一定的誤差，有待后續(xù)進(jìn)一步研究。本研究中沒有考慮到外部條件變更引起的進(jìn)度變化，在多學(xué)科協(xié)作的建設(shè)環(huán)境下，建議后續(xù)研究可以用變更傳播預(yù)測方法進(jìn)行變更管理，通過科學(xué)建模和分析來消除這種不確定性。