考慮作業空間干涉的工程項目時間-成本均衡優化研究

李 遷, 陶 莎, 周曉園，盛昭瀚

(南京大學工程管理學院，江蘇 南京 210093)

1 引言

工程施工進度計劃以及資源的有效配置是施工項目管理的重要科學問題[1-2]。除了人力、設備等資源，施工現場的空間也是重要資源之一。實踐表明，施工活動安排不合理引起的活動作業空間不足、作業空間相互占用易造成作業效率低下、返工、安全隱患等不良后果，大大阻礙了工程目標的實現[3-5]。因此，在優化施工調度方案時充分考慮施工活動的空間需求以及空間約束條件對工程管理實踐具有一定的現實意義。

目前大多學者借助可視化仿真技術對施工中的空間干涉問題開展研究[6-8]。這類研究通常基于已知的調度方案，借助數字化技術識別空間干涉，并通過制定規則來局部地調整計劃方案，以消除或解決空間干涉問題。Moon[6]等人提出一種序列檢查算法來避免并行活動之間發生空間干涉。Choi[7]等人設計了一種作業空間規劃的流程框架，包含識別4D BIM、識別作業空間、表征空間占用、識別空間干涉、解決空間干涉五個階段。Zhang[8]等人利用GPS定位系統和BIM實時地判斷人員的作業空間，進而識別潛在的空間干涉并及時采取防范措施。然而，這類方法缺乏對調度計劃進行預先的整體性優化設計。此外，少部分學者對具體資源(如人、機械設備)的運行方位和動作軌跡等細節上進行建模，避免其作業過程中發生沖突[3,9]。例如，Isaac[9]等人采用時間-空間圖描述員工的動態運動過程，將員工作業路徑表示為粒度函數，對并行活動進行時間和空間的分配。該類研究從資源運動的微觀視角，而非從整體工程項目的宏觀視角根據活動的空間需求信息優化工程調度方案。

資源受限的項目調度問題(RCPSP)是運籌學和運作管理領域的重要研究方向，旨在研究考慮資源供給限制的項目調度優化問題，其應用領域涉及建設工程、工業生產、物流交通等[10]。RCPSP將資源類型大致分為可再生資源(如人力資源)和非再生資源(如原料)，空間資源屬于一類有限的可再生資源[11]。一些學者結合RCPSP與有限工程空間資源開展研究。Frene[12]等人設計空間資源的請求活動(Call activity)、中間活動(Interval activity)、釋放活動(Release activity)三類活動，基于RCPSP并提出采用串行方案生成機制的啟發式算法解決問題。Semenov[13]等人在RCPSP中考慮空間擁堵和作業流擾動約束，建立以工程工期最短為目標的優化模型。Tao[14]等人將空間擁堵作為優化目標之一，建立時間-成本-擁擠度多目標工程調度優化模型。

本文創新性地從空間干涉降低施工作業效率的現實出發，以工期和成本為目標，基于RCPSP相關理論，建立考慮空間干涉的工程調度時間-成本雙目標優化模型。與以往研究假設工期已知不同，該模型定義了活動的作業效率曲線和實際工期變量。此外，不同于傳統求解RCPSP算法的序列或權重編碼方式，本文針對性地設計了相對延遲編碼方式和相應解碼機制，采用NSGA-II算法有效求解問題。

2 問題定義與數學模型

采用AON(Activity-On-Node)網絡表達工程項目，記為G={N,A}。集合N={0,1,…,n,n+1}表示n+2個活動，其中活動0和n+1分別表示虛擬開始和結束活動。集合P?N×N表示活動之間的工序關系，若i是j的緊前活動，則(i,j)∈P。每個活動i有|Mi|種可選擇的執行模式，定義每個活動的備選模式集合Mi={1,2,…,|Mi|}，m∈Mi。假設資源有|K|種，定義資源集合K={1,2,…,|K|}，k∈K。工程項目的計劃時間范圍(Plan Horizon)為[0,T]，為方便算法設計，將時間離散化成時段集合，記為T={1,…,|T|}，t∈T。本研究基于假設：1)活動的作業效率僅受空間干涉影響并與空間干涉程度呈負相關；2)活動實際工期僅受作業效率影響，不考慮其它影響因素；3)每個活動所需的作業空間已知。

