在施工項(xiàng)目規(guī)劃問(wèn)題中群智能算法的應(yīng)用研究

李 波，王 妍

(長(zhǎng)春工程學(xué)院計(jì)算機(jī)技術(shù)與工程學(xué)院，吉林 長(zhǎng)春 130012)

0 引言

工程進(jìn)度控制是當(dāng)前工程項(xiàng)目管理中的三大控制(質(zhì)量控制、進(jìn)度控制、成本控制)之一[1].工程項(xiàng)目的工期和成本一直以來(lái)受到項(xiàng)目管理者的重視，其也直接影響到工程的質(zhì)量，項(xiàng)目的工期和成本存在相互制約、相互影響的關(guān)系[2].建設(shè)項(xiàng)目規(guī)劃中最具有挑戰(zhàn)性的任務(wù)之一就是在考慮最優(yōu)資源配置和資源平衡的有關(guān)問(wèn)題的同時(shí)，最大限度地減少項(xiàng)目總成本和項(xiàng)目的總時(shí)間[3].因此，項(xiàng)目規(guī)劃者需要處理復(fù)雜的多變量：時(shí)間、成本、資源，3個(gè)變量及其不確定性的平衡優(yōu)化問(wèn)題就是TCRO問(wèn)題[4].到目前為止，對(duì)工期-成本優(yōu)化問(wèn)題的求解方法有很多，傳統(tǒng)的線性規(guī)劃方法是一種運(yùn)用較為成熟的優(yōu)化方法，具有計(jì)算方法簡(jiǎn)單、求解速度較快的優(yōu)點(diǎn)[5].但是在實(shí)際的應(yīng)用過(guò)程中，存在計(jì)算誤差大、精度較低的缺點(diǎn)，也限制了其在解決實(shí)際問(wèn)題的應(yīng)用.隨著計(jì)算機(jī)技術(shù)以及人工智能技術(shù)的不斷進(jìn)步，人工智能優(yōu)化算法也被廣泛運(yùn)用到項(xiàng)目工期-成本優(yōu)化問(wèn)題上，主要有禁忌搜索法(TS)、模擬退火法(SA)、粒子群算法(PSO)、遺傳算法(GA)等[6-13].這些算法具有較快的求解速度，能夠較為高效地完成最優(yōu)解搜索，在一定程度上較傳統(tǒng)優(yōu)化方法提高了最優(yōu)解的質(zhì)量，但是上述方法均存在計(jì)算時(shí)間過(guò)長(zhǎng)以及容易陷于局部最優(yōu)等問(wèn)題，難以應(yīng)用到實(shí)際問(wèn)題中[14-17].而且由于施工活動(dòng)中諸多不確定因素的存在，使得施工活動(dòng)的持續(xù)時(shí)間具有模糊性[18].因此20世紀(jì)90年代以來(lái)，對(duì)于傳統(tǒng)的網(wǎng)絡(luò)計(jì)劃方法不能解決工程中不確定因素的問(wèn)題，模糊技術(shù)以它特有的優(yōu)勢(shì)被考慮應(yīng)用到網(wǎng)絡(luò)計(jì)劃技術(shù)當(dāng)中[19].將模糊技術(shù)引入網(wǎng)絡(luò)，使原不確定信息有了更好地表達(dá)方式，能更好地處理由于環(huán)境、風(fēng)險(xiǎn)等影響下的其他不確定的信息[20].本文嘗試將遺傳算法與粒子群算法相混合，并使用模糊集來(lái)表征該混合方法中輸入數(shù)據(jù)的不確定性，即模糊啟用混合遺傳粒子群算法(HGAPSO算法)來(lái)計(jì)算TCRO問(wèn)題.將HGAPSO算法應(yīng)用在工程實(shí)踐的實(shí)際案例中，并與其他算法運(yùn)算結(jié)果進(jìn)行了對(duì)比.

定義1 考慮一個(gè)典型的由N個(gè)相關(guān)活動(dòng)A組成的項(xiàng)目計(jì)劃問(wèn)題：A1，A2，…，AN，由幾種選擇來(lái)分配S類型的項(xiàng)目資源R1，R2，…，RS來(lái)執(zhí)行活動(dòng)，每個(gè)項(xiàng)目進(jìn)度用項(xiàng)目資源組合執(zhí)行活動(dòng)的時(shí)間和成本表示.每個(gè)活動(dòng)的時(shí)間、直接成本的值和范圍都是基于時(shí)間-成本函數(shù)的依賴變量，由項(xiàng)目規(guī)劃人員定義.假設(shè)項(xiàng)目計(jì)劃人員可以選擇活動(dòng)的整個(gè)可行時(shí)間表的選項(xiàng)集合定義為

