電力隧道工程建設(shè)中的離散時間費用權(quán)衡問題

熊 俊， 孫 聰， 劉 青， 馬博翔,3， 張立輝

(1. 國網(wǎng)北京市電力公司， 北京 100041； 2. 華北電力大學(xué) a. 經(jīng)濟與管理學(xué)院； b. 新能源電力與低碳發(fā)展研究北京市重點實驗室， 北京 102206； 3. 清華大學(xué) 電氣學(xué)院， 北京 100084)

當前我國處于基本建設(shè)大發(fā)展時期，大量的重復(fù)性建設(shè)項目如隧道工程、地鐵等正在興建或規(guī)劃之中，這些項目投資大、工期長，因此對它們的研究具有很實際的意義。重復(fù)性建設(shè)項目是指在建設(shè)工程的每個單元各個工序不斷重復(fù)進行的項目[1]。由于工作連續(xù)性和資源恒定性是重復(fù)性建設(shè)項目調(diào)度計劃中需重點考慮的因素。因此，近年來，國內(nèi)外學(xué)者對兩者進行了大量的研究，例如Vanhoucke[2]提出工作連續(xù)性約束能使每個工序的施工空閑時間最小化，這在一定程度上能縮短工期；而Birrell[3]提出維持工作連續(xù)性將導(dǎo)致工期變長； Selinger[4]也認為不保持工作連續(xù)性將有可能進一步縮短項目工期。Zhang等[5,6]提出資源恒定性約束有利于高效利用資源，但同時也可能造成工期的延長，其還研究了資源連續(xù)性的相關(guān)原理。因此，有必要權(quán)衡工作連續(xù)性與資源恒定性對離散時間費用權(quán)衡(Discrete Time-Cost Trade-off Problem，DTCTP)的影響，但目前相關(guān)研究較少。DTCTP是項目調(diào)度中的一種雙目標優(yōu)化問題，屬于強NP - 難問題[7]。DTCTP的解決方法主要有基于動態(tài)規(guī)劃[8]和分支定界的精確算法[9]，也有基于啟發(fā)式規(guī)則的各種啟發(fā)式算法[10]以及智能算法[7,11]。目前對該問題的研究大都采用智能算法求解，如Hyari等[12]構(gòu)建了能權(quán)衡總工期與總費用的遺傳算法，并采用Pareto最優(yōu)性原理對重復(fù)性建設(shè)項目的調(diào)度方案優(yōu)化；Zhang等[1]用遺傳算法解決了軟邏輯下重復(fù)性項目的時間費用權(quán)衡問題；Long等[11]設(shè)計了考慮工序優(yōu)先關(guān)系和工作連續(xù)性的遺傳算法，并將其應(yīng)用于優(yōu)化重復(fù)性項目的工期和費用。但是，針對工作連續(xù)性和資源恒定性的算法還有待進一步研究。所以，本文作者通過探索項目施工過程中工作、資源與時間費用問題的內(nèi)在關(guān)系，構(gòu)建隧道建設(shè)中關(guān)于工作可間斷和資源可波動的離散時間費用權(quán)衡模型(DTCTP-wr)，提出一種雙鏈式整數(shù)編碼和隨機單點交叉算子的改進算法，并以一個實際的電力隧道建設(shè)項目為例，驗證算法的有效性和合理性，并得出工作連續(xù)性約束和資源恒定性約束對項目造成的影響。而且，該算法也能移植到其他重復(fù)性項目的調(diào)度中，為我國基礎(chǔ)設(shè)施建設(shè)提供更為科學(xué)、經(jīng)濟的調(diào)度方案。

1 DTCTP-wr

1.1 問題描述

重復(fù)性項目問題描述如下：設(shè)有N個工序，每個工序有M個相同的單元(例如，隧道具有多個相似的豎井)。工序1是開始工序，工序N是結(jié)束工序。工序i(i=1,…,N)的施工情況與它的緊前工序有關(guān)，需與緊前工序滿足結(jié)束 - 開始的時間約束。工序i的第j單元表示為子工序aij，并且有Ki種執(zhí)行模式。aij的工期用dijk,k=1,2,…,Ki表示，變量k表示執(zhí)行模式選擇。

項目的總費用由以下部分組成：直接費用DC，間接費用IC和所有工序的資源閑置費用IRC。各部分費用具體計算如下：

