考虑作业空间干涉的工程项目时间-成本均衡优化研究

李 迁, 陶 莎, 周晓园，盛昭瀚

(南京大学工程管理学院，江苏 南京 210093)

1 引言

工程施工进度计划以及资源的有效配置是施工项目管理的重要科学问题[1-2]。除了人力、设备等资源，施工现场的空间也是重要资源之一。实践表明，施工活动安排不合理引起的活动作业空间不足、作业空间相互占用易造成作业效率低下、返工、安全隐患等不良后果，大大阻碍了工程目标的实现[3-5]。因此，在优化施工调度方案时充分考虑施工活动的空间需求以及空间约束条件对工程管理实践具有一定的现实意义。

目前大多学者借助可视化仿真技术对施工中的空间干涉问题开展研究[6-8]。这类研究通常基于已知的调度方案，借助数字化技术识别空间干涉，并通过制定规则来局部地调整计划方案，以消除或解决空间干涉问题。Moon[6]等人提出一种序列检查算法来避免并行活动之间发生空间干涉。Choi[7]等人设计了一种作业空间规划的流程框架，包含识别4D BIM、识别作业空间、表征空间占用、识别空间干涉、解决空间干涉五个阶段。Zhang[8]等人利用GPS定位系统和BIM实时地判断人员的作业空间，进而识别潜在的空间干涉并及时采取防范措施。然而，这类方法缺乏对调度计划进行预先的整体性优化设计。此外，少部分学者对具体资源(如人、机械设备)的运行方位和动作轨迹等细节上进行建模，避免其作业过程中发生冲突[3,9]。例如，Isaac[9]等人采用时间-空间图描述员工的动态运动过程，将员工作业路径表示为粒度函数，对并行活动进行时间和空间的分配。该类研究从资源运动的微观视角，而非从整体工程项目的宏观视角根据活动的空间需求信息优化工程调度方案。

资源受限的项目调度问题(RCPSP)是运筹学和运作管理领域的重要研究方向，旨在研究考虑资源供给限制的项目调度优化问题，其应用领域涉及建设工程、工业生产、物流交通等[10]。RCPSP将资源类型大致分为可再生资源(如人力资源)和非再生资源(如原料)，空间资源属于一类有限的可再生资源[11]。一些学者结合RCPSP与有限工程空间资源开展研究。Frene[12]等人设计空间资源的请求活动(Call activity)、中间活动(Interval activity)、释放活动(Release activity)三类活动，基于RCPSP并提出采用串行方案生成机制的启发式算法解决问题。Semenov[13]等人在RCPSP中考虑空间拥堵和作业流扰动约束，建立以工程工期最短为目标的优化模型。Tao[14]等人将空间拥堵作为优化目标之一，建立时间-成本-拥挤度多目标工程调度优化模型。

本文创新性地从空间干涉降低施工作业效率的现实出发，以工期和成本为目标，基于RCPSP相关理论，建立考虑空间干涉的工程调度时间-成本双目标优化模型。与以往研究假设工期已知不同，该模型定义了活动的作业效率曲线和实际工期变量。此外，不同于传统求解RCPSP算法的序列或权重编码方式，本文针对性地设计了相对延迟编码方式和相应解码机制，采用NSGA-II算法有效求解问题。

2 问题定义与数学模型

采用AON(Activity-On-Node)网络表达工程项目，记为G={N,A}。集合N={0,1,…,n,n+1}表示n+2个活动，其中活动0和n+1分别表示虚拟开始和结束活动。集合P⊂N×N表示活动之间的工序关系，若i是j的紧前活动，则(i,j)∈P。每个活动i有|Mi|种可选择的执行模式，定义每个活动的备选模式集合Mi={1,2,…,|Mi|}，m∈Mi。假设资源有|K|种，定义资源集合K={1,2,…,|K|}，k∈K。工程项目的计划时间范围(Plan Horizon)为[0,T]，为方便算法设计，将时间离散化成时段集合，记为T={1,…,|T|}，t∈T。本研究基于假设：1)活动的作业效率仅受空间干涉影响并与空间干涉程度呈负相关；2)活动实际工期仅受作业效率影响，不考虑其它影响因素；3)每个活动所需的作业空间已知。

