基于混合整数线性规划的塔吊选型与布置优化

刘 猛， 黄 春， 王京京， 王文琦， 张 睿

(1. 中建三局国际工程公司(大项目管理)， 北京 100013； 2. 北京工业大学 建筑工程学院， 北京 100124)

建筑业作为支撑我国经济发展的重要产业，其总产值在近5年内的年均增长率约为10.85%[1]，但建筑企业的利润率仅从3.48%上升到3.61%[2]。为节约建筑成本和改进施工管理方法，建筑业提出了“数字建造”的概念。其中，以BIM技术为代表的信息集成管理平台，在施工方案模拟分析和可视化方面应用逐渐广泛[3]。在模拟仿真的基础上，合理优化施工计划能够更大限度利用数字化工程信息的价值，从而推动建筑企业利润率的提高。然而，现有BIM软件主要解决建筑实体三维模型信息的储存和显示问题，缺乏施工场地空间的量化分析能力，使得相关优化研究难以从中获得详细的量化数据。本文以群塔选型与布置优化问题为例，说明空间量化分析在BIM技术中的应用。

塔吊作为施工场地垂直运输的核心设备，其运行效率主要受塔吊与场内设施的空间约束关系影响。塔吊选型与布置问题属于运筹学的二次分配问题(Quadratic Assignment Problem，QAP)[4]主要解决在保证材料运输效率满足施工进度要求的前提下，以最小成本建立施工场地内材料垂直运输网络(供应点-塔吊-需求点)。因此，通过优化供应点-塔吊-需求点的空间关系，有利于提高塔吊运行效率。根据制造业对场地布置的研究，适当的场地布置可以减少20%～60%的材料运输费用[5]，因此优化供应点-塔吊-需求点的空间关系对降低建筑成本也具有较强促进作用。传统塔吊选型与布置方法依靠工程人员的实践经验，通过反复调整塔吊型号和位置，才能得到相对合理的塔吊选型与布置方案[6]，决策过程和方案质量受人员素质和资源投入的影响很大。在大型公共建筑体量越来越大的发展趋势[7]下，塔吊数量逐渐增多且空间约束关系愈发复杂，传统方法更加难以兼顾决策效率和方案质量的平衡，因此有必要探索更高效和精准的塔吊选型与布置方法。

为弥补传统方法的不足，相关研究人员应用优化算法建立一系列优化模型对塔吊选型与布置。Zhang等[8]利用塔吊、需求点和供应点三者间几何关系和塔吊的速度参数，建立了塔吊运行时间的计算模型。Tam等[9]利用遗传算法，通过优化塔吊和物料存储点的位置，缩短了塔吊完成吊运任务的时间。Yeoh和Chua[10]通过优化塔吊的选型与布置方案来缩短塔吊运行时间，从而减少了塔吊使用费用。Ji和Leite[11]建立了基于BIM平台的塔吊选型与布置方案自动审核机制，用以检查塔吊布置方案是否符合现行规范的要求。Briskorn和Dienstknecht[12]利用混合整形规划，在考虑障碍物对塔吊影响的情况下，最小化塔吊使用费用。上述研究，一方面缺乏施工场地空间的量化数据，无法精确模拟塔吊在施工场地的空间约束关系；另一方面仅将塔吊作为独立运行的运输工具，缺乏对塔吊工作范围重叠区域内吊装任务合理分配的考虑。针对上述问题，本文基于BIM技术对施工场地空间进行量化分析，并建立塔吊选型与布置的混合整数线性规划(Mixed Integer Linear Programming，MILP)优化模型，从而实现塔吊资源的合理配置。

1 施工场地空间量化数据

“数字建造”依赖于精确的量化数据实现数字化表达、分析和模拟过程，而可靠的量化数据也是优化建模的重要条件。施工场地是由拟建建筑、物料堆场和临时道路等相关设施组成的连续空间。但以往塔吊选型与布置优化模型大多将场内设施简单抽象为“点”，用以表达所在区域的位置坐标。单纯的“点”是一维图形，难以表达空间体量及其拓扑关系，因此施工场地的BIM数据应是能反映长度、面积和体积的空间体量。此外，对空间体量的分析处理需要大规模布尔运算，从而对电脑CPU和内存提出极高要求[13]。为此，研究通过空间单元的有序组合，合理表达场地空间的体量范围和拓扑关系，从而实现了连续空间的离散化表达。通过赋予离散空间单元相应的属性参数，可以形成包含施工场地空间特征的离散性量化数据，进而建立场地空间单元数据库。

