基于粒子群算法的鐵路建設(shè)項(xiàng)目進(jìn)度優(yōu)化研究

杜航李東

（蘭州交通大學(xué)交通運(yùn)輸學(xué)院 甘肅 蘭州 730070）

1 建立模型

每個(gè)項(xiàng)目工序可以用許多方式執(zhí)行，這些方式依賴于使用的技術(shù)、設(shè)備和資源利用的數(shù)量。每個(gè)執(zhí)行選擇與具體的工序工期和成本有關(guān)。在此，首先利用PERT(Program Evaluationand Review Technique)網(wǎng)絡(luò)建立優(yōu)化模型，然后利用粒子群算法解決優(yōu)化問(wèn)題。

1.1 基本假定及規(guī)定

為了簡(jiǎn)化,這里不考慮發(fā)展的資源約束優(yōu)化,假設(shè)在工期優(yōu)化的過(guò)程中動(dòng)態(tài)網(wǎng)絡(luò)關(guān)鍵路徑不會(huì)改變。因此,給定的假設(shè):

（1）"假設(shè)工程造價(jià),C的壓縮；

（2）"關(guān)鍵電路的期限應(yīng)大于等于縮短了時(shí)間限制,需要縮短；

（3）"每次壓縮關(guān)鍵工序、壓縮不能超過(guò)相應(yīng)的路徑的時(shí)差,非關(guān)鍵

（4）"考慮到工序的不確定性,在最后一次的關(guān)鍵路徑的壓縮過(guò)程的時(shí)間不超過(guò)一個(gè)相應(yīng)的所有非加工時(shí)間總時(shí)間路徑、法規(guī)、保證概率,即壓縮a級(jí)。

1.2 確定目標(biāo)函數(shù)

設(shè)某工程項(xiàng)目工序i-j的壓縮時(shí)間為xi-j，其單位時(shí)間直接壓縮費(fèi)用為Ci-j，方差為δi-j，則根據(jù)PERT網(wǎng)絡(luò)壓縮的優(yōu)化目標(biāo)((即使得項(xiàng)目在具體工期內(nèi)用最小成本完成)，目標(biāo)函數(shù)為:

1.3 約束條件

為了確保在工期優(yōu)化的過(guò)程中PERT網(wǎng)絡(luò)的關(guān)鍵路徑?jīng)]有變，這里應(yīng)用閉合圈原理，即從關(guān)鍵路徑上的某個(gè)節(jié)點(diǎn)出發(fā)經(jīng)過(guò)有限關(guān)鍵路徑上的工序和有限非關(guān)鍵路徑上的工序回到該節(jié)點(diǎn)構(gòu)成一個(gè)閉合圈，在閉合圈上所有關(guān)鍵工序的持續(xù)時(shí)間總和應(yīng)大于等于閉合圈上對(duì)應(yīng)非關(guān)鍵工序持續(xù)時(shí)間的總和。

由閉合圈原理得一組目標(biāo)函數(shù)的約束條件

1.4 優(yōu)化模型

綜上所述，PERT網(wǎng)絡(luò)工期——費(fèi)用優(yōu)化線性規(guī)劃模型為:

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

2 粒子群算法描述

粒子群算法，也稱粒子群優(yōu)化算法（Particle Swarm Optimization），縮寫為PSO。PSO模擬鳥(niǎo)群的捕食行為。設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在隨機(jī)搜索食物。在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周圍區(qū)域。這段話的意思是說(shuō)生物群體中信息共享會(huì)產(chǎn)生進(jìn)化優(yōu)勢(shì)，這也正是粒子群優(yōu)化算法的基本思想。

3 算法流程

針對(duì)工期-費(fèi)用優(yōu)化的粒子群算法流程如下：

Step1：設(shè)置問(wèn)題域系統(tǒng)參數(shù)。系統(tǒng)參數(shù)主要有：種群規(guī)模、學(xué)習(xí)因子 C1和 C2、初始迭代次數(shù) iter、最大迭代次數(shù)itermax、最大慣性權(quán)重 wmax、隨機(jī)數(shù) r1和 r2；

Step2：初始化所有粒子。在允許的范圍內(nèi)隨機(jī)設(shè)置粒子的初始位置和速度。隨機(jī)產(chǎn)生粒子i（i=1，2，…，n）的位置向量Xi＝｛x1，x2，…，xn｝和初始化速度向量 Vi＝｛v1，v2，…，vn｝，其中，vi表示工序 i（i=1，2，…，n）進(jìn)一步壓縮變化量；每個(gè)粒子的pbest設(shè)為初始位置，pbest中的最優(yōu)值設(shè)為gbest；

