周國華, 張華珂

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

0 引言

鐵路特長隧道指鐵路工程中長10000米以上的隧道,近年來隧道工程逐漸表現(xiàn)出長大、特長的特點(diǎn)。截止2020年底,我國投入運(yùn)營的特長鐵路隧道209座,總長2811km;在建特長鐵路隧道116座,總長1675km;規(guī)劃特長鐵路隧道340座,總長5078km。特長隧道常常是關(guān)鍵工程,對于工程按時(shí)完工和降低成本意義重大。然而目前特長隧道施工進(jìn)度計(jì)劃大多基于人工經(jīng)驗(yàn)編制,輔助坑道的數(shù)量和位置等缺少科學(xué)高效的決策方法。

隧道工程是施工作業(yè)在空間上連續(xù)且不斷重復(fù)進(jìn)行的重復(fù)性項(xiàng)目[1],傳統(tǒng)CPM等網(wǎng)絡(luò)計(jì)劃方法在編制這類工程進(jìn)度計(jì)劃時(shí)具有諸多缺陷,如破壞了其施工連續(xù)性特點(diǎn)[2]、只能用時(shí)間維度表達(dá)工程進(jìn)度等[3]。線性計(jì)劃方法(Linear Scheduling Method, LSM)由于其能在時(shí)間和空間兩個(gè)維度上表達(dá)工程項(xiàng)目施工進(jìn)度等優(yōu)點(diǎn)而被廣泛應(yīng)用于重復(fù)性項(xiàng)目中。如GEORGE[4]研究了基于LSM的資源均衡問題。TANG等[1]在LSM框架下提出了包含多種優(yōu)化目標(biāo)的約束規(guī)劃模型。

軟邏輯最早由TAMIMI和DIEKMANN[5]提出,相較于固定邏輯而言,軟邏輯指工序在施工單元的執(zhí)行順序可以變化,而非固定。EL-SERSY[6]指出,通常情況下,帶軟邏輯關(guān)系的工序在不同單元上可以同時(shí)發(fā)生或者交換發(fā)生順序。

特長隧道通常開挖輔助坑道來增加工作面實(shí)現(xiàn)“長隧短打”,增加工作面則引起工序在不同單元上同時(shí)發(fā)生,施工方向的改變又使工序發(fā)生的順序產(chǎn)生變化,此時(shí)隧道邏輯施工順序表現(xiàn)為軟邏輯。軟邏輯關(guān)系會引起關(guān)鍵路線改變從而縮短工期,但它在具備這種優(yōu)點(diǎn)的同時(shí)增加了問題的復(fù)雜性[7],對求解算法也具有更高的要求。FAN等[8]在工序施工隊(duì)數(shù)量和規(guī)模存在多種模式的情況下,構(gòu)建了基于遺傳算法的軟邏輯調(diào)度優(yōu)化模型。張立輝等[7]針對三類離散時(shí)間費(fèi)用權(quán)衡問題,提出了帶有軟邏輯、多模式的項(xiàng)目調(diào)度優(yōu)化模型并采用遺傳算法進(jìn)行求解。王偉鑫等[9]構(gòu)建了基于軟邏輯關(guān)系的工期-成本多目標(biāo)調(diào)度優(yōu)化模型,運(yùn)用通過云模型改進(jìn)后的遺傳算法求解問題。ZOU和ZHANG[10]考慮了施工隊(duì)在不同單元轉(zhuǎn)移時(shí)會產(chǎn)生額外的時(shí)間和成本,建立了基于約束規(guī)劃的軟邏輯調(diào)度模型。已有軟邏輯研究成果的應(yīng)用對象主要為施工作業(yè)空間沒有物理限制的工程,如橋梁工程等,其單元的施工順序既可相互交換,又可并行施工。相較而言,特長隧道作業(yè)空間較為封閉,其存在的軟邏輯關(guān)系主要是多工作面并行施工,且同一工作面施工單元必須相連,施工順序約束與橋梁工程有很大不同, 如圖1。因此,需要結(jié)合隧道工程特點(diǎn),從新的視角研究具有軟邏輯關(guān)系的特長隧道多工作面進(jìn)度計(jì)劃問題。

圖1 不同工程施工特點(diǎn)對比

實(shí)施多工作面施工時(shí),項(xiàng)目工期縮短使得管理成本等間接成本減少,但同時(shí)會引起額外的資源投入導(dǎo)致直接成本增加,進(jìn)而可能提高項(xiàng)目總成本[11]。如何對工期和成本進(jìn)行權(quán)衡是管理者關(guān)注的核心問題。離散時(shí)間-費(fèi)用權(quán)衡問題包括三個(gè)子問題:(1)工期受限下成本最小化;(2)成本受限下工期最小化;(3)構(gòu)建時(shí)間-費(fèi)用的Pareto最優(yōu)解集。本文聚焦于工期受限下成本最小化的問題,以期為施工單位在滿足建設(shè)方提出的工期要求下控制施工成本提供一定指導(dǎo)。