Oi(j)=(Ti，Ci(R1，R2，…，RS)i)(j)，i=1，2，…，N.

(1)

式中j=1/4 ，1，2，…，Mi，其中Mi是執(zhí)行活動(dòng)i的可行配置的總數(shù).

執(zhí)行這種可行的時(shí)間選項(xiàng)和直接成本既可以是離散的也可以是連續(xù)的，取決可用于執(zhí)行活動(dòng)的替代方案的數(shù)量.此外，直接成本取決于每個(gè)可行的時(shí)間表選項(xiàng)(Oi)中的資源分配，并且基于多個(gè)資源的資源數(shù)量和固定(在沒(méi)有計(jì)算任何利息或通貨膨脹下)單位價(jià)格的乘積來(lái)計(jì)算.TCRO問(wèn)題只能夠考慮有限資源的模式，只有在有限的資源條件得到滿足時(shí)，才會(huì)接受每種活動(dòng)的時(shí)間和成本選擇.TCRO模型的流程見圖1.

圖1 TCRO模型的流程

項(xiàng)目規(guī)劃人員面對(duì)的問(wèn)題是如何分配項(xiàng)目資源和安排活動(dòng)，以盡量減少項(xiàng)目總成本和項(xiàng)目總時(shí)間，同時(shí)保持每日資源限制.因此，項(xiàng)目規(guī)劃者在這個(gè)優(yōu)化問(wèn)題中的決策變量是項(xiàng)目活動(dòng)的開始日期SD1，SD2，…，SDN和執(zhí)行項(xiàng)目活動(dòng)的資源分配選項(xiàng)O1，j1，O2，j2，…，ON，jN.假設(shè)任何一個(gè)活動(dòng)都不能分裂并且在進(jìn)行中活動(dòng)的資源分配保持不變情況下，項(xiàng)目規(guī)劃者在TCRO問(wèn)題中的目標(biāo)函數(shù)可以表述為最小化總項(xiàng)目成本、最大限度減少總項(xiàng)目持續(xù)時(shí)間和資源分配總變化3個(gè)目標(biāo).

定義2Z1為最小化總項(xiàng)目成本.總項(xiàng)目成本包括執(zhí)行項(xiàng)目活動(dòng)的總直接成本和完成項(xiàng)目的間接成本.項(xiàng)目的總直接成本與活動(dòng)持續(xù)時(shí)間成正比，間接成本通常被認(rèn)為等于項(xiàng)目執(zhí)行總時(shí)間中項(xiàng)目的每日固定成本總和，公式為

Z1=min(TC).

(2)

定義3Z2為最大限度減少項(xiàng)目總時(shí)間(TD).項(xiàng)目總時(shí)間是完成項(xiàng)目活動(dòng)網(wǎng)絡(luò)關(guān)鍵路徑上的關(guān)鍵活動(dòng)所需的時(shí)間，公式為

Z2=min (TD).

(3)

定義4Z3為最大限度地減少資源分配的總體變化.衡量資源分配變化最常用的指標(biāo)之一是在整個(gè)項(xiàng)目期間使用的資源平方和(SSR).項(xiàng)目規(guī)劃人員應(yīng)該盡量減少這一資源，以實(shí)現(xiàn)更好的資源調(diào)配，公式為

(4)

式中Resourcen，k是在n個(gè)活動(dòng)項(xiàng)目持續(xù)時(shí)間的第k天計(jì)劃使用的資源的數(shù)量，其中n=1，2，…，s，k=1，2，…，TD.

建筑項(xiàng)目規(guī)劃中的TCRO問(wèn)題受到以下幾個(gè)限制：

(1) 項(xiàng)目活動(dòng)網(wǎng)絡(luò)圖中所示的項(xiàng)目活動(dòng)之間的邏輯依賴關(guān)系.項(xiàng)目活動(dòng)之間的開始-開始，開始-結(jié)束，結(jié)束-開始以及結(jié)束-結(jié)束關(guān)系必須在活動(dòng)開始日期SD1，SD2，…，SDN和相應(yīng)的持續(xù)時(shí)間T1，T2，…，TN中.

(2) 每日資源總量限制.整個(gè)項(xiàng)目活動(dòng)中特定資源的總消耗量不得超過(guò)項(xiàng)目期間任何時(shí)間點(diǎn)該資源的能力.