采用式(1)計算項目直接費用DC，由項目中每個工序各單元的材料費用MC、勞動力費用WC、設(shè)備費用EC之和構(gòu)成。

DC=MC+WC+EC

(1)

采用式(2)計算項目間接費用IC，由項目中每天對應(yīng)的費用之和構(gòu)成。

(2)

式中：ICRd為第d天的間接費用；D為項目的總工期。

采用式(3)計算資源閑置費用IRCi。資源閑置費用是由于承包商執(zhí)行模式選擇不當，造成資源閑置所產(chǎn)生的費用。若工序i須保證資源恒定性約束，IRCi等于所選擇執(zhí)行模式的勞動費用率(包括人、料、機的閑置費)與中斷天數(shù)的積。否則，若工序i無資源恒定性約束，IRCi等于所有可選執(zhí)行模式中勞動費用率最高值與中斷天數(shù)的積。

(3)

式中：xijk為二進制數(shù)(如果子工序aij在模式k下執(zhí)行，xijk取1；否則，xijk取0)；INTi為工序i的中斷天數(shù)；Ri為工序i資源恒定性約束；集合Θ表示所有工序的資源恒定約束關(guān)系。

1.2 數(shù)學(xué)模型

目標函數(shù)：

MCij+IRCi]+IC

(4)

約束條件：

sij+dij≤spj,p∈(j,N],i=1,2,…,N;j=1,2,…,M

(5)

(6)

(7)

(8)

(9)

xijk-xi(j+1)k=0,i∈Θ;j=1,2,…,M-1;k=1,2,…,Ki

(10)

(11)

Ft≤Tmax

(12)

式中：i為工序數(shù)；j為單元數(shù)；N為工序總數(shù)；M為單元總數(shù)。目標函數(shù)式(4)最小化項目總成本。約束條件式(5)表示在同一工序中子工序aij完成后子工序ai(j+1)才可能開始，sij為子工序aij的開始時間。約束條件式(6)中dij指工序i單元j的持續(xù)時長。約束條件式(7)中yijl指工序i單元j選擇第l種模式時yijl=1。約束條件式(6)(7)要求每一工序需滿足給定的邏輯施工順序，即子工序ai(l+1)只能在子工序ail結(jié)束后才能開始(如果子工序ai(l+1)滿足條件，yijl取1；否則，yijl取0)。約束(8)表示每個子工序只能有一種邏輯調(diào)度順序。約束(9)表明為了滿足工作連續(xù)性約束，中斷時間必須為0，集合Φ表示所有工序的工作連續(xù)性約束關(guān)系。約束條件式(10)要求所有滿足資源恒定約束的工序均需執(zhí)行同樣的執(zhí)行模式。約束條件式(11)表示任一子工序僅有一種施工順序，同一工序內(nèi)的任何兩個子工序不能同時施工。約束條件式(12)要求項目的工期Ft不能超過給定的最大工期限制Tmax。

2 改進遺傳算法

由于DTCTP問題的計算規(guī)模相當大[7]，非線性方法很難在短時間內(nèi)得到令人滿意的結(jié)果。因此，針對所研究的問題，本文設(shè)計了相應(yīng)的雙鏈染色體編碼方式、帶懲罰函數(shù)的適應(yīng)度值計算法，以及單點交叉算子和變異算子，并最終提出了一種具有求解能力的改進遺傳算法。

2.1 雙鏈染色體編碼

圖1 染色體結(jié)構(gòu)

2.2 適應(yīng)值計算

對于DTCTP-wr，在調(diào)度方案集中有可能存在一些總工期超期或總費用超額的方案。所以本文提出了一種懲罰機制，確保這些方案比在工期范圍內(nèi)的項目適應(yīng)度值小。對于個體I,Ft(I)為個體I對應(yīng)的最小總工期。修正其最小總工期目標函數(shù)為：

F′c(I)=(1+βt)Fc(I)

(14)

式中：βt為一個正懲罰因子，按式(15)計算。

(15)

因為DTCTP-wr屬于最小化雙目標問題，所以適應(yīng)度函數(shù)應(yīng)轉(zhuǎn)化為：

fc(I)=max{F′c(1)，F(xiàn)′c(2),…,F′c(P)}-F′c(I)

(16)

式中：P為種群規(guī)模。

適應(yīng)度值確定后，接下來就選擇當前代的最優(yōu)個體進行迭代遺傳操作。

2.3 單點交叉算子