本文的研究问题可概括为：在已知活动工序、计划工期以及作业空间需求等参数条件下，考虑活动执行过程中的空间干涉对作业效率和实际工期的影响，如何合理选择各活动的执行模式并安排活动执行时间，以达到工程工期和成本均最小化的目标。

2.1 作业空间干涉

作业空间干涉(Workspace Interference)或简称空间干涉是指在活动执行过程中，其作业空间被其他活动占用，从而对自身产生一定的干扰和影响。空间干涉发生要求两个或两个以上的活动在同一时间有相同的空间需求，即作业空间重叠[6]。假设任意活动i的作业空间记为Ωi，函数v(Ωi)表示该作业空间的体积，则活动i的资源密度表示为资源占用的空间体积与总体作业空间体积之比，如公式(1)。

(1)

其中，υk表示每单位资源k占用的空间体积。Rimk表示活动i执行模式m所需资源k的数量。xim为0/1决策变量，当选择模式m执行活动i时，xim=1；否则，xim=0。

进一步地，定义任意t时段上活动i的空间干涉程度Si(t)为其它活动在t时段内与活动i重叠空间内的资源密度加和，如公式(2)[13-14]。

Si(t)=∑i′∈Ni(ρi′·v(Ωi∩Ωi′)·yit·yi′t),∀i,k

(2)

其中，Ωi∩Ωj表示两作业空间Ωi和Ωj的重叠部分。yit为0/1变量，当活动i在t时段上执行时，yit=1；否则，yit=0。可以看出，对于任意活动i,i′，若v(Ωi∩Ωi′)=0(作业空间不重叠)或者yit·yi′t=0(作业时间不重叠)，则空间干涉为0。

2.2 作业效率函数

活动的作业效率和实际工期均是受空间干涉影响的变量。在无空间干涉的理想情况下，活动i在执行模式m时的计划工期为Wim，即Wim是完成活动i所需的总工作量或总工时。而在空间干涉的影响下，活动作业效率随时间改变，记效率函数为ei(t)∈[0,1]。参考作业效率与其它因素(如学习速度、经验)的函数关系[15]，本文采用Sigmoid函数定义ei(t)，如公式(3)。

ei(t)

(3)

(4)

(5)

为了更容易理解，以图1的效率函数为例，计划工期等于效率函数曲线与时间轴围成的阴影区域的面积。可以看出，在第t时段上活动i是否结束与第t-1时段及之前各时段内的累计工作量有关。当累计工作量小于总工作量要求，则活动i未完成，第t时段将继续执行活动i；否则，活动i完成且完工时间为t-1。基于这一思想，初始化t为活动i的开始时间，循环上述操作直至活动i完成，即能确定其结束时间。下一节将基于该思想设计算法的编码方式和解码机制。

图1 作业效率和实际工期的关系示意图

2.3 数学模型

本文同时考虑工期和成本两目标，建立如下双目标数学规划模型。其中，公式(6)计算项目工期fT，即虚拟结束活动的开始时间。公式(7)计算总成本fC，总成本由活动执行成本和延期成本两部分构成。其中，活动执行成本等于所有活动成本之和∑i,m∈Mixim·Cim(Cim表示活动i在模式m下执行时所需的直接成本)；延期成本等于超期时间max{tn+1-Tdl,0}乘以延迟单位时间的惩罚成本CP(截止工期记为Tdl)。约束(8)是工序关系，即任意活动的开始时间不得早于其前序活动的完成时间。约束(9)定义0/1变量yit，即当活动i在t时段上正在执行时，yit=1；否则为0。由于每个活动只能选择一种执行模式，因而约束(10)成立。此外，模型还包括上述介绍的公式(1)至公式(5)。

minF=(fT,fC)

(6)

fC=∑i,m∈Mixim·Cim+CP·max{fT-Tdl,0}

(7)

(8)

∀i∈N,t∈T

(9)

∑i,m∈Mixim=1

(10)

