装配式构件施工现场吊装调度建模与优化

李文杰， 黄 春， 刘占省， 蔺宏远， 何 阳

(1.北京工业大学 建筑工程学院，北京 100124；2.山东省建筑设计研究院有限公司，山东 济南 250001)

建筑业是支撑我国经济发展的重要传统产业，但近十年我国建筑企业的平均利润率一直徘徊在3.37%～3.50%之间[1]。全球范围内建筑业劳动生产率的增长仅为1%，而制造业则为3.6%[2]。行业发展的要求与相对落后的管理和生产水平之间的矛盾已经日益突出，迫切需要利用现代信息技术实现建筑业的转型升级与持续健康发展[3]。针对于此，各国相继提出建筑业发展战略计划，如《美国基础设施重建计划》、英国的《建造2025》、德国的《数字化设计与建造发展路线图》[4]、我国的《建筑业信息化发展纲要》和《中国建造2035战略研究》等计划[5]。

建筑业的发展与四次工业革命的典型创新技术紧密结合，经历了人力、机械化、自动化及数字化等阶段[6]。尤其在第四次工业革命中，以数字化、网络化和智能化为标志的新一代信息技术，正在与各产业深度融合[4]。虽然施工现场具备数字化基础，但智能化建造过程目前仍处于起步阶段。相对于制造业的生产过程，传统工程项目施工过程需要大量的人员参与，具有较高的复杂性和不确定性。而目前的智能算法则侧重于优化具有较高规律性和重复性的工序。相对于其他施工工序，塔吊吊装过程中所涉及的因素较为单一，建筑材料在施工场地中的存储位置及种类、塔吊位置和塔司等一般不会发生较大变动，促成了吊装过程的规律性与可预测性。

塔吊是施工现场中最重要的吊装设备，其吊装效率很大程度上决定了现场的施工效率，而吊装效率则很大程度上取决于塔吊的调度方案。在施工现场，塔吊调度方案是按照物料需求出现的时间先后进行排序，然后凭借信号工个人经验，通过对讲机指挥塔司运行。但是传统的调度方法缺乏对各个物料需求空间位置的系统考虑，造成了塔吊运输路径的不合理规划以及重复运输。因此，本研究拟以塔吊的调度方案为研究对象，建立优化模型，制定塔吊的调度计划，提升塔吊运输效率并由此促进智能化建造的发展。

1 装配式构件吊装问题分析

研究假定塔吊每次运输单个构件，且塔吊的布置可以覆盖作业面，并满足构件的起吊重量。图1描述了装配式构件吊装过程中吊钩的运行轨迹，首先由初始位置D1移动至物料存储位置S2，装载物料M2，而后将物料运输到需求位置D1，卸载物料M2，完成首个运输任务；然后吊钩由需求位置D1出发，移动至物料存储位置S3，装载物料M1，运输并卸载于需求位置D2；以此类推，吊钩完整的路径为：D1→S2→D1→S3→D2→S1→D2。

图1 吊钩运行路径

国内外学者将塔吊的调度问题抽象为运筹学中经典的旅行商问题(Travel Salesman Problem，TSP)。通过将物料存放点和需求点视为TSP问题中的一个个城市，以减少塔吊完成所有物料运输任务的距离为目标，最终得到塔吊完成任务的顺序，即吊钩经过物料存放点和需求点的顺序[7,8]。Zavichi等[8]将此类问题定义为吊机服务排序问题(Crane Service Sequencing Problem，CSSP)，并通过整数规划(Integer Programming，IP)建模。随后，Tork[9]又将物料需求任务的截止时间衡量物料需求任务的紧急程度，并利用遗传算法求解。Monghasemi等[10]认为优化物料需求任务的等待时间对实际建设产生的效果更好，并基于博弈论(Game Theory)与和声搜索算法(Harmony Search)均衡了吊装任务的等待时间。Huang等[11]利用混合整数线性规划(Mixed-Integer Linear Programming，MILP)，将物料存储位置和塔吊位置作为优化模型的决策变量，并考虑了吊钩的初始位置、吊机的运输能力等因素，得到了CSSP问题的全局最优解，极大地减少了塔吊运输时间。