1 問(wèn)題建模

在PSO的精英集中，增強(qiáng)的精英是新一代人口的一半，而另一半則是通過(guò)對(duì)這些增強(qiáng)型的精英進(jìn)行交叉和變異操作而產(chǎn)生的.HGAPSO作為一種演化學(xué)習(xí)算法，在可行解空間內(nèi)生成解，并通過(guò)GA的交叉和變異操作，搜索和改進(jìn)當(dāng)前解，模糊邏輯已被廣泛應(yīng)用于作為表征建設(shè)項(xiàng)目規(guī)劃中不確定變量的一種方法，通過(guò)使用模糊輸入數(shù)據(jù)使算法適用于建筑工程規(guī)劃的特定環(huán)境.本文中使用標(biāo)準(zhǔn)的三角模糊隸屬函數(shù)來(lái)描述完成其中某一項(xiàng)活動(dòng)的成本和時(shí)間的不確定性.

定義5 分配選項(xiàng)集中的成本及時(shí)間的最小值、平均值和最大值分別設(shè)為Cmin，CavgCmax以及Tmin，Tavg和Tmax.構(gòu)造三角成本時(shí)間隸屬函數(shù)見圖2.

設(shè)計(jì)用于解決TCRO問(wèn)題的HGAPSO算法包括以下步驟：

(1) 首先，設(shè)置k=1，初始化一組可行的項(xiàng)目進(jìn)度解決方案為

是整個(gè)可行的日期和時(shí)間-成本-資源分配活動(dòng)的隨機(jī)選擇，其中i=1，2，…，N.

該初始人口集由N個(gè)項(xiàng)目進(jìn)度表的解決方案組成，這些方案從項(xiàng)目活動(dòng)的可行開始日期和時(shí)間、成本、資源分配中隨機(jī)抽取，并且考慮了項(xiàng)目活動(dòng)之間的邏輯和時(shí)間關(guān)系.

(2) 計(jì)算P(K)中每個(gè)可行項(xiàng)目進(jìn)度計(jì)劃選項(xiàng)的優(yōu)化目標(biāo)函數(shù)值為總項(xiàng)目成本(Z1)、總項(xiàng)目持續(xù)時(shí)間(Z2)和資源分配總變化量(Z3).

(3) 從可行集合P(K)中消除主導(dǎo)解決方案.主導(dǎo)解決方案是一種花費(fèi)成本、持續(xù)時(shí)間和資源變化都大于或等于另一種解決方案.從最初P(K)中刪除主導(dǎo)的項(xiàng)目進(jìn)度表選項(xiàng)并更新.

(5) 對(duì)于P(K)中的每個(gè)項(xiàng)目時(shí)間表選項(xiàng)，計(jì)算三維客觀空間中距離原點(diǎn)的歸一化距離，公式為

(4)

(6) 從P(K)的最大距離到最小距離制定項(xiàng)目進(jìn)度表，將排序的總體集合拆分為兩個(gè)解集子集：下半部分和上半部分(如果P(K)的大小是偶數(shù)，則上半部分子集包括中點(diǎn)).

(7) 應(yīng)用GA的組合交叉和變異算子詳細(xì)描述當(dāng)前的下半部分子集，以生成新的、可行的項(xiàng)目進(jìn)度表解決方案.這些新的解決方案屬于由P(K+1)表示的下一代人口集合的項(xiàng)目進(jìn)度選項(xiàng).

(8) 對(duì)PSO詳細(xì)描述當(dāng)前的上半部分子集，以生成新的、可行的項(xiàng)目進(jìn)度表解決方案.這些新的解決方案也屬于由P(K+1)表示的下一代人口集的項(xiàng)目進(jìn)度計(jì)劃選項(xiàng).

(9) 重復(fù)步驟(2)到步驟(8)，直到執(zhí)行步驟(7)和步驟(8)不能找到新的項(xiàng)目進(jìn)度表解決方案，即當(dāng)下一代人口組的項(xiàng)目進(jìn)度計(jì)劃選項(xiàng)等于當(dāng)前的一組項(xiàng)目進(jìn)度計(jì)劃選項(xiàng)時(shí)，并且最終的人口集表示TCRO問(wèn)題的Pareto最優(yōu)項(xiàng)目進(jìn)度計(jì)劃解決方案.

圖3總結(jié)了上述步驟，從初始人口到精英人口再到新人口迭代的全部過(guò)程.