约束(1)-(5)

3 元启发式算法

NSGA-II是经典的多目标优化算法之一，它具有全局优化性好、通用性强和易于实现等优势，且在算法收敛性、鲁棒性等方面展现出良好的性能，因而在经济管理、工业工程等领域得到了广泛应用[16]。本文采用NSGA-II求解问题，由于未涉及改变NSGA-II算法框架和算子，关于NSGA-II算法介绍请参考相关文献，此处不再赘述。

求解RCPSP的启发式算法的编码方式一般包括活动排序和活动权重两种，排序和权重均体现活动占用资源的优先权。传统的解码机制通常采用贪婪准则，即在资源允许的情况下活动尽早开始。这种方式难以灵活控制活动执行时间上的重叠程度。然而，本文研究的问题需要更精细地控制活动执行时间，从而调整空间干涉对作业效率及实际工期的影响。因此，传统的RCPSP编码和解码方法难以适用本文问题。为此，本文针对性地设计了基于相对延迟编码方式和相应解码机制。

编码由2n个整数元素构成，记为DML=(Δ1,…,Δn,m1,…,mn)。其中，前n个元素中，Δi表示活动i的相对延迟时间，即相对于活动i的最早可开始时间再延迟Δi单位时间，活动i才开始执行。活动i的最早可开始时间指的是活动i的前序活动全部完成的时刻。Δi=0表示活动i不延迟，即其前序活动均完成时立即开始执行。Δi的取值范围为{0,1,…,MAXΔ}，参数MAXΔ表示最大延迟时间。DML后n个元素为活动的模式选择，mi∈Mi。由于NSGA-II算法的染色体x=(x1,…,x2n),x∈[Minx,Maxx]为实数向量。针对本文问题特征，设定染色体的每个基因位的取值区间分别为xj∈[0,1],∀j∈{1…n}和xj∈[1,Max|Mi|],∀j∈{n+1…2n}。接着，根据公式(11)和(12)对任意实数向量x进行离散化处理，将x映射为DML。其中，函数round表示四舍五入。

Δi=round(xi·MAXΔ),∀i∈{1…n}

(11)

mi=round(xi+n),∀i∈{1…n}

(12)

图2 解码机制

4 案例分析

4.1 案例描述和参数设置

某办公楼装饰工程由19个活动构成的，活动基本信息如表1所示[3,17]，各活动的作业空间布局如图3所示。其他参数设置如表2，不妨称为标准参数设置。

表1 活动参数表

表1 活动参数表

图3 空间示意图

表2 实验的参数设置

算法在软件MATLAB R2013a上编译，算例实验在CPU主频2.20GHz，内存8GB，64位操作系统配置的个人计算机上运行实现。

4.2 实验结果分析

4.2.1 标准参数下的结果分析

基于表2参数执行NSGA-II算法，得到一个包含7个解的Pareto集合，解集在目标空间内的分布如图4所示。工期和成本在一定程度上相互冲突，尤其在工期小于125或大于144时，工期与成本近乎成线性关系。当工期小于125时，成本与工期的冲突性更大，即每压缩一单位时间所付出的成本更高。以目标取值为(125, 259)的最优解为例，活动的效率曲线如图5所示，每个活动开始于第一次效率大于零的时刻，结束时刻是在效率再次降为零且此后始终为零时，活动的工期为活动结束时刻与开始时刻之差。从效率曲线图上不仅可以看出每个活动的开始作业时间和工期，还可以看出每个活动的作业效率随时间和项目发展的变化情况，可见效率曲线图比传统甘特图更详尽。

图4 Pareto解集

图5 各活动的效率曲线(横轴为时间，纵轴为效率)

4.2.2 与传统方法对比分析