基于特長隧道多工作面施工表現(xiàn)出的軟邏輯關(guān)系以及項(xiàng)目工期和成本的背反關(guān)系,提出工期受限下施工成本最小化的進(jìn)度計(jì)劃優(yōu)化模型。針對帶有軟邏輯關(guān)系的離散時(shí)間-權(quán)衡問題求解的復(fù)雜性以及隧道工程規(guī)模龐大的特征,提出改進(jìn)的遺傳算法對模型進(jìn)行求解。最后,通過鐵路特長隧道算例驗(yàn)證模型的有效性和算法的優(yōu)越性。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

1.2 假設(shè)條件

(1)輔助坑道形式為斜井、豎井或橫洞;

(2)可利用輔助坑道單向施工正洞或雙向同時(shí)施工正洞;

(3)各班組中每個(gè)員工和機(jī)械的工效及成本相同[8];

(4)增加工作面引起額外的人工成本和機(jī)械成本[8]。

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

隧道施工進(jìn)度計(jì)劃模型優(yōu)化目標(biāo)為最小化隧道施工成本C,由正洞施工人工成本、機(jī)械成本、材料成本,輔助坑道成本以及間接成本三部分組成。

(1)

(2)

(3)

(4)

(5)

(6)

T≤Tmax

(7)

1≤wp

(8)

yp∈{0,1},p=1,…,2M+1

(9)

zj∈{0,1},j=1,…,2M+2

(10)

(11)

2 算法設(shè)計(jì)

離散時(shí)間-費(fèi)用權(quán)衡問題屬于NP-hard問題[12],精確算法難以對其求解。遺傳算法由于其具有較好的解決NP-hard問題的能力而被廣泛運(yùn)用于離散時(shí)間-費(fèi)用權(quán)衡問題的研究中。本文采用自適應(yīng)的交叉、變異概率和災(zāi)變算子以增強(qiáng)遺傳算法的全局搜索能力。同時(shí),為了增強(qiáng)局部搜索能力,將變異算子改進(jìn)來提高變異后解的質(zhì)量。

2.1 算法基本要素

(1)編碼與解碼

圖3 染色體示意圖

(2)初始化種群

每段染色體在各自定義域范圍內(nèi)隨機(jī)生成值,重復(fù)Pop次,構(gòu)成初始種群。其中,Pop為種群規(guī)模。由于初始種群的質(zhì)量對于求解結(jié)果影響較大,因此當(dāng)初始種群所有個(gè)體都不滿足截止工期約束時(shí),重新生成初始種群。

(3)適應(yīng)度函數(shù)

在種群中,適應(yīng)度值越高的個(gè)體越優(yōu)。適應(yīng)度函數(shù)取成本的倒數(shù),對于違反截止工期約束的個(gè)體,令其適應(yīng)度值為足夠小的數(shù)。

(4)選擇算子與精英保留

采用輪盤賭選擇算子。同時(shí),為保證算法的收斂性,采用精英保留策略。對于每一代種群,將當(dāng)代種群中適應(yīng)度值最高的染色體直接復(fù)制進(jìn)入下一代,替換下一代適應(yīng)度值最小的染色體。

(5)自適應(yīng)交叉算子

對于第一段染色體(分段點(diǎn)位置),交叉方式為:隨機(jī)選擇交叉點(diǎn),染色體在交叉點(diǎn)處斷開,父代1分為[Pa1,Pb1],父代2分為[Pa2,Pb2]。保持父代1交叉點(diǎn)前的基因Pa1不變,交叉點(diǎn)后的基因依次選擇父代2中與Pa1不相同的基因,形成子代1;保持Pa2不變,交叉點(diǎn)后的基因依次選擇父代1中與Pa2不相同的基因,形成子代2。對于后三段染色體,分別對每段染色體進(jìn)行單點(diǎn)交叉。

運(yùn)用自適應(yīng)交叉概率。采用變形的sigmiod函數(shù)調(diào)整概率,使得在遺傳前期交叉概率較大,加強(qiáng)算法的搜索能力,而在后期概率減小,保護(hù)優(yōu)秀個(gè)體不被破壞;對于個(gè)體而言,讓適應(yīng)度值更高的個(gè)體更容易發(fā)生交叉,使優(yōu)良基因片段更容易傳播,避免早熟現(xiàn)象。遺傳代數(shù)為t時(shí)第i次交叉的概率見式(12)。

(12)

檢驗(yàn)生成的子代染色體,如果違反截止工期約束則放棄子代,保留父代。