對執(zhí)行模式鏈進行單點交叉操作。令隨機整數(shù)r(0≤r≤N)作為單點交叉起點。工序i=1,2,…,r所在的染色體，從一個父代中得到染色體片段，即

(17)

工序i(r

(18)

與執(zhí)行模式的單點交叉操作方法類似，邏輯順序鏈也用同樣的方法，但須注意的是單點交叉點的位置需要重新隨機生成。

2.4 變異算子

對于執(zhí)行模式鏈，隨機選取工序t，t∈[1,N]作為突變點。若工序t有資源恒定性約束，那么，工序t所在的染色體片段需在隨機整數(shù)[1,Kt]取值。否則，保證工序t中有且僅有一個單元在[1,Kt]隨機取值即可。

對于邏輯順序鏈，首先選出變異的工序t，即隨機生成整數(shù)t，t∈[1,N]；然后，選出工序t所在的變異單元，即生成兩個隨機整數(shù)u,v,u,v∈[1,M]；最后，將工序t的第u單元的染色體信息與第v單元的染色體片段信息交換。

2.5 調(diào)度算法

為了將每個染色體中的信息整合為與工期相關(guān)的信息，進而求得其對應(yīng)的總工期和總費用。對于給定個體I，調(diào)度算法具體步驟如下。

步驟1：初始化種群P，種群大小為Np，設(shè)當前遺傳代數(shù)gen為1 ；

步驟2：通過模型中的約束條件解析執(zhí)行模式鏈和邏輯順序鏈，計算子工序aij的工期dij并根據(jù)模型中的約束條件得到當前代的最小總費用。根據(jù)所要求解的子問題計算所有個體的適應(yīng)度值，然后對種群進行輪盤賭選擇，生成子種群C；

步驟3：對子種群C中的所有個體進行交叉算子，生成新的子種群C1；

步驟4：對子種群C1中所有個體執(zhí)行變異算子，生成新的子種群C2；

步驟5：分別從種群P和子種群C2中各挑選適應(yīng)度較高的1/2個體進行合并得到新的種群P；

步驟6：令gen=gen+1，若gen的值小于設(shè)定的最大遺傳代數(shù)，返回步驟2；否則跳出程序并輸出近似最優(yōu)解。

3 結(jié)果及分析

本文采用一個明開電力隧道建設(shè)項目作為算例[13]。該項目由五個工序構(gòu)成，分別是挖隧道，填地基，做豎井，上蓋板和鋪頂面。項目管理費用為2500美元/d。項目其他基本信息如表1所示。dijk可通過dijk=Qij/Pik得到。下面將通過四種情形進行討論：

情形1: 所有工序沒有工作連續(xù)性約束，但均有資源恒定性約束；

情形2: 所有工序都有工作連續(xù)性約束和資源恒定性約束；

情形3: 所有工序均有工作連續(xù)性約束，但沒有資源恒定性約束；

情形4: 所有工序沒有工作連續(xù)性約束，同時也沒有資源恒定性約束。

表1 項目基本數(shù)據(jù)

3.1 工作可間斷影響分析

圖2 有/無工作連續(xù)性約束下時間 - 費用曲線

圖2為有/無工作連續(xù)性約束下時間 - 費用曲線，通過比較情形1和情形2的結(jié)果可知，在資源恒定性約束情況下，工作可間斷對項目成本和時間的影響。(1)如圖2所示，總工期范圍在106～118 d內(nèi)，情形1，2的時間 - 費用權(quán)衡曲線基本上是重合的。這是由于在該隧道建設(shè)項目中，只有當所有工序都沒有中斷或存在很少中斷的情況下才會出現(xiàn)項目工期較長的情況。(2)如圖2所示，情形1得到的方案數(shù)明顯比情形2多， 這是因為不考慮工作連續(xù)性，子工序與子工序之間的時間關(guān)系將更加靈活，約束時間不再必須取0。(3)表2，3分別為情形1，2下時間 - 費用曲線的詳細計算結(jié)果。據(jù)表2，3可知，兩種情形下主要的區(qū)別在于方案中的最小項目總工期。表3列出了情形2下詳細的計算結(jié)果，其中最小項目總工期為104.82 d，對應(yīng)的總費用為1654977美元。如果所有工序允許工作不連續(xù)(情形1)，最小項目總工期將縮短為94 d，相比節(jié)約了10.32%；但是對應(yīng)的費用相應(yīng)也提高到了1758235美元。情形3，4也有相似的結(jié)論，具體結(jié)果分別見表4，5?？梢?，允許工作中斷將有利于項目縮短總工期。

3.2 資源可波動影響分析

圖3為有/無資源恒定性約束下時間 - 費用曲線,通過情形1和情形4的結(jié)果比較可知，在沒有工作連續(xù)性的情況下，資源可波動對項目成本和時間的影響。(1)如圖3所示，在最大工期限制范圍內(nèi)，每個可行的項目方案，情形4中的總費用總是低于情形1。這種現(xiàn)象可解釋為：當工序不需維持資源恒定性約束時，該工序中所有的子工序都不會對項目工期造成影響，并且將會選擇最經(jīng)濟的執(zhí)行模式。但是，當所有工序有資源恒定約束，子工序需要根據(jù)其他相關(guān)子工序執(zhí)行模式選擇情況來選擇類似的執(zhí)行模式，而對其他子工序經(jīng)濟的執(zhí)行模式并不一定適用于該子工序。(2)根據(jù)圖3，結(jié)合對比表2，5中的項目總費用可知，當截止日期為Tmax=94 d時，這兩種情形下的項目總費用差值達到最大值(1758235-1723960)=34275美元。因為總工期越短，中斷天數(shù)越少，不考慮資源恒定性的情形4下，對應(yīng)的資源閑置費用就越低，而情形1中資源閑置費用也會降低，根據(jù)公式(3)可知，中斷天數(shù)的變化在這一階段對資源閑置費用起主要的影響；(3)據(jù)表2，5可知，當所有工序沒有資源恒定性約束時的最小項目總費用1615909美元，而滿足資源恒定性約束時最小總費用為1618868美元，兩者基本相等。而對應(yīng)的總工期前者僅113 d遠少于后者的118 d。情形2，3也有相似的結(jié)論，具體的結(jié)果分別見表3，4?？梢?，取消資源恒定性約束將有利于項目減少總費用。

3.3 雙重因素組合影響分析

通過情形2和情形4的結(jié)果比較可知，工作可間斷和資源可波動雙重因素影響下對項目成本和時間的影響。(1)據(jù)表3和表5可知，情形2的可選擇方案數(shù)明顯少于情形4。主要原因有兩點，一是因為情形2考慮工作連續(xù)性后，子工序與子工序之間的時間約束比情形4強，因而導(dǎo)致情形2中部分方案丟失，二是因為資源恒定性要求，子工序之間必須選擇同一執(zhí)行模式，這樣也大大減少了可選的方案。(2)對比觀察表3，5可知，當選擇總費用相差不大的方案時，在表3選擇總費用為1619612美元的方案，對應(yīng)表5與之最接近的總費用為1619954美元的方案，前者的工期比后者長(118.48-108.41)=10 d。當選擇總工期相差不大的方案時，在表3選擇總工期為104.82 d的方案，對應(yīng)表5與之接近的總工期為104.89 d的方案，前者的總費用比后者高(1654977-1622063)=32914美元。因此，對于工作連續(xù)性和資源連續(xù)性的選擇，項目管理者應(yīng)根據(jù)具體的項目目標制定與之契合的方案。

表3 情形2下時間 - 費用曲線的詳細計算結(jié)果

圖3 有/無資源恒定性約束下時間 - 費用曲線

表4 情形3下時間 - 費用曲線的詳細計算結(jié)果

表5 情形4下時間 - 費用曲線的詳細計算結(jié)果

4 結(jié) 論

(1)構(gòu)建了工作可間斷和資源可波動的離散時間費用權(quán)衡優(yōu)化模型(DTCTP-wr)，并通過一個實際的電力隧道工程建設(shè)項目驗證了其可用性和合理性。

(2)結(jié)合研究的問題，提出了基于雙鏈式整數(shù)編碼和隨機單點交叉算子的改進遺傳算法。該算法在確保近似最優(yōu)解的條件下有效地減少了運算量，并且只要稍加擴展與完善就可用于國家基礎(chǔ)建設(shè)項目的規(guī)劃中。

(3)定量驗證了允許工作間斷有利于項目縮短總工期；允許資源波動有利于減少項目總費用。在考慮工作可間斷和資源可波動雙因素的影響下，管理者可根據(jù)項目的具體要求有針對性地得到最佳的項目調(diào)度方案。