尽管MILP算法可以得到最优解，但传统的分支定界算法(Branch-and-Bound)求解时间会随着问题规模的增大而呈指数趋势增加，并且模型忽略了吊装物料次序对施工工序的影响。尤其以装配式建筑为例，若模型忽略了施工顺序对构件吊装顺序的要求，则造成优化后的调度方案不合理。例如，预制梁若在预制墙体安装前被运输到物料需求点，则将导致工序无法搭接，引起构件的二次运输，造成运输资源浪费。

因此，本研究在前人研究基础上，针对装配式构件吊装调度问题，基于MILP建立优化模型。在考虑施工顺序的前提下，优化塔吊的吊运顺序，减少塔吊吊装构件的运输时间，并考虑吊钩初始位置与物料供应位置的影响。研究随后设计一种改进遗传算法(Improved Genetic Algorithm)对优化模型进行求解，大幅减少求解时间，同时保证优化结果的质量，增强了整个优化模型的工程实用性。

2 装配式构件吊装调度模型构建

2.1 塔吊运行时间估算模型

相关研究[8～11]采用了Zhang等[12]提出的简化模型来估算塔吊在两点间的运行时间。吊钩运行轨迹分解为：吊臂的切向运动、吊钩沿吊臂的径向运动以及吊钩的竖向运动，其中吊臂的切向运动与吊钩的径向运动组成了水平方向的运动。如图2所示，当物料供应点、物料需求点以及塔吊位置坐标已定的情况下，根据式(1)～(3)计算出三者之间的直线距离ρ(Si,Dj)，ρ(Si,Tck)，ρ(Dj,Tck)。

图2 塔吊水平向运动

(1)

(2)

(3)

(4)

根据余弦定理，式(5)计算得到了吊臂的切向运动时间。

0≤arccos(·)≤π

(5)

(6)

图3 塔吊竖向运动

(7)

(8)

2.2 装配式构件吊装调度模型

2.2.1 参数与决策变量

(1)参数：αi,m∈{0，1}表示物料供应位置i存储有物料m；εr,j,m∈{0，1}表示物料需求任务r为需求位置j需要物料m；λj∈{0，1}表示吊钩初始位置位于需求位置j。

(2)决策变量：xs,r∈{0，1}表示物料运输任务r的执行顺序为s；δr,i,j,m∈{0，1}表示物料需求任务r的运输路径为由供应位置i运输物料m至需求位置j；ys,i,j,m∈{0,1}表示吊钩在执行顺序s下将物料m由物料供应位置i运输至物料需求位置j；χs,j,m∈{0，1}表示吊钩在执行顺序s下将物料m运输至物料需求位置j；zs,j,i∈{0，1}表示塔吊在执行顺序s下的任务衔接路径为由物料需求位置j至物料供应位置i。

2.2.2 目标函数

塔吊完成所有物料需求任务所花费的总时间为所有物料运输路径与任务衔接路径之和计算所得，其表达式为：

(9)

式中：R为塔吊执行任务总数；I为物料供应位置总数；J为物料需求位置总数；M为物料种类总数；Ti,j为物料运输时间；TUnloading为物料卸载操作时间；TLoading为物料装载操作时间。

2.2.3 限制条件

(1)选择物料供应位置

式(10)限制了选择的物料供应位置必须存储有需求任务所需要的物料种类。

(10)

若物料存储位置i没有存储有物料种类m的构件，即αi,m=0，则该存储位置不能成为需求任务r(需要物料种类m)的备选供应位置，即δr,i, j,m=0。式(11)限制了物料运输路径只选择一个物料供应位置。

(11)

(2)排序物料运输任务

式(12)限制了塔吊每次运输都完成一个物料需求任务；式(13)限制了每个物料需求任务必定会被满足。

(12)

(13)

(3)确定执行顺序下的物料运输路径

式(14)表示了每个执行顺序下的物料运输路径。

2-xs,r-δr,i, j,m≥1-ys,i, j,m，

(14)

若物料需求任务r的执行顺序为s，即xs,r=1，且该物料需求任务r的运输路径为由供应位置i运输物料m至需求位置j，即δr,i, j,m=1，那么吊钩在执行顺序s下将物料m由物料供应位置i运输至需求位置j，即ys,i, j,m=1。式(15)表示了每个执行顺序下的运输目的地j以及运输物料种类m；

(15)

(4)限制构件运输顺序符合安装顺序