(6)多重檢驗(yàn)的變異算子

對每段染色體分別進(jìn)行基本位變異,特別地,對于第一段染色體,當(dāng)隨機(jī)生成的基因與父代中任一基因相同時(shí),重新生成該基因。采用自適應(yīng)的變異率,將式(12)中的pc1,pc2分別替換為pm1,pm2(0

為了增強(qiáng)算法的局部搜索能力,對變異后的個(gè)體進(jìn)行檢驗(yàn)。第一,判斷子代個(gè)體是否滿足截止工期約束;第二,判斷子代個(gè)體適應(yīng)度值是否大于父代種群中的最差值。任何一個(gè)條件不滿足則放棄子代,保留父代。

(7)改進(jìn)的災(zāi)變算子

為了增強(qiáng)算法的全局搜索能力,引入災(zāi)變算子。對災(zāi)變方式進(jìn)行改進(jìn)。災(zāi)變條件和災(zāi)變方式設(shè)計(jì)如下:1)災(zāi)變條件:當(dāng)連續(xù)Ca代種群中最高適應(yīng)度值相同時(shí),發(fā)生災(zāi)變;2)災(zāi)變方式:在原有種群中隨機(jī)選擇比例為pz的個(gè)體,其余1-pz個(gè)體重新生成。將種群中適應(yīng)度最差的個(gè)體替換為保留的精英個(gè)體,形成新種群。

(8)算法終止條件

當(dāng)算法迭代次數(shù)達(dá)到Mt終止算法,輸出最優(yōu)值和最優(yōu)解。

2.2 算法求解步驟

Step1輸入工程進(jìn)度和成本相關(guān)參數(shù),輸入遺傳算法參數(shù),種群規(guī)模Pop、最大迭代次數(shù)Mt,交叉概率pc1,pc2,變異概率pm1,pm2,災(zāi)變參數(shù)Ca,pz。

Step2生成初始種群。令進(jìn)化代數(shù)t=1。

Step3計(jì)算適應(yīng)度值并執(zhí)行精英保留。

Step4執(zhí)行輪盤賭選擇操作。執(zhí)行交叉操作,隨機(jī)選擇兩條染色體,判斷是否進(jìn)行交叉,循環(huán)Pop/2次。執(zhí)行變異操作,隨機(jī)選擇一條染色體,判斷是否執(zhí)行變異操作,循環(huán)Pop次。

Step5判斷是否執(zhí)行災(zāi)變算子,若是則對Step4中生成的種群進(jìn)行災(zāi)變;否則跳過該步驟。令t=t+1。

Step6判斷:若t>Mt,轉(zhuǎn)Step7;t≤Mt,轉(zhuǎn)Step3。

Step7進(jìn)化完成,輸出第Mt代的最優(yōu)值及相應(yīng)最優(yōu)解。

3 算例分析

以鐵路特長隧道工程數(shù)據(jù)為算例。算法編程在MATLAB R2018b上實(shí)現(xiàn)。

3.1 算例描述

鐵路特長隧道全長18226米,為了滿足工期要求,采用開挖輔助坑道、增加工作面的方式來縮短工期。增加的工作面的數(shù)量、施工范圍和方向的改變會引起隧道邏輯施工順序的變化,該特長隧道施工順序從而表現(xiàn)為軟邏輯。以該鐵路特長隧道工程數(shù)據(jù)對模型和算法的有效性進(jìn)行驗(yàn)證。

將該特長隧道按圍巖級別劃分施工單元,單元長度超過300米時(shí),以300米為界進(jìn)行細(xì)分,單元工作量和圍巖情況見表1。不同施工模式下正洞進(jìn)度指標(biāo)見表2,正洞自身成洞指從隧道進(jìn)、出口開挖,不利用輔助坑道,其與利用輔助坑道開挖的速率不同。備選輔助坑道數(shù)量為5,不同工作面數(shù)量下不同模式對應(yīng)的成本信息見表3。不同位置處輔助坑道施工時(shí)間及成本見表4。工程間接成本率ICR為20000元/天。截止工期Tmax為810天。

表2 正洞施工進(jìn)度指標(biāo)

表4 輔助坑道備選位置施工時(shí)間及成本

3.2 求解結(jié)果

運(yùn)用提出的改進(jìn)遺傳算法求解,設(shè)置算法參數(shù)如下:種群規(guī)模Pop為100,自適應(yīng)交叉概率pc1為0.9,pc2為0.5,自適應(yīng)變異概率pm1為0.1,pm2為0.001,災(zāi)變參數(shù)Ca為10,pz為0.1。經(jīng)過多次試驗(yàn)設(shè)置最大進(jìn)化次數(shù)Mt為1000代,以在保證解的有效性的同時(shí)算法具有較高的運(yùn)行效率。進(jìn)度計(jì)劃輸出結(jié)果見表5。

