混合粒子群算法在塔吊合理分配上的应用

徐 洁 张 弘侯亚涛

（1.西安邮电大学自动化学院 西安 710121）（2.中建二局第三建筑工程有限公司 北京 100070）

1 引言

塔吊以其高效、覆盖范围广等特点成为使用最广泛的建筑工程机械之一［1］，但由于塔吊分布是人为决定的，在作业过程中因缺乏科学管理和正确使用，所以会存在利用率低等问题。据建设机械公司的数据显示，2016年第一季度塔吊的平均利用率仅为52.8%，而导致这种现象的原因主要有以下两个方面：1）预留量大，造成塔吊资源浪费；2）预留量刚好，但塔吊调度不合理，需通过加班等措施来保证按时完工。因此，如何提高塔吊利用率是本文要解决的主要问题。

早期针对该问题的研究，采用的方法都是线性规划［2］、动态规划［3］等精确算法，而现有的大多数研究都是结合遗传算法［4］的改进来解决类似问题，但遗传算法计算较为复杂，因此，本文采用一种新的算法—混合粒子群算法（HPSO）［5］。与遗传算法相比，混合粒子群算法是粒子在解空间跟随当前最优的粒子进行搜索，从而能够提高运算速度、加快工期预计进度［6］。

2 问题描述与模型建立

2.1 问题描述

在建筑项目中，塔吊需吊取水泥、木材、钢筋等多种物料，由于物料性质不同，塔吊在作业时分为满载和不满载两种情况。施工时塔吊经常处于满载状态会导致其寿命变短，因此，在实际操作中塔吊作业基本都是处于不满载状态，但这也可能会拖延工期进度。施工方为了解决拖期问题，一般会让塔吊进行混吊等违规操作或者采取延长加班时间的方式，这都会增加施工安全的风险［7］。从安全和塔吊维护的角度考虑，施工现场需要使用合理缩短工期的科学方法，来提高塔吊的利用率，以减少安全风险。

2.2 基于塔吊工期问题优化模型

由于塔吊都是群体作业，作业方式为单一模式，满足计划评审技术（Program Evalu-ation and Review Technique，PERT）网络计划模型的场景［8］，为了优化塔吊作业过程中整个项目的工期，我们可以将塔吊吊取的物料类型模拟成不同的任务，然后将整个项目任务看成一个PERT网络计划工期问题。

2.2.1 目标函数

设某工程项目需塔吊吊取n种物料，吊取这n种物料的工期内塔吊都处于不满载状态，因此我们需要对其工期进行合理压缩，其中吊取物料i的可压缩作业时间为xi，其压缩单位时间塔吊的损坏率为Ci，根据网络压缩的优化目标，目标函数为

2.2.2 基本假定及规定

为了简化模型，假设在对塔吊作业工期进行优化的过程中，网络的关键作业路径不发生变化，关键作业路径如：要用水泥和沙子混合成混凝土，则可利用不同的塔吊分别吊取这两种物料，若需吊取水泥的时间较长，则关键作业路径为吊取水泥所花费的时间，可忽略非关键作业路径上吊取沙子所用的时间。为此，给出如下假设：1）假定塔吊作业过程中压缩工期导致塔吊损坏的损坏率为C；2）关键作业路径上压缩的任务工期应大于等于将要压缩的任务工期；3）每次要压缩关键任务工期时，要保证其压缩量不大于对应的所有非关键作业路径上的工期差；4）考虑塔吊作业持续时间的不确定性，在关键作业路径上，任务工期的压缩量不得大于与其对应的所有非关键作业路径上任务工期的总时差，即压缩水平 a［9］。

2.2.3 约束条件

根据上面假设的条件，为保证在塔吊作业过程中网络的关键作业路径不发生变化，本文采用闭合圈原理，即从关键作业路径的某个任务节点出发，经过有限关键作业路径上的任务和有限非关键作业路径上的任务回到该任务节点构成一个闭合圈，在闭合圈上，所有关键任务的持续时间总和应大于等于闭合圈上对应的非关键任务持续时间的总和［10］。由闭合圈原理得到目标函数的一组约束条件：

式中，xi、tei分别为闭合圈中关键作业路径上任务i的可压缩时间和平均持续时间；xg、teg分别为闭合圈中非关键作业路径上任务g的可压缩时间和平均持续时间。

为了满足各任务中关键任务的作业工期压缩水平不能超过规定的压缩水平a，工程还应该满足下面的约束条件：

此公式为一个概率型约束条件，按照假定，可将其转化为线性约束条件：

式中，ai为第i闭合圈上作业所有任务的方差和的均方根；λai为a水平下的第i闭合圈上的常数。

综上所述，按照目标函数及约束条件建立工期问题的优化模型为

式中，bi为任务i的工期压缩量的最大值。

3 HPSO优化算法的实现

由于工期问题属于典型的目标优化问题，而PSO算法是求解优化问题较好的一种方法，但标准PSO在求解的过程中容易陷入局部最优，因此，本文采用与遗传算法结合的混合PSO优化算法对其进行优化，避免了在其迭代过程中出现局部最优。

3.1 标准PSO优化算法的数学原理

PSO优化算法的基本思想是通过整个群体中个体之间的信息共享和协作来寻找最优解，而最优解是通过速度和位置的更新实现的［11］。PSO算法需要初始化一群随机粒子，然后通过迭代找到最优解，在每一次迭代中，粒子通过跟踪两个最优值来更新自己，第一个为粒子自己搜索到的最优解 pi，另一个为当前整个种群粒子搜索到的最优解gi［12］。