式(16)限制了同一物料需求点的物料运输顺序必须满足装配式构件安装次序。例如吊钩在顺序s将物料m运输至需求位置j，即χs, j,m=1，在此后顺序t(t>s)不能运输施工顺序靠前的物料u(m>u)，即χt, j,u=0。

(16)

式中：J*为存在多个物料需求任务的需求位置。物料种类序号与构件安装顺序一致。

(5)确定执行顺序下的任务衔接路径

式(17)表示了两个物料运输任务之间的衔接路径。

2-χs, j,m-ys+1,i,o,u≥1-zs+1, j,i，

(17)

若吊钩在顺序s下将物料m运输至需求位置j，即χs, j,m=1，而且吊钩在顺序s+1的物料运输路径为将物料u由物料供应位置i运输至需求位置o，即ys+1,i,o,u=1，那么吊钩在顺序s+1的任务衔接路径为由需求位置j至物料供应位置i，即zs+1, j,i=1。式(18)限制了任务衔接路径最多只能选择一个的物料供应位置。

(18)

(6)根据吊钩初始位置确定首个任务衔接路径

式(19)表示了首个执行顺序的任务衔接路径。

2-λj-ys=1,i,o,m≥1-zs=1, j,i，

(19)

若吊钩初始位置在需求位置j，即λj=1，首个执行顺序的物料运输路径为将物料m由物料供应位置i运输至需求位置j，即ys=1,i,o,m=1，因此首个执行顺序的任务衔接路径为由需求位置j至物料供应位置i，即zs=1, j,i=1。式(20)限制了首个任务衔接路径起始点为吊钩初始位置。

(20)

3 装配式构件吊装调度模型的求解

遗传算法(Genetic Algorithm，GA)来源于进化论和群体遗传学[13]，是一种寻求全局最优解的随机并行搜索算法。由于具有较强的全局寻优能力、鲁棒性以及易用性，遗传算法在工程优化[14～6]领域得到了广泛应用。本文提出的遗传算法对染色体编码方式进行了改进，而且加入了染色体处理机制，考虑了构件施工次序的限制。图4显示了改进遗传算法计算流程。

图4 改进遗传算法计算流程

3.1 确定编码方式

本文染色体编码长度为2N(N为物料需求任务数)，由两部分组成：第一部分由N个物料需求任务的执行顺序组成，第二部分由选择的N个物料供应位置编号组成。以5个物料需求任务为例，如图5所示，该染色体前5个基因为执行顺序，按照需求任务R3→R1→R5→R4→R2的顺序完成；后5个基因为物料供应点S位置，表示需求任务R1的供应位置为S3，任务R2的供应位置为S1，依此类推。

图5 染色体基因组成

3.2 生成初始种群

由于塔吊物料运输特殊性，因此需要保证生成的初始种群必须是可行的，即满足式(10)～(13)的限制。因此，执行顺序基因段通过M次(种群数量)随机生成N个(物料需求任务数量)不重复的正整数，即满足式(12)(13)。良好的初始种群会加速寻优的进度，优化模型的目的是寻求构件吊运时间最短的调度方案。所以每个物料需求任务所匹配的供应位置应在满足限制式(10)(11)的基础上，若与需求位置的距离越近，则被选择的概率越大。根据式(21)计算符合条件的物料供应位置被选择的概率Pb。

(21)

式中：Tb为符合条件的供应位置与需求位置的运输时间；B为符合条件的供应位置总数；D为常数。

3.3 染色体处理机制

染色体处理机制是为了保证生成的染色体符合施工次序的要求，即满足式(16)的限制。如上述所述，当同一物料需求位置存在多个物料需求任务时，任务间的优先级按照物料种类划分。以预制构件吊装为例，物料吊装顺序为预制墙体→叠合梁→叠合板→楼梯，如果顺序出现差错，就会导致施工任务无法正常进行。因此，染色体处理是在生成初始种群和新一代种群后，检验同一需求位置的不同需求任务的执行顺序是否满足约束条件，如果不满足则进行调整。

3.4 计算个体适应度

