周国华, 张华珂

(西南交通大学 经济管理学院,四川 成都 610031)

0 引言

铁路特长隧道指铁路工程中长10000米以上的隧道,近年来隧道工程逐渐表现出长大、特长的特点。截止2020年底,我国投入运营的特长铁路隧道209座,总长2811km;在建特长铁路隧道116座,总长1675km;规划特长铁路隧道340座,总长5078km。特长隧道常常是关键工程,对于工程按时完工和降低成本意义重大。然而目前特长隧道施工进度计划大多基于人工经验编制,辅助坑道的数量和位置等缺少科学高效的决策方法。

隧道工程是施工作业在空间上连续且不断重复进行的重复性项目[1],传统CPM等网络计划方法在编制这类工程进度计划时具有诸多缺陷,如破坏了其施工连续性特点[2]、只能用时间维度表达工程进度等[3]。线性计划方法(Linear Scheduling Method, LSM)由于其能在时间和空间两个维度上表达工程项目施工进度等优点而被广泛应用于重复性项目中。如GEORGE[4]研究了基于LSM的资源均衡问题。TANG等[1]在LSM框架下提出了包含多种优化目标的约束规划模型。

软逻辑最早由TAMIMI和DIEKMANN[5]提出,相较于固定逻辑而言,软逻辑指工序在施工单元的执行顺序可以变化,而非固定。EL-SERSY[6]指出,通常情况下,带软逻辑关系的工序在不同单元上可以同时发生或者交换发生顺序。

特长隧道通常开挖辅助坑道来增加工作面实现“长隧短打”,增加工作面则引起工序在不同单元上同时发生,施工方向的改变又使工序发生的顺序产生变化,此时隧道逻辑施工顺序表现为软逻辑。软逻辑关系会引起关键路线改变从而缩短工期,但它在具备这种优点的同时增加了问题的复杂性[7],对求解算法也具有更高的要求。FAN等[8]在工序施工队数量和规模存在多种模式的情况下,构建了基于遗传算法的软逻辑调度优化模型。张立辉等[7]针对三类离散时间费用权衡问题,提出了带有软逻辑、多模式的项目调度优化模型并采用遗传算法进行求解。王伟鑫等[9]构建了基于软逻辑关系的工期-成本多目标调度优化模型,运用通过云模型改进后的遗传算法求解问题。ZOU和ZHANG[10]考虑了施工队在不同单元转移时会产生额外的时间和成本,建立了基于约束规划的软逻辑调度模型。已有软逻辑研究成果的应用对象主要为施工作业空间没有物理限制的工程,如桥梁工程等,其单元的施工顺序既可相互交换,又可并行施工。相较而言,特长隧道作业空间较为封闭,其存在的软逻辑关系主要是多工作面并行施工,且同一工作面施工单元必须相连,施工顺序约束与桥梁工程有很大不同, 如图1。因此,需要结合隧道工程特点,从新的视角研究具有软逻辑关系的特长隧道多工作面进度计划问题。

图1 不同工程施工特点对比

实施多工作面施工时,项目工期缩短使得管理成本等间接成本减少,但同时会引起额外的资源投入导致直接成本增加,进而可能提高项目总成本[11]。如何对工期和成本进行权衡是管理者关注的核心问题。离散时间-费用权衡问题包括三个子问题:(1)工期受限下成本最小化;(2)成本受限下工期最小化;(3)构建时间-费用的Pareto最优解集。本文聚焦于工期受限下成本最小化的问题,以期为施工单位在满足建设方提出的工期要求下控制施工成本提供一定指导。

基于特长隧道多工作面施工表现出的软逻辑关系以及项目工期和成本的背反关系,提出工期受限下施工成本最小化的进度计划优化模型。针对带有软逻辑关系的离散时间-权衡问题求解的复杂性以及隧道工程规模庞大的特征,提出改进的遗传算法对模型进行求解。最后,通过铁路特长隧道算例验证模型的有效性和算法的优越性。

1 问题描述及数学模型

1.1 问题描述

1.2 假设条件

(1)辅助坑道形式为斜井、竖井或横洞;

(2)可利用辅助坑道单向施工正洞或双向同时施工正洞;

(3)各班组中每个员工和机械的工效及成本相同[8];

(4)增加工作面引起额外的人工成本和机械成本[8]。

1.3 数学模型