速度和位置的更新应用如下公式：

其中w为惯性权重；c1、c2分别为粒子跟踪自身和群体历史最优值的权重系数；r1r2为［0，1］区间内均匀分布的随机数；r为进行位置更新时，速度前加的约束因子［13］。

3.2 HPSO算法

为了避免局部最优，文章在标准PSO算法的基础上，借鉴遗传算法中杂交的概念对粒子进行离散点处理［14］。在每次迭代中，根据确定的杂交概率选取指定数量的粒子放入杂交池中，池中的粒子随机进行两两杂交，然后产生和父代（p）同样数目的子代粒子（c），并用子代粒子代替父代粒子［15］，即用杂交后的粒子代替了传统的基本粒子。改进后的子代位置由父代位置进行交叉得到：

其中，p是0～1之间的随机数。

杂交后的子代速度由下式计算：

4 HPSO算法在塔吊分配模型中的应用

4.1 模型的编码

本文将HPSO算法引入塔吊的工期优化问题中，以期快速的获得满意解。假设项目中塔吊作业的网络模型共有n种待吊取物料，则粒子位置向量X={x1,x2,…,xn}，xi为待吊物料i的可压缩作业时间。由于粒子群算法的适应度函数用于衡量粒子个体的优劣，因此将其作为本文网络优化模型的目标函数。对于该优化问题中的约束条件，这里采取惩罚函数的方法处理，即如果个体违反了约束条件将被淘汰［16］。

根据上述编码过程，本文所确立的HPSO算法适应度函数可以用式（1）中的目标函数进行描述，即：

4.2 HPSO算法在塔吊工期优化模型中的实现

1）先将塔吊作业的每个任务进行编码，然后将种群中各粒子的速度和位置随机初始化；

2）初步计算所有粒子的适应度，将当前每个粒子的位置和适应值存储在各自的 pi中，然后将各自 pi中适应最优个体的位置和适应值存储在gi中；

3）按式（6）、（7）更新每个粒子的速度和位置；

4）将每个粒子当前的适应值与其经历过的最好位置相比较，选取较好的作为当前的最好位置；

5）对比当前所有的 pi和gi值，然后更新gi；

6）采用杂交的概念对粒子进行离散点处理，其中子代的位置和速度计算公式如（8）、（9）所示，保持 pi和 gi不变；

7）判断迭代是否满足要求，若是，则停止搜索将结果输出，否则返回3）继续。

提升塔吊利用率的工期优化过程的实现流程如图1所示。

图1 HPSO实现流程图

5 实例分析与评估

为了验证混合粒子群算法在所建立模型应用中的合理性，本文基于Matlab软件环境进行了验证。算法的参数设置如下：种群数为100，学习因子 c1、c2为 2，粒子速度取值范围为［-0.7，0.7］，w取值范围为［0.3，0.9］，杂交概率为0.9。选用某大型项目的QTZ-40塔吊作业问题对算法进行仿真测试，选取任务号1、2、3、4…分别为吊取木材、水泥、模板、钢筋、沙子等物料，由于物料不同，因此压缩工期后造成的塔吊损坏率也不同。实际项目中需要的6种建筑材料由表1中的8种物料构成，将其转化成PERT网络结构如图2所示，其中，每次塔吊作业都处于不满载状态，要求项目在33天（d）内完成。由已知的网络可知共需塔吊吊取8种物料（模拟为8种任务），则根据编码方式可知，粒子的位置向量表示为X={x1,x2,…,x8}，其中各任务与节点的关系见表1。

图2 项目所需的6种材料PERT网络结构图

表1 塔吊吊取8种物料（任务）与节点的对应关系

5.1 实例模型及目标函数

根据工期优化的HPSO算法及项目参数，确定本实例的目标函数如下：

由于粒子群算法就是对适应度函数求最优解，而适应度函数就是目标函数，因此该实例的适应度函数同式（11）。

5.2 结果

经过多次实验，得到的平均最优结果为X={3,0,3,0,0,1,0,3}，塔吊最小损坏率为C=13.5%，因此可得到压缩后的理想工期如表2所示。

由表2可知，在要求的项目工期内，塔吊吊取各物料的作业时间为t={3,0,3,0,0,1,0,3}时，对塔吊的损坏最小。而且由下面图3可以看出，与标准PSO算法相比，HPSO算法应用于缩短塔吊工期问题的求解具有更强的搜索能力，能够有效地避免粒子群陷入早熟收敛，具有运算简单、收敛速度更快、易于实现等优点。

图3 合理分配后的塔吊损坏率进化曲线

6 结语

塔吊的预留量大或调度不合理导致其利用率低是工程施工要解决的重大难题。本文应用PSO算法进行优化处理，并将遗传算法中杂交的概念引入标准PSO算法，避免了在寻优过程中出现局部最优。实例验证表明，在塔吊承重范围内，混合粒子群算法实现了对塔吊作业工期的合理压缩，从而提高了塔吊利用率。另外，将混合粒子群算法用于求解本文模型，不但可以为大型建筑项目中塔吊作业的合理调度提供参考借鉴，而且因其计算效果更佳、收敛速度更快，还可将其引用到同类型的工期优化问题中。