將使用HGAPSO算法來(lái)解決建設(shè)項(xiàng)目規(guī)劃中的實(shí)際TCRO問(wèn)題的案例，從研究方法中找到的最優(yōu)項(xiàng)目解決方案并與現(xiàn)有優(yōu)化算法的結(jié)果進(jìn)行比較.

圖3 HGAPSO算法的框圖

2 案例分析

案例分析1 第1個(gè)例子由7個(gè)相互關(guān)聯(lián)的活動(dòng)組成的項(xiàng)目，活動(dòng)節(jié)點(diǎn)圖(AON圖)如圖4所示.本項(xiàng)目使用R1，R2，…，R77種資源類型，每個(gè)活動(dòng)有若干個(gè)選項(xiàng)可以使用這些資源的不同配置.表1顯示了活動(dòng)(1)的11個(gè)執(zhí)行活動(dòng)的時(shí)間、資源和成本配比.此外，假定該項(xiàng)目的間接成本為每天1 500美元.

文獻(xiàn)[2]使用模糊GA算法來(lái)解決這個(gè)項(xiàng)目規(guī)劃問(wèn)題，并找到最優(yōu)的項(xiàng)目進(jìn)度解決方案，并且在2009年應(yīng)用NSGA-Ⅱ演化算法找到項(xiàng)目進(jìn)度解決方案的Pareto最優(yōu)前沿.圖4展示了該項(xiàng)目第一項(xiàng)活動(dòng)的時(shí)間和成本函數(shù).

表1 例1中活動(dòng)(1)的可行項(xiàng)目進(jìn)度表選項(xiàng)

圖4 例1中項(xiàng)目活動(dòng)的AON圖

本文也在同一問(wèn)題中用HGAPSO算法解決這個(gè)項(xiàng)目規(guī)劃問(wèn)題，以找到項(xiàng)目進(jìn)度解決方案的Pareto最優(yōu)解，然后將本文的解決方案與前兩種算法的結(jié)果進(jìn)行比較.

活動(dòng)的持續(xù)時(shí)間和直接成本的離散化隸屬函數(shù)見圖5.將HGAPSO算法與HGA和NSGA-Ⅱ算法進(jìn)行比較(見圖6)，考慮同時(shí)最小化總項(xiàng)目成本、總項(xiàng)目持續(xù)時(shí)間和資源分配的總變化.可以看出HGAPSO算法比HGA算法得出更多的最優(yōu)解，比NSGA-Ⅱ算法最優(yōu)解的總項(xiàng)目花費(fèi)更低.

圖5 活動(dòng)的持續(xù)時(shí)間和直接成本的離散化隸屬函數(shù)

圖6 項(xiàng)目總成本和項(xiàng)目工期的2D空間中的最優(yōu)項(xiàng)目進(jìn)度解

項(xiàng)目目標(biāo)三維空間中Pareto最優(yōu)前沿的項(xiàng)目進(jìn)度解決方案中項(xiàng)目總成本、總項(xiàng)目持續(xù)時(shí)間和資源分配總變化見圖7，這些Pareto最優(yōu)點(diǎn)顯示了總項(xiàng)目成本，總項(xiàng)目持續(xù)時(shí)間和非主導(dǎo)項(xiàng)目進(jìn)度解決方案的資源分配總變化，可以看出在3個(gè)目標(biāo)前提下，在三維圖中能夠找到本案例的最優(yōu)解(圖7兩圖資源配比不同).

a：資源配比1；b：資源配比2

為了更好地比較這兩種算法在項(xiàng)目規(guī)劃的目標(biāo)二維解空間中得出的最優(yōu)項(xiàng)目進(jìn)度計(jì)劃解決方案，在解空間中兩兩目標(biāo)進(jìn)行比較：總項(xiàng)目成本和總項(xiàng)目持續(xù)時(shí)間之間(及C與T之間)，總項(xiàng)目成本和總資源分配變化之間(C與R之間)，項(xiàng)目總時(shí)間和資源分配總變化之間(T與R之間)(見圖8).

從圖8可以看出，對(duì)于總項(xiàng)目成本和總項(xiàng)目持續(xù)時(shí)間這兩個(gè)目標(biāo)而言，相對(duì)于NSGA-Ⅱ算法、HGAPSO算法在相同時(shí)間條件下，找到的解總項(xiàng)目花費(fèi)更低；對(duì)于同樣的總項(xiàng)目花費(fèi)而言，HGAPSO算法消耗的總資源最少；對(duì)于同樣的總持續(xù)時(shí)間而言，HGAPSO算法找到更多最優(yōu)解，并且消耗資源較少.尤其在圖8a中可以找到64 d的最優(yōu)解，在NSGA-Ⅱ中沒(méi)有找到；HGAPSO算法發(fā)現(xiàn)的最低項(xiàng)目總成本(227 250美元)低于NSGA-Ⅱ算法(228 750美元).在圖8b中HGAPSO算法發(fā)現(xiàn)的資源分配總量變化最小.