场地空间单元数据库的建立过程如图1所示：(1)在施工场地BIM模型(图1a)中等间距插入3 m×3 m×3 m标准单元(图1b)，并依次为空间单元编号；(2)基于RevitPythonShell模块作为Revit程序的数据接口，利用Python脚本建立空间单元与Excel数据单元之间的映射关系；(3)将施工场地单元所具有的属性参数储存在Excel的单元(图1c)中，从而形成施工场地单元数据库。以图1d中编号117的单元为例，单元数据库中储存着每个单元的坐标、功能、需求和起吊重量等一系列属性参数。基于场地内拟建建筑、各类设施和塔吊可选位置的分布情况，如图1c中不同背景单元所示，将对应位置的单元归类为建筑单元集合B、材料供给单元集合I、材料需求单元集合J、塔吊可选位置单元集合K和办公区域单元集合W等单元集合，并最终汇总成单元总集C。

图1 施工场地单元数据库的建立过程

通过将连续施工场地离散化的方法，研究在BIM模型中建立了场地空间的离散型量化数据，从而为精确分析材料供需关系和科学配置塔吊资源创造了数据基础。

2 塔吊布置问题的空间量化关系

依托施工场地的空间单元数据库，研究通过分析塔吊与相关区域的空间量化关系建立基于MILP的优化模型，模拟了吊装任务最繁忙阶段塔吊运行情况，从而保证优化结果的可行性；采用分支定界法(Branch and Bound)完成模型的求解过程，保证了优化结果的最优性。基于最优化理论，优化模型一般由约束条件和优化目标两部分组成。模型通过约束条件的限制筛选出优化问题的所有可行解，从而形成可行域；然后利用求解算法在可行域中搜索优化问题的最优解。MILP的约束条件和优化目标中的所有关系表达式都是线性的，且相关变量同时包含整数变量和连续型变量。分支定界法是针对MILP模型的一种搜索和迭代算法，通过不断更新目标下界逐渐缩小搜索范围，从而得到问题的最优解。研究采用Python语言建立优化模型；然利用优化软件Gurobi[14]实现分支定界法的求解过程；最后通过Python脚本和RevitPythonShell模块，将优化结果自动导入到BIM模型中。

2.1 塔吊安全距离约束

由于塔吊吊臂具有绕塔身作圆周运动的运行特点，塔吊布置应考虑塔吊之间以及塔吊与邻近设施的碰撞风险。例如，塔吊吊臂在大风天气应保持能够随风自由转动的状态，以避免风荷载造成过大扭矩导致塔吊坍塌。如果塔吊架设位置不合理，有可能导致其与相邻塔吊或邻近设施发生碰撞事故。为此，模型建立了相应的安全距离约束条件。如图2所示，式(1)～(3)限制了任意两塔吊之间的距离Dk,k′与其中任意塔吊臂长(Rn和Rn′)的差值，应不小于塔吊之间最小安全距离(一般取=2 m)；式(4)(5)限制了位于单元k的塔吊到邻近设施单元w的距离Dw,k与n型号塔吊吊臂长度Rn的差值，应不小于塔吊与邻近设施的最小安全距离υ(υ=3 m)。

2-αk,n-αk′,n′≥1-χk,n,k′,n′，∀k∈K,∀n∈N,∀k′∈K,∀n′∈N,k≠k′

(1)

χk,n,k′,n′(Dk,k′-Rn-)≥0，∀k∈K,∀n∈N,∀k′∈K,∀n′∈N,k≠k′

(2)

χk,n,k′,n′(Dk,k′-Rn′-)≥0，∀k∈K,∀n∈N,∀k′∈K,∀n′∈N,k≠k′

(3)

(4)

ζw,k,n≥αk,n，∀w∈W,∀k∈K,∀n∈N

(5)

