在施工項目規劃問題中群智能算法的應用研究

李 波，王 妍

(長春工程學院計算機技術與工程學院，吉林 長春 130012)

0 引言

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

定義1 考慮一個典型的由N個相關活動A組成的項目計劃問題：A1，A2，…，AN，由幾種選擇來分配S類型的項目資源R1，R2，…，RS來執行活動，每個項目進度用項目資源組合執行活動的時間和成本表示.每個活動的時間、直接成本的值和范圍都是基于時間-成本函數的依賴變量，由項目規劃人員定義.假設項目計劃人員可以選擇活動的整個可行時間表的選項集合定義為

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

(1)

式中j=1/4 ，1，2，…，Mi，其中Mi是執行活動i的可行配置的總數.

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

圖1 TCRO模型的流程

項目規劃人員面對的問題是如何分配項目資源和安排活動，以盡量減少項目總成本和項目總時間，同時保持每日資源限制.因此，項目規劃者在這個優化問題中的決策變量是項目活動的開始日期SD1，SD2，…，SDN和執行項目活動的資源分配選項O1，j1，O2，j2，…，ON，jN.假設任何一個活動都不能分裂并且在進行中活動的資源分配保持不變情況下，項目規劃者在TCRO問題中的目標函數可以表述為最小化總項目成本、最大限度減少總項目持續時間和資源分配總變化3個目標.

定義2Z1為最小化總項目成本.總項目成本包括執行項目活動的總直接成本和完成項目的間接成本.項目的總直接成本與活動持續時間成正比，間接成本通常被認為等于項目執行總時間中項目的每日固定成本總和，公式為

Z1=min(TC).

(2)

定義3Z2為最大限度減少項目總時間(TD).項目總時間是完成項目活動網絡關鍵路徑上的關鍵活動所需的時間，公式為

Z2=min (TD).

(3)

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

(4)

式中Resourcen，k是在n個活動項目持續時間的第k天計劃使用的資源的數量，其中n=1，2，…，s，k=1，2，…，TD.

建筑項目規劃中的TCRO問題受到以下幾個限制：

(1) 項目活動網絡圖中所示的項目活動之間的邏輯依賴關系.項目活動之間的開始-開始，開始-結束，結束-開始以及結束-結束關系必須在活動開始日期SD1，SD2，…，SDN和相應的持續時間T1，T2，…，TN中.

(2) 每日資源總量限制.整個項目活動中特定資源的總消耗量不得超過項目期間任何時間點該資源的能力.

1 問題建模

在PSO的精英集中，增強的精英是新一代人口的一半，而另一半則是通過對這些增強型的精英進行交叉和變異操作而產生的.HGAPSO作為一種演化學習算法，在可行解空間內生成解，并通過GA的交叉和變異操作，搜索和改進當前解，模糊邏輯已被廣泛應用于作為表征建設項目規劃中不確定變量的一種方法，通過使用模糊輸入數據使算法適用于建筑工程規劃的特定環境.本文中使用標準的三角模糊隸屬函數來描述完成其中某一項活動的成本和時間的不確定性.

定義5 分配選項集中的成本及時間的最小值、平均值和最大值分別設為Cmin，CavgCmax以及Tmin，Tavg和Tmax.構造三角成本時間隸屬函數見圖2.

設計用于解決TCRO問題的HGAPSO算法包括以下步驟：

(1) 首先，設置k=1，初始化一組可行的項目進度解決方案為

是整個可行的日期和時間-成本-資源分配活動的隨機選擇，其中i=1，2，…，N.

該初始人口集由N個項目進度表的解決方案組成，這些方案從項目活動的可行開始日期和時間、成本、資源分配中隨機抽取，并且考慮了項目活動之間的邏輯和時間關系.

(2) 計算P(K)中每個可行項目進度計劃選項的優化目標函數值為總項目成本(Z1)、總項目持續時間(Z2)和資源分配總變化量(Z3).

(3) 從可行集合P(K)中消除主導解決方案.主導解決方案是一種花費成本、持續時間和資源變化都大于或等于另一種解決方案.從最初P(K)中刪除主導的項目進度表選項并更新.

(5) 對于P(K)中的每個項目時間表選項，計算三維客觀空間中距離原點的歸一化距離，公式為

(4)

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

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

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

(9) 重復步驟(2)到步驟(8)，直到執行步驟(7)和步驟(8)不能找到新的項目進度表解決方案，即當下一代人口組的項目進度計劃選項等于當前的一組項目進度計劃選項時，并且最終的人口集表示TCRO問題的Pareto最優項目進度計劃解決方案.

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