本文的研究問題可概括為：在已知活動工序、計劃工期以及作業空間需求等參數條件下，考慮活動執行過程中的空間干涉對作業效率和實際工期的影響，如何合理選擇各活動的執行模式并安排活動執行時間，以達到工程工期和成本均最小化的目標。

2.1 作業空間干涉

作業空間干涉(Workspace Interference)或簡稱空間干涉是指在活動執行過程中，其作業空間被其他活動占用，從而對自身產生一定的干擾和影響。空間干涉發生要求兩個或兩個以上的活動在同一時間有相同的空間需求，即作業空間重疊[6]。假設任意活動i的作業空間記為Ωi，函數v(Ωi)表示該作業空間的體積，則活動i的資源密度表示為資源占用的空間體積與總體作業空間體積之比，如公式(1)。

(1)

其中，υk表示每單位資源k占用的空間體積。Rimk表示活動i執行模式m所需資源k的數量。xim為0/1決策變量，當選擇模式m執行活動i時，xim=1；否則，xim=0。

進一步地，定義任意t時段上活動i的空間干涉程度Si(t)為其它活動在t時段內與活動i重疊空間內的資源密度加和，如公式(2)[13-14]。

Si(t)=∑i′∈Ni(ρi′·v(Ωi∩Ωi′)·yit·yi′t),?i,k

(2)

其中，Ωi∩Ωj表示兩作業空間Ωi和Ωj的重疊部分。yit為0/1變量，當活動i在t時段上執行時，yit=1；否則，yit=0。可以看出，對于任意活動i,i′，若v(Ωi∩Ωi′)=0(作業空間不重疊)或者yit·yi′t=0(作業時間不重疊)，則空間干涉為0。

2.2 作業效率函數

活動的作業效率和實際工期均是受空間干涉影響的變量。在無空間干涉的理想情況下，活動i在執行模式m時的計劃工期為Wim，即Wim是完成活動i所需的總工作量或總工時。而在空間干涉的影響下，活動作業效率隨時間改變，記效率函數為ei(t)∈[0,1]。參考作業效率與其它因素(如學習速度、經驗)的函數關系[15]，本文采用Sigmoid函數定義ei(t)，如公式(3)。

ei(t)

(3)

(4)

(5)

為了更容易理解，以圖1的效率函數為例，計劃工期等于效率函數曲線與時間軸圍成的陰影區域的面積。可以看出，在第t時段上活動i是否結束與第t-1時段及之前各時段內的累計工作量有關。當累計工作量小于總工作量要求，則活動i未完成，第t時段將繼續執行活動i；否則，活動i完成且完工時間為t-1。基于這一思想，初始化t為活動i的開始時間，循環上述操作直至活動i完成，即能確定其結束時間。下一節將基于該思想設計算法的編碼方式和解碼機制。

圖1 作業效率和實際工期的關系示意圖

2.3 數學模型

本文同時考慮工期和成本兩目標，建立如下雙目標數學規劃模型。其中，公式(6)計算項目工期fT，即虛擬結束活動的開始時間。公式(7)計算總成本fC，總成本由活動執行成本和延期成本兩部分構成。其中，活動執行成本等于所有活動成本之和∑i,m∈Mixim·Cim(Cim表示活動i在模式m下執行時所需的直接成本)；延期成本等于超期時間max{tn+1-Tdl,0}乘以延遲單位時間的懲罰成本CP(截止工期記為Tdl)。約束(8)是工序關系，即任意活動的開始時間不得早于其前序活動的完成時間。約束(9)定義0/1變量yit，即當活動i在t時段上正在執行時，yit=1；否則為0。由于每個活動只能選擇一種執行模式，因而約束(10)成立。此外，模型還包括上述介紹的公式(1)至公式(5)。

minF=(fT,fC)

(6)

fC=∑i,m∈Mixim·Cim+CP·max{fT-Tdl,0}

(7)

(8)

?i∈N,t∈T

(9)

∑i,m∈Mixim=1

(10)

約束(1)-(5)

3 元啟發式算法