隧道施工进度计划模型优化目标为最小化隧道施工成本C,由正洞施工人工成本、机械成本、材料成本,辅助坑道成本以及间接成本三部分组成。

(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 算法设计

离散时间-费用权衡问题属于NP-hard问题[12],精确算法难以对其求解。遗传算法由于其具有较好的解决NP-hard问题的能力而被广泛运用于离散时间-费用权衡问题的研究中。本文采用自适应的交叉、变异概率和灾变算子以增强遗传算法的全局搜索能力。同时,为了增强局部搜索能力,将变异算子改进来提高变异后解的质量。

2.1 算法基本要素

(1)编码与解码

图3 染色体示意图

(2)初始化种群

每段染色体在各自定义域范围内随机生成值,重复Pop次,构成初始种群。其中,Pop为种群规模。由于初始种群的质量对于求解结果影响较大,因此当初始种群所有个体都不满足截止工期约束时,重新生成初始种群。

(3)适应度函数

在种群中,适应度值越高的个体越优。适应度函数取成本的倒数,对于违反截止工期约束的个体,令其适应度值为足够小的数。

(4)选择算子与精英保留

采用轮盘赌选择算子。同时,为保证算法的收敛性,采用精英保留策略。对于每一代种群,将当代种群中适应度值最高的染色体直接复制进入下一代,替换下一代适应度值最小的染色体。

(5)自适应交叉算子

对于第一段染色体(分段点位置),交叉方式为:随机选择交叉点,染色体在交叉点处断开,父代1分为[Pa1,Pb1],父代2分为[Pa2,Pb2]。保持父代1交叉点前的基因Pa1不变,交叉点后的基因依次选择父代2中与Pa1不相同的基因,形成子代1;保持Pa2不变,交叉点后的基因依次选择父代1中与Pa2不相同的基因,形成子代2。对于后三段染色体,分别对每段染色体进行单点交叉。

运用自适应交叉概率。采用变形的sigmiod函数调整概率,使得在遗传前期交叉概率较大,加强算法的搜索能力,而在后期概率减小,保护优秀个体不被破坏;对于个体而言,让适应度值更高的个体更容易发生交叉,使优良基因片段更容易传播,避免早熟现象。遗传代数为t时第i次交叉的概率见式(12)。

(12)

检验生成的子代染色体,如果违反截止工期约束则放弃子代,保留父代。

(6)多重检验的变异算子

对每段染色体分别进行基本位变异,特别地,对于第一段染色体,当随机生成的基因与父代中任一基因相同时,重新生成该基因。采用自适应的变异率,将式(12)中的pc1,pc2分别替换为pm1,pm2(0

为了增强算法的局部搜索能力,对变异后的个体进行检验。第一,判断子代个体是否满足截止工期约束;第二,判断子代个体适应度值是否大于父代种群中的最差值。任何一个条件不满足则放弃子代,保留父代。

(7)改进的灾变算子

为了增强算法的全局搜索能力,引入灾变算子。对灾变方式进行改进。灾变条件和灾变方式设计如下:1)灾变条件:当连续Ca代种群中最高适应度值相同时,发生灾变;2)灾变方式:在原有种群中随机选择比例为pz的个体,其余1-pz个体重新生成。将种群中适应度最差的个体替换为保留的精英个体,形成新种群。

(8)算法终止条件

当算法迭代次数达到Mt终止算法,输出最优值和最优解。

2.2 算法求解步骤

Step1输入工程进度和成本相关参数,输入遗传算法参数,种群规模Pop、最大迭代次数Mt,交叉概率pc1,pc2,变异概率pm1,pm2,灾变参数Ca,pz。

Step2生成初始种群。令进化代数t=1。

Step3计算适应度值并执行精英保留。

Step4执行轮盘赌选择操作。执行交叉操作,随机选择两条染色体,判断是否进行交叉,循环Pop/2次。执行变异操作,随机选择一条染色体,判断是否执行变异操作,循环Pop次。

Step5判断是否执行灾变算子,若是则对Step4中生成的种群进行灾变;否则跳过该步骤。令t=t+1。

Step6判断:若t>Mt,转Step7;t≤Mt,转Step3。

Step7进化完成,输出第Mt代的最优值及相应最优解。

3 算例分析

以铁路特长隧道工程数据为算例。算法编程在MATLAB R2018b上实现。

3.1 算例描述