將使用HGAPSO算法來解決建設項目規劃中的實際TCRO問題的案例，從研究方法中找到的最優項目解決方案并與現有優化算法的結果進行比較.

圖3 HGAPSO算法的框圖

2 案例分析

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

文獻[2]使用模糊GA算法來解決這個項目規劃問題，并找到最優的項目進度解決方案，并且在2009年應用NSGA-Ⅱ演化算法找到項目進度解決方案的Pareto最優前沿.圖4展示了該項目第一項活動的時間和成本函數.

表1 例1中活動(1)的可行項目進度表選項

圖4 例1中項目活動的AON圖

本文也在同一問題中用HGAPSO算法解決這個項目規劃問題，以找到項目進度解決方案的Pareto最優解，然后將本文的解決方案與前兩種算法的結果進行比較.

活動的持續時間和直接成本的離散化隸屬函數見圖5.將HGAPSO算法與HGA和NSGA-Ⅱ算法進行比較(見圖6)，考慮同時最小化總項目成本、總項目持續時間和資源分配的總變化.可以看出HGAPSO算法比HGA算法得出更多的最優解，比NSGA-Ⅱ算法最優解的總項目花費更低.

圖5 活動的持續時間和直接成本的離散化隸屬函數

圖6 項目總成本和項目工期的2D空間中的最優項目進度解

項目目標三維空間中Pareto最優前沿的項目進度解決方案中項目總成本、總項目持續時間和資源分配總變化見圖7，這些Pareto最優點顯示了總項目成本，總項目持續時間和非主導項目進度解決方案的資源分配總變化，可以看出在3個目標前提下，在三維圖中能夠找到本案例的最優解(圖7兩圖資源配比不同).

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

為了更好地比較這兩種算法在項目規劃的目標二維解空間中得出的最優項目進度計劃解決方案，在解空間中兩兩目標進行比較：總項目成本和總項目持續時間之間(及C與T之間)，總項目成本和總資源分配變化之間(C與R之間)，項目總時間和資源分配總變化之間(T與R之間)(見圖8).

從圖8可以看出，對于總項目成本和總項目持續時間這兩個目標而言，相對于NSGA-Ⅱ算法、HGAPSO算法在相同時間條件下，找到的解總項目花費更低；對于同樣的總項目花費而言，HGAPSO算法消耗的總資源最少；對于同樣的總持續時間而言，HGAPSO算法找到更多最優解，并且消耗資源較少.尤其在圖8a中可以找到64 d的最優解，在NSGA-Ⅱ中沒有找到；HGAPSO算法發現的最低項目總成本(227 250美元)低于NSGA-Ⅱ算法(228 750美元).在圖8b中HGAPSO算法發現的資源分配總量變化最小.

圖8 二維解空間兩種算法的對比

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

表2 案例2中執行項目活動的成本-時間函數

表3 案例2中執行活動(1)的可行項目時間表選項示例

有學者使用PSO算法來解決過這個項目調度問題，并找到了最優的項目進度解決方案.此外，在2009年也將NSGA-Ⅱ算法應用于此問題中尋找最佳項目進度表選項，相比較用HGAPSO算法來解決這個優化問題，能找到更多項目進度解決方案及Pareto最優解.在項目總成本和總項目時間的二維空間中針對該問題的Pareto最優項目進度解決方案見圖9.圖9顯示了HGAPSO、PSO以及NSGA-Ⅱ算法找到的解決方案的總項目成本和總項目持續時間對比.可以看出，HGAPSO算法能夠找到更多解決方案，其總項目成本和總項目持續時間較低.尤其是HGAPSO算法所找到的最優解(21 d)的最短總項目持續時間少于PSO算法(27 d)和NSGA-Ⅱ算法(36 d).HGAPSO算法發現的最低項目總成本(81 265美元)低于PSO算法(93 156美元)和NSGA-Ⅱ算法(96 708美元).在本案例中HGAPSO算法以較低的項目總成本和較短的總項目時間尋找額外的最優項目進度解決方案.

圖9 項目總成本和項目工期的2D空間中最優項目進度解

3 結論

綜上所述，在兩個案例中得出以下結論：

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

(2) 在總持續時間相同的前提下，HGAPSO算法總項目花費時間更低；

(3) 在總花費相同的前提下，HGAPSO算法總資源數量更小；

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

因此，本文在建設項目TCRO問題求解中，HGAPSO算法比NSGA-Ⅱ算法和PSO算法有明顯優勢.