NSGA-II是經典的多目標優化算法之一，它具有全局優化性好、通用性強和易于實現等優勢，且在算法收斂性、魯棒性等方面展現出良好的性能，因而在經濟管理、工業工程等領域得到了廣泛應用[16]。本文采用NSGA-II求解問題，由于未涉及改變NSGA-II算法框架和算子，關于NSGA-II算法介紹請參考相關文獻，此處不再贅述。

求解RCPSP的啟發式算法的編碼方式一般包括活動排序和活動權重兩種，排序和權重均體現活動占用資源的優先權。傳統的解碼機制通常采用貪婪準則，即在資源允許的情況下活動盡早開始。這種方式難以靈活控制活動執行時間上的重疊程度。然而，本文研究的問題需要更精細地控制活動執行時間，從而調整空間干涉對作業效率及實際工期的影響。因此，傳統的RCPSP編碼和解碼方法難以適用本文問題。為此，本文針對性地設計了基于相對延遲編碼方式和相應解碼機制。

編碼由2n個整數元素構成，記為DML=(Δ1,…,Δn,m1,…,mn)。其中，前n個元素中，Δi表示活動i的相對延遲時間，即相對于活動i的最早可開始時間再延遲Δi單位時間，活動i才開始執行。活動i的最早可開始時間指的是活動i的前序活動全部完成的時刻。Δi=0表示活動i不延遲，即其前序活動均完成時立即開始執行。Δi的取值范圍為{0,1,…,MAXΔ}，參數MAXΔ表示最大延遲時間。DML后n個元素為活動的模式選擇，mi∈Mi。由于NSGA-II算法的染色體x=(x1,…,x2n),x∈[Minx,Maxx]為實數向量。針對本文問題特征，設定染色體的每個基因位的取值區間分別為xj∈[0,1],?j∈{1…n}和xj∈[1,Max|Mi|],?j∈{n+1…2n}。接著，根據公式(11)和(12)對任意實數向量x進行離散化處理，將x映射為DML。其中，函數round表示四舍五入。

Δi=round(xi·MAXΔ),?i∈{1…n}

(11)

mi=round(xi+n),?i∈{1…n}

(12)

圖2 解碼機制

4 案例分析

4.1 案例描述和參數設置

某辦公樓裝飾工程由19個活動構成的，活動基本信息如表1所示[3,17]，各活動的作業空間布局如圖3所示。其他參數設置如表2，不妨稱為標準參數設置。

表1 活動參數表

表1 活動參數表

圖3 空間示意圖

表2 實驗的參數設置

算法在軟件MATLAB R2013a上編譯，算例實驗在CPU主頻2.20GHz，內存8GB，64位操作系統配置的個人計算機上運行實現。

4.2 實驗結果分析

4.2.1 標準參數下的結果分析

基于表2參數執行NSGA-II算法，得到一個包含7個解的Pareto集合，解集在目標空間內的分布如圖4所示。工期和成本在一定程度上相互沖突，尤其在工期小于125或大于144時，工期與成本近乎成線性關系。當工期小于125時，成本與工期的沖突性更大，即每壓縮一單位時間所付出的成本更高。以目標取值為(125, 259)的最優解為例，活動的效率曲線如圖5所示，每個活動開始于第一次效率大于零的時刻，結束時刻是在效率再次降為零且此后始終為零時，活動的工期為活動結束時刻與開始時刻之差。從效率曲線圖上不僅可以看出每個活動的開始作業時間和工期，還可以看出每個活動的作業效率隨時間和項目發展的變化情況，可見效率曲線圖比傳統甘特圖更詳盡。

圖4 Pareto解集

圖5 各活動的效率曲線(橫軸為時間，縱軸為效率)

4.2.2 與傳統方法對比分析

