基于粒子群算法的铁路建设项目进度优化研究

杜航李东

（兰州交通大学交通运输学院 甘肃 兰州 730070）

1 建立模型

每个项目工序可以用许多方式执行，这些方式依赖于使用的技术、设备和资源利用的数量。每个执行选择与具体的工序工期和成本有关。在此，首先利用PERT(Program Evaluationand Review Technique)网络建立优化模型，然后利用粒子群算法解决优化问题。

1.1 基本假定及规定

为了简化,这里不考虑发展的资源约束优化,假设在工期优化的过程中动态网络关键路径不会改变。因此,给定的假设:

（1）"假设工程造价,C的压缩；

（2）"关键电路的期限应大于等于缩短了时间限制,需要缩短；

（3）"每次压缩关键工序、压缩不能超过相应的路径的时差,非关键

（4）"考虑到工序的不确定性,在最后一次的关键路径的压缩过程的时间不超过一个相应的所有非加工时间总时间路径、法规、保证概率,即压缩a级。

1.2 确定目标函数

设某工程项目工序i-j的压缩时间为xi-j，其单位时间直接压缩费用为Ci-j，方差为δi-j，则根据PERT网络压缩的优化目标((即使得项目在具体工期内用最小成本完成)，目标函数为:

1.3 约束条件

为了确保在工期优化的过程中PERT网络的关键路径没有变，这里应用闭合圈原理，即从关键路径上的某个节点出发经过有限关键路径上的工序和有限非关键路径上的工序回到该节点构成一个闭合圈，在闭合圈上所有关键工序的持续时间总和应大于等于闭合圈上对应非关键工序持续时间的总和。

由闭合圈原理得一组目标函数的约束条件

1.4 优化模型

综上所述，PERT网络工期——费用优化线性规划模型为:

其中的bi-j，表示工序i-j的工期压缩量的最大值。

2 粒子群算法描述

粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为PSO。PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。这段话的意思是说生物群体中信息共享会产生进化优势，这也正是粒子群优化算法的基本思想。

3 算法流程

针对工期-费用优化的粒子群算法流程如下：

Step1：设置问题域系统参数。系统参数主要有：种群规模、学习因子 C1和 C2、初始迭代次数 iter、最大迭代次数itermax、最大惯性权重 wmax、随机数 r1和 r2；

Step2：初始化所有粒子。在允许的范围内随机设置粒子的初始位置和速度。随机产生粒子i（i=1，2，…，n）的位置向量Xi＝｛x1，x2，…，xn｝和初始化速度向量 Vi＝｛v1，v2，…，vn｝，其中，vi表示工序 i（i=1，2，…，n）进一步压缩变化量；每个粒子的pbest设为初始位置，pbest中的最优值设为gbest；

Step3：根据适应度函数计算每个粒子的适应值，并刷新pbest。根据式4.5计算粒子的适应值，如果满足约束并优于pbest则pbest被当前位置替换，否则pbest保持不变；

Step4：刷新gbest。选择所有的个体最优解pbest中的最优值作为粒子群体当前的全局最优解gbest;

Step5：刷新粒子的位置和速度。对每一个粒子，用公式4.4计算刷新新速度、用公式4.3刷新粒子位置、用公式4.6刷新惯性权重；

Step6：刷新迭代次数。Iter=iter+1

Step7：终止条件判断。如果满足终止条件（到达最大迭代次数或者找到最优值）则终止迭代，gbests所记录位置即为问题的最优解。否则，转入step3。

由于实际的项目进度计划工期习惯上的基本单位是天，因此，在step3计算适应值时，采用四舍五入的办法，将xi的值取整后计算。

4 实例

某工程项目的PERT网络计划如图所示，具体参数的计算列写在表1中。要求该项目在33天时间内完成。

PERT网络参数工序 节点 工期（d） 方差 压缩范围 压缩费用/单位时间1 1-2 8 0.6 6 7 3 2 0 2 1-3 1 0 1.1 6 7 2 1 0 3 2-3 1 0 1.0 0 0 3 7 4 2-4 1 1 0.6 6 7 4 5 5 2-5 1 7 0.6 6 7 7 2 5 6 3-5 1 6 0.6 6 7 6 3 0 7 4-6 9 0.8 3 3 2 4 8 5-6 9 1.0 0 0 3 8

项目的PERT网络共有8个工序，则粒子位置向量表示为：Xi＝｛x1，x2，…，x8｝，xi表示工序 i的压缩时间。 对 PERT 网络计划图，其工序与节点之间的对应关系以及网络参数如上表。

5 目标函数

6 适应度函数的确定

根据工期—成本优化的数学模型以及项目参数，确定工程项目工期—费用优化的目标函数为：

根据上述内容，粒子群算法的适应度函数就是工程项目工期—费用优化的目标函数，即：

f（x）=MinC

7 算法实现

应用PSO算法优化该项目。针对上述算法流程，设置参数如下：

种群规模为50、学习因子c1=c2=2、初始迭代次数iter=1、最大迭代次数itermax=200、惯性权重wmax=0.9、随机数r1=r2=0.1。

基于上述方法，在Matlab中开发了PSO工具箱，并使用计算机仿真运行。

8 结果

经实验，得到理想最优解即压缩时间为x=｛3，0，3，0，0，1，0，3｝。 压 缩 后 的 工 序 时 间 为 t=｛5，10，7，11，17，15，9，6｝，相应的压缩费用为 C=135 元，总工期T=33天。

［1］乞建勋，苏志雄，王强，张立辉.统筹法的发展及前沿问题[M].科学出版社，2010，8.

［2］焦永兰.管理运筹学[M].中国铁道出版社，2007.

［3］《运筹学》教材编写组.运筹学[M].清华大学出版社，2005.

［4］孙贵江.高速铁路（客运专线）的施工组织设计探讨[J].中国工程咨询，2004，12.

［5］周昱.浅析客运专线施工组织设计[J].铁道工程学报，2008，5.

［6］孙连三.新编 Project 2003 项目管理[M].人民邮电出版社，2008，6.

［7］张文杰，林知炎，伍戈.对工程项目管理组织模式优化的探讨[D].同济大学管理学院，2000，8.