式中：0-1变量αk,n为n型号塔吊存在于单元k内；0-1变量χk,n,k′,n′为n和n′型号两塔吊同时分别存在于k和k′两单元内；Dk,k′为位于k和k′两单元内的两台塔吊之间的距离；Rn和Rn′分别为位于k和k′两单元内的两台塔吊的臂长；为塔吊之间最小安全距离；0-1变量ζw,k,n为位于单元k的n型号塔吊与邻近设施单元w满足最小安全距离的要求；Dw,k为位于单元k的塔吊到邻近设施单元w的距离；υ为塔吊与邻近设施的最小安全距离。

图2 安全因素关系示意

2.2 材料供需关系约束

塔吊是施工场地内最主要的垂直运输工具，主要负责将施工材料从材料堆场(供应点)吊运到作业平面(需求点)。为避免二次转运影响塔吊效率[15]，供应点与需求点通常建立直接的材料供需关系。为此，研究建立如下约束条件：

(1)塔吊的起重能力满足材料供应点与需求点的吊装任务重量的要求。塔吊的起吊重量不仅受到塔吊型号控制，而且与起吊点到塔身的距离(小车幅度)相关。如图3中塔吊起重特性曲线所示，塔吊的最大起吊重量随小车幅度的增加而减小。基于该曲线，式(6)计算得出塔吊在其工作范围内各单元处的最大起吊重量，即图3中单元颜色深度所示。式(7)判断了位于单元k的n型号塔吊在供应点i处的最大起吊能力Ci,k,n是否满足该处材料吊装重量Wi的要求(通过0-1变量δi,k,n表示判断结果)。式(8)判断了位于单元k的n型号塔吊能否同时满足供应点i和需求点j的材料吊装重量要求(通过0-1变量εi, j,k,n表示判断结果)。

图3 塔吊起吊重量与小车幅度的关系

Ci,k,n=fn(Di,k)，∀i∈I∪J,∀k∈K,∀n∈N

(6)

(7)

3-δi,k,n-δj,k,n-αk,n≥1-εi, j,k,n，∀i∈I,∀j∈J,∀k∈K

(8)

式中：Ci,k,n为位于单元k的n型号塔吊在单元i处的最大起吊能力；Di,k为单元i到塔吊所在单元k的距离；Wi为塔吊在其工作范围内各单元处的最大起吊重量；0-1变量δi,k,n为位于单元的型号塔吊在单元处的最大起吊能力是否满足该处材料吊装重量的要求；0-1变量εi, j,k,n为位于单元k的n型号塔吊能否同时满足供应点i和需求点j的材料吊装重量要求。

(2)塔吊的位置分布应考虑，材料供应点与需求点对应种类材料的运输任务仅通过一台塔吊独立完成。式(9)(10)保证了供应点可以为需求点提供所需对应种类的材料。式(11)(12)保证了每个供应点与需求点之间的材料吊运任务可以仅由一台塔吊独立完成。

2-λi,m-φj,m≥1-φi, j,m，∀i∈I,∀j∈J,∀m∈M

(9)

(10)

2-εi, j,k,n-φi, j,m≥1-γi,j,k,m,n，∀i∈I,∀j∈J,∀k∈K,∀m∈M,∀n∈N

(11)

(12)

式中：0-1变量λi,m为需求点j需要材料m；0-1变量φj,m为供应点i可以提供材料m；0-1变量φi, j,m为供应点i可以为需求点j提供材料m；γi, j,k,m,n为位于单元k的n型号塔吊可以将材料m从供应点i吊运到需求点j。

2.3 吊装任务分配约束

对于塔吊布置问题，相邻塔吊工作范围难免存在重叠区域，因此需要其共同完成该区域的材料吊装任务。单台塔吊在单位时间内所能完成的吊装任务量(理论吊次)是有限的，通过合理分配重叠区域内材料吊装任务量，可以在一定程度上提高塔吊完成吊装任务的能力，并提高塔吊应对吊装任务量变化的能力。为保证塔吊能在规定时间内完成全部材料吊装任务，模型建立了理论吊次的评估方法和材料吊装任务分配机制，并建立了每台塔吊实际吊次不大于理论吊次的限制条件。由此，研究模拟了施工最繁忙阶段的材料吊装任务量分布情况下塔吊吊装作业的执行情况，从而保证塔吊选型与布置方案在其他任意时刻的可行性。