基于表2參數設置執行NSGA-II算法，重復實驗10次，共計求得38個最優解。由于空間干涉主要影響活動調度決策，因此令所有解的模式選擇決策保持不變，采用傳統正向調度法求解工程調度方案，計算所得方案的時間和成本目標值。箱線圖6統計了NSGA-II所得的方案相比于傳統方法所得方案在時間和成本兩方面的節省，計算公式為(傳統方案時間/成本目標-NSGAII方案時間/成本目標)÷傳統方案時間/成本目標。相比于傳統方法得到的方案，NSGA-II所得方案在工期目標上平均節省3.09%，在95%的情況下NSGA-II的方案具有更短的工期；在成本目標上，NSGA-II的方案平均節省1.01%，在26%的情況下傳統方法所得方案的成本更大且增加的成本是延期成本，這是由于實驗設定活動執行模式不變，兩組解的活動執行成本相同。實驗表明，傳統方法引起工程延期主要是由于在安排活動時忽略了空間干涉的影響，使得調度方案執行時的空間干涉增大，引起作業效率降低。綜上，本文在工程調度問題中考慮空間干涉影響，對工程進度和成本兩方面目標均更為有利。

圖6 考慮與不考慮空間干涉的方案目標對比

4.2.3 最大延遲時間參數影響分析

為了評估不同MAXΔ取值下算法所得解集的優劣，首先選擇一個解集作為比較基準，視為精確Pareto解集。本文通過隨機運行算法10次，匯集所有解并從中刪除重復解和支配解，最終得到由7個非支配解構成的Pareto解集，其目標向量(完工時間，成本×102)分別為(123，281)，(125，275)，(126，259)，(129，253)，(130，249)，(149，243)，(151，241)。與精確Pareto解集相比，對不同MAXΔ取值下的NSGA-II求得的解集從五方面指標進行評價，分別是無可行解次數、可行解數量、非支配解占比、收斂性(即離精確Pareto前沿的距離)和算法運行時間。令參數MAXΔ=10,20,30,…,70，其它參數按標準設置。不同MAXΔ取值下，每組實驗重復進行10次，五個指標的均值如下表3所示。可以看出，算法平均得到的可行解數量隨著MAXΔ增加而逐漸減少。甚至當MAXΔ≥50時，隨著MAXΔ增長，算法運行失敗(即找不到可行解)的次數明顯增加。這是因為MAXΔ增長使解空間范圍大幅擴大，算法搜索非支配解甚至可行解的難度都大大增加。然而，并非令MAXΔ取值越小就對算法性能有利，從表3的非支配解占比和收斂性指標可以看出，盡管MAXΔ取值越小，算法得到的可行解數量更多，但解的最優性表現欠佳。例如當MAXΔ取值為10和20時，算法得到的非支配解數量較少且離精確Pareto前沿距離較遠。這是由于MAXΔ取值越小，搜索的解空間范圍越小，從而容易遺漏搜索范圍之外的最優解。從表3可以看出，當MAXΔ取值為40時，非支配解占比和收斂性均是最高，分別是22.86%和0.77。在算法運行時間方面，各組實驗的算法平均耗時相差不大，說明對于本案例問題，MAXΔ對算法的運行時間影響較小。綜上，MAXΔ取值過大或者過小都不利于Pareto解的質量。針對本文案例，MAXΔ取值為40時的算法性能表現最好。

表3 不同MAXΔ取值的算法性能比較

*收斂性指標的計算除去了無可行解的實驗結果。

5 結語

工程活動的作業空間干涉會引起資源作業相互干擾，導致作業效率降低，從而對工程總體進度和成本產生不利的影響。本文在工程調度優化問題中考慮空間干涉對作業效率的影響，定義活動作業效率和活動實際工期關于空間干涉的函數，建立時間-成本雙目標優化的工程調度模型。為有效求解模型，采用NSGA-II元啟發式算法并針對性地設計相對延遲編碼方式和解碼機制。對某一裝飾工程案例研究發現，與傳統調度方法相比，本文提出的方法可以更有效地加快工程進度，節省施工成本。通過多組對比實驗探討算法參數MAXΔ對算法性能的影響，結果表明MAXΔ取值過大或過小都不利于算法性能。針對本文的工程案例，MAXΔ取值為40時算法性能最好。本研究對于提高施工方案質量、改善施工作業環境、保證施工安全等方面均具有一定的理論和實踐意義。未來可進一步將優化模型、元啟發式算法與可視化信息技術結合，設計工程調度的計算實驗平臺，為工程實踐者提供技術支持。