Step3：根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)值，并刷新pbest。根據(jù)式4.5計(jì)算粒子的適應(yīng)值，如果滿足約束并優(yōu)于pbest則pbest被當(dāng)前位置替換，否則pbest保持不變；

Step4：刷新gbest。選擇所有的個(gè)體最優(yōu)解pbest中的最優(yōu)值作為粒子群體當(dāng)前的全局最優(yōu)解gbest;

Step5：刷新粒子的位置和速度。對(duì)每一個(gè)粒子，用公式4.4計(jì)算刷新新速度、用公式4.3刷新粒子位置、用公式4.6刷新慣性權(quán)重；

Step6：刷新迭代次數(shù)。Iter=iter+1

Step7：終止條件判斷。如果滿足終止條件（到達(dá)最大迭代次數(shù)或者找到最優(yōu)值）則終止迭代，gbests所記錄位置即為問(wèn)題的最優(yōu)解。否則，轉(zhuǎn)入step3。

由于實(shí)際的項(xiàng)目進(jìn)度計(jì)劃工期習(xí)慣上的基本單位是天，因此，在step3計(jì)算適應(yīng)值時(shí)，采用四舍五入的辦法，將xi的值取整后計(jì)算。

4 實(shí)例

某工程項(xiàng)目的PERT網(wǎng)絡(luò)計(jì)劃如圖所示，具體參數(shù)的計(jì)算列寫在表1中。要求該項(xiàng)目在33天時(shí)間內(nèi)完成。

PERT網(wǎng)絡(luò)參數(shù)工序 節(jié)點(diǎn) 工期（d） 方差 壓縮范圍 壓縮費(fèi)用/單位時(shí)間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

項(xiàng)目的PERT網(wǎng)絡(luò)共有8個(gè)工序，則粒子位置向量表示為：Xi＝｛x1，x2，…，x8｝，xi表示工序 i的壓縮時(shí)間。 對(duì) PERT 網(wǎng)絡(luò)計(jì)劃圖，其工序與節(jié)點(diǎn)之間的對(duì)應(yīng)關(guān)系以及網(wǎng)絡(luò)參數(shù)如上表。

5 目標(biāo)函數(shù)

6 適應(yīng)度函數(shù)的確定

根據(jù)工期—成本優(yōu)化的數(shù)學(xué)模型以及項(xiàng)目參數(shù)，確定工程項(xiàng)目工期—費(fèi)用優(yōu)化的目標(biāo)函數(shù)為：

根據(jù)上述內(nèi)容，粒子群算法的適應(yīng)度函數(shù)就是工程項(xiàng)目工期—費(fèi)用優(yōu)化的目標(biāo)函數(shù)，即：

f（x）=MinC

7 算法實(shí)現(xiàn)

應(yīng)用PSO算法優(yōu)化該項(xiàng)目。針對(duì)上述算法流程，設(shè)置參數(shù)如下：

種群規(guī)模為50、學(xué)習(xí)因子c1=c2=2、初始迭代次數(shù)iter=1、最大迭代次數(shù)itermax=200、慣性權(quán)重wmax=0.9、隨機(jī)數(shù)r1=r2=0.1。

基于上述方法，在Matlab中開(kāi)發(fā)了PSO工具箱，并使用計(jì)算機(jī)仿真運(yùn)行。

8 結(jié)果

經(jīng)實(shí)驗(yàn)，得到理想最優(yōu)解即壓縮時(shí)間為x=｛3，0，3，0，0，1，0，3｝。 壓 縮 后 的 工 序 時(shí) 間 為 t=｛5，10，7，11，17，15，9，6｝，相應(yīng)的壓縮費(fèi)用為 C=135 元，總工期T=33天。

［1］乞建勛，蘇志雄，王強(qiáng)，張立輝.統(tǒng)籌法的發(fā)展及前沿問(wèn)題[M].科學(xué)出版社，2010，8.

［2］焦永蘭.管理運(yùn)籌學(xué)[M].中國(guó)鐵道出版社，2007.

［3］《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)[M].清華大學(xué)出版社，2005.

［4］孫貴江.高速鐵路（客運(yùn)專線）的施工組織設(shè)計(jì)探討[J].中國(guó)工程咨詢，2004，12.

［5］周昱.淺析客運(yùn)專線施工組織設(shè)計(jì)[J].鐵道工程學(xué)報(bào)，2008，5.

［6］孫連三.新編 Project 2003 項(xiàng)目管理[M].人民郵電出版社，2008，6.

［7］張文杰，林知炎，伍戈.對(duì)工程項(xiàng)目管理組織模式優(yōu)化的探討[D].同濟(jì)大學(xué)管理學(xué)院，2000，8.