铁路特长隧道全长18226米,为了满足工期要求,采用开挖辅助坑道、增加工作面的方式来缩短工期。增加的工作面的数量、施工范围和方向的改变会引起隧道逻辑施工顺序的变化,该特长隧道施工顺序从而表现为软逻辑。以该铁路特长隧道工程数据对模型和算法的有效性进行验证。

将该特长隧道按围岩级别划分施工单元,单元长度超过300米时,以300米为界进行细分,单元工作量和围岩情况见表1。不同施工模式下正洞进度指标见表2,正洞自身成洞指从隧道进、出口开挖,不利用辅助坑道,其与利用辅助坑道开挖的速率不同。备选辅助坑道数量为5,不同工作面数量下不同模式对应的成本信息见表3。不同位置处辅助坑道施工时间及成本见表4。工程间接成本率ICR为20000元/天。截止工期Tmax为810天。

表2 正洞施工进度指标

表4 辅助坑道备选位置施工时间及成本

3.2 求解结果

运用提出的改进遗传算法求解,设置算法参数如下:种群规模Pop为100,自适应交叉概率pc1为0.9,pc2为0.5,自适应变异概率pm1为0.1,pm2为0.001,灾变参数Ca为10,pz为0.1。经过多次试验设置最大进化次数Mt为1000代,以在保证解的有效性的同时算法具有较高的运行效率。进度计划输出结果见表5。

表5 进度计划输出结果

求解结果表明:共需开挖3个辅助坑道,设置7个工作面,总工期为805天。总成本为1.65×109元,其中,正洞施工人工成本2.98×108元,机械成本3.98×108元,材料成本9.16×108元,辅助坑道开挖成本1.75×107元,间接成本1.61×107元。

运用提出的算法得出了满足截止工期前提下,施工成本最小化的特长隧道施工进度计划以及成本构成信息,模型和算法的有效性得以验证。

3.3 算法对比

为测试本文算法,保持其它参数不变,设计规模和截止工期不同的算例。单元规模N包括60,80,100,单元从表1中随机抽取并随机排列。截止工期的设置方式如下:首先计算出无辅助坑道进、出口工作面以最小速率施工时的最长工期LT,再计算所有工作面同时以最大速率施工时的最短工期UT,最后设置截止工期Tmax=UT+(LT-UT)θ,其中,θ表示截止工期的松弛度,θ∈{0.25,0.5,0.75}。

对于每个算例,将提出的改进遗传算法(IGA)、标准遗传算法(GA)和粒子群算法(PSO)各运行20次,仿真结果见表6。取θ=0.5时三种规模下各算法的运行结果进行比较,见图4。GA中交叉概率设置为0.9,变异概率为0.1;PSO中惯性权重为0.8,个体学习因子和群体学习因子均为2,最大速度为1,其余参数和输入数据与3.2中一致。运算环境为操作系统为Windows 10,处理器为Intel Core i7-8565U,CPU主频1.99GHZ,内存为8GB的个人电脑。

表6 算法仿真结果

由表6可以看出,三种算法分别运行20次,IGA得到的平均值和最小值均较GA和PSO更小,证明IGA具有更强的寻优能力。另外,由图4可知,随着问题规模增大,GA和PSO在求解时极易陷入局部最优,且PSO得出的解的波动性较大,而IGA求得的解更小且更加稳定。在运行速度上,IGA较于传统的GA更快,这是由于IGA优化了GA的搜索机制,提高了运行效率。IGA的速度不及PSO是因为PSO无需进行遗传算法中的交叉变异等运算。以上结果说明所提的IGA对于大规模隧道进度计划优化问题具有较好的寻优能力和较快的运行速度。

4 结论

针对多工作面的特长隧道进度计划优化问题,构建了工期受限下施工成本最小化的软逻辑进度计划优化模型,设计了自适应的交叉和变异概率、多重检验的变异算子和改进的灾变算子对算法进行优化,并基于不同算例开展了实验研究。结果表明:(1)提出的软逻辑施工进度计划优化模型和算法能够有效地应用于特长隧道工程,优化后的进度计划能够为施工单位实际施工提供一定参考。(2)改进后的遗传算法相较于标准遗传算法和粒子群算法具有更强的全局寻优能力,在运行速度上比标准遗传算法更快,在求解大规模特长隧道进度计划优化问题上表现出更好的性能。

本研究适用于辅助坑道为斜井、竖井或横洞的情形,当辅助坑道为平导加横通道时,需要根据平导超前开挖情况调整施工顺序,将通过进一步研究对其完善。