塔吊理论吊次不仅受塔吊机械性能(型号)的影响，而且与塔吊、供应点和需求点的位置关系有关。研究基于塔吊工作范围内吊装作业的平均运行时间，建立塔吊理论吊次的评估方法。式(13)通过对比单元i到塔吊所在单元k的距离Di,k与n型号塔吊臂长Rn，判断该单元是否处在塔吊工作范围内(通过0-1变量βi,k,n表示判断结果)。式(14)判断了供给点i和需求点j是否同时处在单元k处的n型号塔吊的工作范围内(0-1变量ωi, j,k,n表示判断结果)。基于塔吊工作范围内供应点与需求点的分布情况，即0-1变量ωi, j,k,n的取值情况，式(15)计算得到位于单元k处的n型号塔吊工作范围内所有可能吊装作业的平均运行时间MTk,n。基于吊装作业的平均运行时间，式(16)计算了单元k处的n型号塔吊的理论吊次Fk,n。

(13)

2-βi,k,n-βj,k,n≥1-ωi, j,k,n，∀i∈I,∀j∈J,∀k∈K,∀n∈N

(14)

(15)

(16)

式中：0-1变量βi,k,n和βj,k,n分别为单元i和单元j处在位于单元k的塔吊的工作范围内；0-1变量ωi, j,k,n为供给点i和需求点j是否同时处在单元k处的n型号塔吊的工作范围内；Ti, j,k,n为位于单元k处的n型号塔吊从供给点i运行到需求点j的时间(基于Zhang等[8]的研究)；MTk,n为位于单元k处的n型号塔吊工作范围内所有可能吊装作业的平均运行时间；WT为塔吊每日工作时长，数字2表示塔吊往复作业的实际运行状态。

为了模拟塔吊对每个吊装任务的执行情况，研究假设相邻塔吊可以共同完成某需求点对某类材料的吊装任务量，并由此建立吊装任务分配机制。式(17)～(19)通过建立0-1变量γi, j,k,m,n与整数变量Si, j,k,m,n的映射关系，使得模型可以反映塔吊任意吊装作业的执行路线(从某供应点到某需求点)和执行次数，从而建立了材料吊装任务量在塔吊之间的分配机制。式(20)限制了位于k单元n型号塔吊的实际吊次不大于其理论吊次Fk,n。

Si, j,k,m,n≥γi, j,k,m,n，∀i∈I,∀j∈J,∀k∈K,∀m∈M,∀n∈M

(17)

Si, j,k,m,n≤γi, j,k,m,nN，∀i∈I,∀j∈J,∀k∈K,∀m∈M,∀n∈M

(18)

(19)

(20)

式中：整数变量Si, j,k,m,n为位于k单元n型号塔吊将材料m从供应单元i到需求单元j的次数；Qj,m为需求单元j所需物料m的数量；Hm为塔吊平均每次吊运物料m的数量；「⎤表示向上取整。

2.4 塔吊布置优化目标

在施工企业不断寻求节约建筑成本的背景下，塔吊成本是衡量塔吊选型与布置方案优劣的关键指标。塔吊成本的计算方法如式(21)所示。

(21)

式中：Φn为n型号塔吊的日常费用，包含塔吊租金、修理费、燃料费和人工费等与施工周期相关的成本；Ψn为n型号塔吊的固定费用，包含基础制作费、运输费和安装拆除费等一次性投入；D为塔吊的使用周期。

塔吊作为施工场地内最主要的垂直运输设备，塔吊工作范围充分覆盖施工作业区域有利于提高物料运输的灵活性。式(22)(23)通过分析作业面单元与塔吊覆盖范围的关系，判断作业面单元是否至少处于一台塔吊的工作范围之内。式(24)建立了塔吊覆盖率的统计指标，从而形成了优化模型的第二项优化目标。

(22)

(23)

(24)

式中：0-1变量ρi为单元i被塔吊覆盖；Num为统计单元集合中的元素数量。