在遗传算法中，适应度用来衡量解的优劣程度，同时也作为选择算子执行功能的依据。在计算适应度前要将染色体解码为问题的解，重新将遗传算法空间映射到问题空间。本文的解码操作为：(1)按照染色体中的供应位置编号与物料需求任务所对应的位置编号匹配，作为物料运输路径，即式(11)；(2)按照染色体中的执行顺序，将物料运输路径进行排序，即式(14)；(3)按照排序好的物料运输路径，得到所有的任务衔接路径，即式(17)～(19)；(4)计算该染色体对应的目标函数，即式(9)。在本模型中所对应的目标函数为物料运输时间，物料运输总时间越短，则代表了该调度方案越优，其适应度值越大。因此，适应度ft按式(22)计算。

ft=D/Obj(t)

(22)

式中：D为常数；Obj(t)为个体的目标函数值。

3.5 种群进化

3.5.1 选择算子与精英保留策略

本文采用轮盘赌法作为选择算子，并以精英保留策略辅助种群的进化。若个体的适应度越大，则被轮盘赌法选择的几率越大，被保存至下一代种群的几率越大。精英保留策略通过保留种群中适应度最大的个体作为精英个体，在交叉算子与变异算子执行完毕后，用精英个体替换适应度最小的个体。因此保证了优良个体的基因结构不会被破坏。

3.5.2 交叉算子

为保证交叉后的染色体仍为可行的，本文使用自适应交叉概率调节机制下的部分映射交叉(Partially-Mapped Crossover, PMX)和两点交叉(Two-Point Crossover)作为交叉算子，并使用自适应参数调整机制，根据个体的适应度对交叉概率进行调整[17,18]。式(23)表示若当前个体的适应度大于种群的平均适应度，则表明当前个体属于较优个体，为了保证其优良的基因结构不会被破坏，降低其交叉概率；若当前个体的适应度较小，则保持交叉概率不变，促进该个体与其他个体的交叉，以期产生更好的个体，发挥全局寻优的功能。

(23)

PMX算子针对执行顺序基因段进行交叉操作，使子代个体的执行顺序不会出现重复或缺少。PMX算子要求随机产生两个交叉点，两个父代个体交叉点之间确定一个匹配段，利用匹配段的基因建立映射关系，生成两个子代个体。双点交叉算子则针对供应位置基因段进行交叉。两点交叉算子与PMX算子所产生的交叉点一致，通过交换父代个体中交叉点之间的基因段，产生子代个体新的基因段。如图6所示，假设随机产生的交叉点为2，4，PMX算子将两个父代个体中2～4位置的基因匹配段建立映射关系：R1-R3，R4-R2，R5-R4，依次将父代P1中基因值R1-R3，R4-R2，R5-R4的顺序互换，得到子代C1的执行顺序为R1-R3-R2-R4-R5；同理，交换父代P2的执行顺序，得到子代个体C2。双点交叉也选择2～4位置的基因为交换段S1-S2-S2，S2-S1-S3，互换父代个体P1，P2的交换段，得到子代个体C1，C2的物料供应位置为S3-S2-S1-S3-S1，S2-S1-S2-S2-S3。

图6 交叉算子示例

3.5.3 变异算子

本文为增强变异算子的局部搜索能力，采用了逆序变异算子、插入变异算子、交换变异算子和单点变异算子。执行顺序基因段的变异主要采用逆序变异算子、插入变异算子和交换变异算子。图7描述了执行顺序基因段变异算子的操作过程。

图7 执行顺序基因段的变异算子

供应位置基因段的变异采用单点变异算子，而且为保证变异后个体的可行性，变异后的物料供应位置必须存储有对应物料需求任务所需的物料类型。图8描述了供应位置基因段变异算子的具体操作。

图8 供应位置基因段的变异算子

3.6 终止条件

当满足预定的终止条件，则终止遗传算法求解；若不满足终止条件，则继续染色体处理。本文设定的终止条件为达到最大迭代次数时，计算自动停止。

3.7 算法表现

本文采用5个算例对改进遗传算法的表现进行了分析，算例的规模分别为5，10，15个物料需求任务。商业求解器Gurobi求得的解为该问题的全局最优解，可作为GA算法表现的对比标杆。GA中参数取值如下：最大交叉概率pmax=0.8，自适应系数p=0.3，变异概率pmu=0.018，种群数量M为50，最大迭代次数为200次。对于每个算例，将GA在同样的参数下计算20次，并取所有计算结果的平均值作为该算例的计算结果。实验基于Python 3.6，计算平台为Intel Core i5-8279U@2.4 GHz 16 GB RAM。