基于表2参数设置执行NSGA-II算法，重复实验10次，共计求得38个最优解。由于空间干涉主要影响活动调度决策，因此令所有解的模式选择决策保持不变，采用传统正向调度法求解工程调度方案，计算所得方案的时间和成本目标值。箱线图6统计了NSGA-II所得的方案相比于传统方法所得方案在时间和成本两方面的节省，计算公式为(传统方案时间/成本目标-NSGAII方案时间/成本目标)÷传统方案时间/成本目标。相比于传统方法得到的方案，NSGA-II所得方案在工期目标上平均节省3.09%，在95%的情况下NSGA-II的方案具有更短的工期；在成本目标上，NSGA-II的方案平均节省1.01%，在26%的情况下传统方法所得方案的成本更大且增加的成本是延期成本，这是由于实验设定活动执行模式不变，两组解的活动执行成本相同。实验表明，传统方法引起工程延期主要是由于在安排活动时忽略了空间干涉的影响，使得调度方案执行时的空间干涉增大，引起作业效率降低。综上，本文在工程调度问题中考虑空间干涉影响，对工程进度和成本两方面目标均更为有利。

图6 考虑与不考虑空间干涉的方案目标对比

4.2.3 最大延迟时间参数影响分析

为了评估不同MAXΔ取值下算法所得解集的优劣，首先选择一个解集作为比较基准，视为精确Pareto解集。本文通过随机运行算法10次，汇集所有解并从中删除重复解和支配解，最终得到由7个非支配解构成的Pareto解集，其目标向量(完工时间，成本×102)分别为(123，281)，(125，275)，(126，259)，(129，253)，(130，249)，(149，243)，(151，241)。与精确Pareto解集相比，对不同MAXΔ取值下的NSGA-II求得的解集从五方面指标进行评价，分别是无可行解次数、可行解数量、非支配解占比、收敛性(即离精确Pareto前沿的距离)和算法运行时间。令参数MAXΔ=10,20,30,…,70，其它参数按标准设置。不同MAXΔ取值下，每组实验重复进行10次，五个指标的均值如下表3所示。可以看出，算法平均得到的可行解数量随着MAXΔ增加而逐渐减少。甚至当MAXΔ≥50时，随着MAXΔ增长，算法运行失败(即找不到可行解)的次数明显增加。这是因为MAXΔ增长使解空间范围大幅扩大，算法搜索非支配解甚至可行解的难度都大大增加。然而，并非令MAXΔ取值越小就对算法性能有利，从表3的非支配解占比和收敛性指标可以看出，尽管MAXΔ取值越小，算法得到的可行解数量更多，但解的最优性表现欠佳。例如当MAXΔ取值为10和20时，算法得到的非支配解数量较少且离精确Pareto前沿距离较远。这是由于MAXΔ取值越小，搜索的解空间范围越小，从而容易遗漏搜索范围之外的最优解。从表3可以看出，当MAXΔ取值为40时，非支配解占比和收敛性均是最高，分别是22.86%和0.77。在算法运行时间方面，各组实验的算法平均耗时相差不大，说明对于本案例问题，MAXΔ对算法的运行时间影响较小。综上，MAXΔ取值过大或者过小都不利于Pareto解的质量。针对本文案例，MAXΔ取值为40时的算法性能表现最好。

表3 不同MAXΔ取值的算法性能比较

*收敛性指标的计算除去了无可行解的实验结果。

5 结语

工程活动的作业空间干涉会引起资源作业相互干扰，导致作业效率降低，从而对工程总体进度和成本产生不利的影响。本文在工程调度优化问题中考虑空间干涉对作业效率的影响，定义活动作业效率和活动实际工期关于空间干涉的函数，建立时间-成本双目标优化的工程调度模型。为有效求解模型，采用NSGA-II元启发式算法并针对性地设计相对延迟编码方式和解码机制。对某一装饰工程案例研究发现，与传统调度方法相比，本文提出的方法可以更有效地加快工程进度，节省施工成本。通过多组对比实验探讨算法参数MAXΔ对算法性能的影响，结果表明MAXΔ取值过大或过小都不利于算法性能。针对本文的工程案例，MAXΔ取值为40时算法性能最好。本研究对于提高施工方案质量、改善施工作业环境、保证施工安全等方面均具有一定的理论和实践意义。未来可进一步将优化模型、元启发式算法与可视化信息技术结合，设计工程调度的计算实验平台，为工程实践者提供技术支持。