对于单台塔吊选型与布置问题，为了充分利用塔吊的运输能力，塔吊工作范围应尽可能完全覆盖作业区域。但对于多台塔吊选型与布置问题，严格要求塔吊工作范围完全覆盖作业区域，有可能导致高昂的塔吊成本。因此，研究基于ε约束法，求解得到塔吊成本与覆盖率的Pareto前沿，从而分析塔吊使用成本与覆盖率之间的影响关系。ε约束法是用于求解多目标优化问题的一种计算方法。该方法按照优化目标的重要程度，选取次要优化目标，通过设定理论下限的方法将其转化为约束条件，从而保证优化结果满足基本工程需求；在此基础上，通过最小化或最大化主要优化目标，得到优化问题的理论最优解；最终通过在一定范围内不断调整次要优化目标理论下限的取值，得到优化问题的最优解集，从而建立主要优化目标与次要优化目标的Pareto前沿曲线。式(25)将塔吊成本设置为主要优化目标，式(26)设定了塔吊覆盖率的理论下限。

minCost=F1(x)，x∈Ω

(25)

Coverage=F2(x)≥ε2,x∈Ω

(26)

式中：F1为与塔吊成本相关的约束集合；F2为与塔吊覆盖率相关的约束集合；x为相关变量集合；Ω为变量可行区间；ε2为塔吊覆盖率的理论下限。

3 模型应用与结果分析

3.1 工程背景

研究针对优化模型在某施工场地的应用效果，分析不同优化目标对塔吊选型与布置最优方案的影响关系。如图4所示，该施工场地内包含A，B，C三栋拟建建筑，单层建筑面积共计39276.5 m2，分为75个施工段(图中编号1～75)，塔吊使用周期12个月。如图5所示，对90000 m2的施工场地空间进行离散化，共形成10000个单元(100×100)。其中包含各类单元的情况如下：建筑物单元4294个，供应点单元42个，塔吊单元62个。每个施工段的材料需求状况通过一个需求点单元表示，共形成75个需求点单元。本文以图4中的10个施工段(4～8，14～18)为例，说明各施工段的吊装任务量，相关数值如表1(正常任务分布)所示。研究选取了5种备选塔吊型号，相关成本指标如表2所示。

图4 施工场地及施工段划分/m

图5 施工场地BIM模型及空间单元分布

表1 部分施工段吊装任务量

表2 塔吊参数

3.2 塔吊使用成本与覆盖范围的Pareto前沿

经试算，在保证布置方案满足所有约束条件的条件下，该施工场地的塔吊覆盖率变化区间为96%～100%。基于ε约束法，研究在此区间内每间隔0.5%选取一个塔吊覆盖率下限(即ε的取值)；依次将每个塔吊覆盖率下限设为约束条件，分别最小化塔吊成本，从而得到塔吊成本与覆盖率的Pareto前沿曲线，如图6中实线(正常任务分布情况)所示，其中共包含12个理论最优方案。图中：方案P1的塔吊使用成本为364.3万元，覆盖率96.18%；方案P12的塔吊使用成本为681.44万元，覆盖率100%；对比可知，塔吊覆盖率提高3.97%，但使用成本增加87.06%。由此说明，严格要求塔吊完全覆盖作业区域有可能导致较高的塔吊成本，从而损害工程效益。分析图6中实线的发展趋势可知，随着塔吊覆盖率的提高，塔吊使用成本增长不断升高，并且在曲线后半段增速极高。因此，合理选择塔吊覆盖率是保证塔吊布置方案经济性的重要保证。

图6 塔吊成本与覆盖率的Pareto前沿

表3 塔吊布置方案及相关指标分析

3.3 局部吊装任务量增加对塔吊布置方案的影响

由于施工进度难以完全依照进度计划进行，很容易出现赶进度的状况。此时，作业区域的每日材料需求量增加，塔吊吊装任务量也相应增加。如果塔吊无法通过合理调整任务量分配情况，将造成吊装任务量无法按时完成，因而影响施工进度。为探究吊装任务量变化对塔吊布置方案的影响，研究增加了A栋建筑局部作业区域的材料需

求量(施工段4～8，14～18)，调整后各施工段的吊装任务量如表1(局部任务增加)所示。