如表1所示，随着优化问题规模的扩大，使用Gurobi求解该模型的时间呈指数型增长。特别地，算例5在计算超过7200 s后上下界仍未收敛，其结果为Gurobi求解器求得的上界。随着问题规模的增大，精确算法的计算时间无法达到实际工程应用的要求，而GA则可以在较短计算时间求得近似最优解。

表1 Gurobi与GA的比较

4 案例分析

4.1 案例背景

研究应用于北京某装配式建筑施工场地，根据施工计划选取了部分物料需求任务作为本文的案例。该项目采用的场地布置方案是根据场地建筑面积量、施工条件、工期以及成本等因素综合考虑确定。塔吊位置与选型方案可以覆盖整个施工作业面，并满足构件的起吊重量与吊装任务量。在确定初始方案后，利用BIM(Building Informa-tion Modeling)技术分析了驾驶员的可视角度，确定了最终的塔吊位置，减少了驾驶员的盲区范围，增强了吊装过程的安全性。为了减少构件吊装时间，提升塔吊运输效率，项目设置了多个物料供应位置。依据施工场地及周边空间条件、施工要求、管理人员经验，结合优化算法和BIM技术的空间分析和可视化功能来制定，保证了吊装过程的高效性。图9为该施工场地的平面布置图，场地布置了1个塔吊和4个物料供应位置，物料供应位置的详细信息如表2所示。

图9 场地平面布置

表2 物料供应位置坐标及存储材料种类

案例中共有12个物料需求任务，分布于9个物料需求位置，物料运输任务的详细信息如表3所示。假设无紧急物料需求，即各物料需求点的优先级一致。如上文所述，同一物料需求位置的不同物料需求任务应该按照物料种类进行排序，使其符合施工过程的要求。例如物料需求点D4所对应的两个需求任务为R1和R6，所需物料种类分别为M3(叠合板)和M4(楼梯)，为了施工作业的正常顺序，应当在吊运并安装物料M3后才能吊运物料M4，所以需求任务R6的执行顺序必然在任务R1之后。物料需求点D5和D6中存在同样的情况。本案例的解共包含有827，714，764，800种组合，其中执行顺序有12!(479001600)种组合，供应位置选择有1728种组合。

表3 物料需求位置坐标及吊装任务信息

4.2 案例结果

图10展示了GA的计算过程，优化结果为62.38 min，计算用时4.32 s。同样，将该案例使用Gurobi软件求解MILP模型，优化结果为62.38 min，计算用时6160 s。因此，本文提出的改进遗传算法具有良好的寻优能力和工程实用性。

图10 GA计算过程

表4给出了最优调度方案，表中的第1列给出了物料运输任务执行顺序，第3列与第4列给出了吊钩运行的详细信息，第5列为吊钩运行时间，第6列为吊钩的累积运行时间，包含吊钩运行时间与装、卸载物料的操作时间(设置为单位时间/1min)。由表4可知，需求任务R1和需求任务R6的执行顺序分别为1，2，满足施工方案的要求。同样地，需求任务R4，R12，R9，R11也都满足此限制。

5 结 语

本文基于MILP算法构建了一个装配式构件吊运调度优化模型，并设计了一种改进遗传算法用于求解该问题。优化调度结果可以为实际施工中塔吊调度方案提供参考，以期达到节省运输时间、降低成本及提高施工效率的目的，同时也为工程机械自动化的实现提供新的思路。本研究取得的主要成果如下：

(1)建立了考虑吊钩初始位置、物料供应位置以及构件安装顺序的装配式场地塔吊调度优化模型；

(2)通过改进编码方式和引入染色体处理机制，设计了一个新的改进遗传算法求解该优化模型；

(3)通过遗传算法与商业求解器的比较，验证了改进遗传算法可以在较短时间内将大规模问题求解，并得出近似最优的调度方案。

但是该算法在面对求解任务规模大于15的调度问题时，依旧容易陷入局部最优解，在未来的研究中应当加入新的扰动算子或结合其他优化算法辅助跳出局部最优解。并且，塔吊的运行时间估算模型是基于经验拟定的，而实际中塔吊运行的制约因素较多，因此在以后的研究中可以利用机器学习方法，提高塔吊运行轨迹与时间的准确性。