圖8 二維解空間兩種算法的對(duì)比

案例分析2 第2個(gè)例子是一個(gè)快餐店項(xiàng)目，由14個(gè)相互關(guān)聯(lián)的活動(dòng)組成.該項(xiàng)目還使用了10種不同的資源類型：R1，R2，…，R10，考慮可行資源、時(shí)間和成本的各種組合，有幾個(gè)項(xiàng)目進(jìn)度計(jì)劃選項(xiàng)可以執(zhí)行每項(xiàng)活動(dòng).表2中的幾個(gè)不同的連續(xù)和離散的時(shí)間-成本函數(shù)描述了項(xiàng)目進(jìn)度選項(xiàng)，每個(gè)活動(dòng)都可以使用不同的資源集合進(jìn)行.表3總結(jié)了執(zhí)行活動(dòng)(1)的資源配置的幾個(gè)示例，每個(gè)資源配置對(duì)應(yīng)確定的特定時(shí)間-成本配置.該項(xiàng)目的間接費(fèi)用設(shè)定為600美元/d.

表2 案例2中執(zhí)行項(xiàng)目活動(dòng)的成本-時(shí)間函數(shù)

表3 案例2中執(zhí)行活動(dòng)(1)的可行項(xiàng)目時(shí)間表選項(xiàng)示例

有學(xué)者使用PSO算法來(lái)解決過(guò)這個(gè)項(xiàng)目調(diào)度問(wèn)題，并找到了最優(yōu)的項(xiàng)目進(jìn)度解決方案.此外，在2009年也將NSGA-Ⅱ算法應(yīng)用于此問(wèn)題中尋找最佳項(xiàng)目進(jìn)度表選項(xiàng)，相比較用HGAPSO算法來(lái)解決這個(gè)優(yōu)化問(wèn)題，能找到更多項(xiàng)目進(jìn)度解決方案及Pareto最優(yōu)解.在項(xiàng)目總成本和總項(xiàng)目時(shí)間的二維空間中針對(duì)該問(wèn)題的Pareto最優(yōu)項(xiàng)目進(jìn)度解決方案見圖9.圖9顯示了HGAPSO、PSO以及NSGA-Ⅱ算法找到的解決方案的總項(xiàng)目成本和總項(xiàng)目持續(xù)時(shí)間對(duì)比.可以看出，HGAPSO算法能夠找到更多解決方案，其總項(xiàng)目成本和總項(xiàng)目持續(xù)時(shí)間較低.尤其是HGAPSO算法所找到的最優(yōu)解(21 d)的最短總項(xiàng)目持續(xù)時(shí)間少于PSO算法(27 d)和NSGA-Ⅱ算法(36 d).HGAPSO算法發(fā)現(xiàn)的最低項(xiàng)目總成本(81 265美元)低于PSO算法(93 156美元)和NSGA-Ⅱ算法(96 708美元).在本案例中HGAPSO算法以較低的項(xiàng)目總成本和較短的總項(xiàng)目時(shí)間尋找額外的最優(yōu)項(xiàng)目進(jìn)度解決方案.

圖9 項(xiàng)目總成本和項(xiàng)目工期的2D空間中最優(yōu)項(xiàng)目進(jìn)度解

3 結(jié)論

綜上所述，在兩個(gè)案例中得出以下結(jié)論：

(1) 相比于NSGA-Ⅱ算法和PSO算法，HGAPSO算法能找到更多最優(yōu)解；

(2) 在總持續(xù)時(shí)間相同的前提下，HGAPSO算法總項(xiàng)目花費(fèi)時(shí)間更低；

(3) 在總花費(fèi)相同的前提下，HGAPSO算法總資源數(shù)量更??；

(4) 在總持續(xù)時(shí)間相同前提下，HGAPSO算法需要總資源數(shù)量更少.

因此，本文在建設(shè)項(xiàng)目TCRO問(wèn)題求解中，HGAPSO算法比NSGA-Ⅱ算法和PSO算法有明顯優(yōu)勢(shì).