局部吊装任务量增加后，塔吊使用成本与覆盖率的Pareto曲线如图6中虚线所示。正常任务量分布(实线)与局部任务量增加(虚线)条件下的Pareto曲线可知，方案P1失去现实可行性，无法应对任务量的增加；方案P2通过调整塔吊布局，虽然损失了塔吊覆盖率，但保证了方案的可行性；方案P3～P12未受到任务量调整的影响。塔吊理论吊次冗余率是指塔吊理论吊次与塔吊吊装任务量的差值占塔吊理论吊次的比例，反映了塔吊对吊装任务量增加的承受能力。局部任务量调整前后各方案的塔吊理论吊次冗余率如图7所示。由图可知，方案P1和P2的塔吊理论吊次冗余率低于其他方案，因此研究通过分析各方案塔吊理论吊次的利用情况，探究方案P1和P2 出现变化的原因。

图7 局部任务量调整前后塔吊理论吊次冗余率

正常任务量分布条件下，方案P2 的塔吊布置情况如图8所示，各塔吊理论吊次与实际吊次的对比情况如图10所示；局部任务量增加后，方案P2的塔吊布置情况如图9所示，各塔吊理论吊次与实际吊次的对比情况如图11所示。对比可知：随着A栋建筑局部吊装任务量的增大，TC1通过位置调整承担更多新增吊装任务量；TC2也相应承担更多A栋建筑的吊装任务量；为了弥补原本由TC1和TC2承担的B栋建筑吊装任务量，

图8 正常任务量条件下方案P2的三维视图

图9 局部任务量增加后的方案P2的三维视图

图10 正常任务量条件下方案P2塔吊吊装任务分配

图11 局部任务量增加后方案P2塔吊吊装任务分配

TC3和TC4承担更多B栋建筑的吊装任务量；为了减少TC1位置调整造成塔吊覆盖率的影响，TC3～TC6分别进行了位置调整。综上可知，对于理论吊次冗余量较少的塔吊布置方案P2，局部吊装任务量的增加有可能使得塔吊最优布局发生较大变化。

案P3塔吊布置方案不受局部任务量变化的影响。正常任务量分布条件下的方案P3中，各塔吊理论吊次与实际吊次的对比情况如图12所示；局部任务量调整后的方案P3中，各塔吊理论吊次与实际吊次的对比情况如图13所示。对比可知：TC1和TC2承担A栋建筑增加的吊装任务量，相应地减少对B栋建筑的吊装任务量；由于理论吊次冗余量较多，B栋建筑的吊装任务量主要由TC3和TC4承担；TC5和TC6基本不受影响。由此可知：对于理论吊次冗余量较多的塔吊布置方案，可以通过吊装任务量的协调分配承担局部吊装任务量的增加，而不影响布置方案的最优性。

图12 正常任务量条件下的方案P3塔吊吊装任务分配

图13 局部任务量增加后方案P3塔吊吊装任务分配

综上所述，方案P1的理论吊次冗余量过少，使得方案无法应对吊装任务量的增加；方案P2的理论吊次冗余量较少，需要通过调整塔吊布局才能满足吊装任务量增加后的材料需求状况；方案P3～P12拥有足够的理论吊次冗余量，能够承受一定范围内的吊装任务量的增加。

4 结 论

为探索优化算法在“数字建造”中的应用，研究基于BIM技术建立了施工场地的空间量化分析方法，实现了连续空间的离散化表达。基于量化的空间数据，模型建立了塔吊吊装次数评估方法和吊装任务分配机制，从而模拟施工最繁忙阶段的材料吊装任务量分布情况下塔吊吊装作业的执行情况。依靠研究通过分析优化模型对某施工场地塔吊布置的优化效果，得出了塔吊选型与布置问题的如下规律：(1)严格要求塔吊完全覆盖作业区域并不适合所有的工程项目，塔吊使用成本和覆盖率存在理论平衡；(2)各塔吊理论吊次存在适当冗余量时，塔吊可以通过合理分配吊装任务量，在一定范围内应对局部吊装任务量的变化。

以上研究结论说明，基于BIM的施工场地空间量化分析，提高了优化建模的模拟精度和优化效果，从而促进了优化算法在“数字建造”过程中发挥更大的作用。