表5 進(jìn)度計(jì)劃輸出結(jié)果

求解結(jié)果表明:共需開挖3個(gè)輔助坑道,設(shè)置7個(gè)工作面,總工期為805天。總成本為1.65×109元,其中,正洞施工人工成本2.98×108元,機(jī)械成本3.98×108元,材料成本9.16×108元,輔助坑道開挖成本1.75×107元,間接成本1.61×107元。

運(yùn)用提出的算法得出了滿足截止工期前提下,施工成本最小化的特長隧道施工進(jìn)度計(jì)劃以及成本構(gòu)成信息,模型和算法的有效性得以驗(yàn)證。

3.3 算法對比

為測試本文算法,保持其它參數(shù)不變,設(shè)計(jì)規(guī)模和截止工期不同的算例。單元規(guī)模N包括60,80,100,單元從表1中隨機(jī)抽取并隨機(jī)排列。截止工期的設(shè)置方式如下:首先計(jì)算出無輔助坑道進(jìn)、出口工作面以最小速率施工時(shí)的最長工期LT,再計(jì)算所有工作面同時(shí)以最大速率施工時(shí)的最短工期UT,最后設(shè)置截止工期Tmax=UT+(LT-UT)θ,其中,θ表示截止工期的松弛度,θ∈{0.25,0.5,0.75}。

對于每個(gè)算例,將提出的改進(jìn)遺傳算法(IGA)、標(biāo)準(zhǔn)遺傳算法(GA)和粒子群算法(PSO)各運(yùn)行20次,仿真結(jié)果見表6。取θ=0.5時(shí)三種規(guī)模下各算法的運(yùn)行結(jié)果進(jìn)行比較,見圖4。GA中交叉概率設(shè)置為0.9,變異概率為0.1;PSO中慣性權(quán)重為0.8,個(gè)體學(xué)習(xí)因子和群體學(xué)習(xí)因子均為2,最大速度為1,其余參數(shù)和輸入數(shù)據(jù)與3.2中一致。運(yùn)算環(huán)境為操作系統(tǒng)為Windows 10,處理器為Intel Core i7-8565U,CPU主頻1.99GHZ,內(nèi)存為8GB的個(gè)人電腦。

表6 算法仿真結(jié)果

由表6可以看出,三種算法分別運(yùn)行20次,IGA得到的平均值和最小值均較GA和PSO更小,證明IGA具有更強(qiáng)的尋優(yōu)能力。另外,由圖4可知,隨著問題規(guī)模增大,GA和PSO在求解時(shí)極易陷入局部最優(yōu),且PSO得出的解的波動性較大,而IGA求得的解更小且更加穩(wěn)定。在運(yùn)行速度上,IGA較于傳統(tǒng)的GA更快,這是由于IGA優(yōu)化了GA的搜索機(jī)制,提高了運(yùn)行效率。IGA的速度不及PSO是因?yàn)镻SO無需進(jìn)行遺傳算法中的交叉變異等運(yùn)算。以上結(jié)果說明所提的IGA對于大規(guī)模隧道進(jìn)度計(jì)劃優(yōu)化問題具有較好的尋優(yōu)能力和較快的運(yùn)行速度。

4 結(jié)論

針對多工作面的特長隧道進(jìn)度計(jì)劃優(yōu)化問題,構(gòu)建了工期受限下施工成本最小化的軟邏輯進(jìn)度計(jì)劃優(yōu)化模型,設(shè)計(jì)了自適應(yīng)的交叉和變異概率、多重檢驗(yàn)的變異算子和改進(jìn)的災(zāi)變算子對算法進(jìn)行優(yōu)化,并基于不同算例開展了實(shí)驗(yàn)研究。結(jié)果表明:(1)提出的軟邏輯施工進(jìn)度計(jì)劃優(yōu)化模型和算法能夠有效地應(yīng)用于特長隧道工程,優(yōu)化后的進(jìn)度計(jì)劃能夠?yàn)槭┕挝粚?shí)際施工提供一定參考。(2)改進(jìn)后的遺傳算法相較于標(biāo)準(zhǔn)遺傳算法和粒子群算法具有更強(qiáng)的全局尋優(yōu)能力,在運(yùn)行速度上比標(biāo)準(zhǔn)遺傳算法更快,在求解大規(guī)模特長隧道進(jìn)度計(jì)劃優(yōu)化問題上表現(xiàn)出更好的性能。

本研究適用于輔助坑道為斜井、豎井或橫洞的情形,當(dāng)輔助坑道為平導(dǎo)加橫通道時(shí),需要根據(jù)平導(dǎo)超前開挖情況調(diào)整施工順序,將通過進(jìn)一步研究對其完善。