帶有多重空間干涉約束的工程調度優(yōu)化

陶莎，盛昭瀚

（南京大學 工程管理學院，南京 210093）

工程調度是工程現場協(xié)調控制的重要任務，其本質上是對一組相互關聯(lián)的活動進行資源分配[1-3]。空間資源是指工程活動執(zhí)行過程中對施工現場三維空間的占用[4-5]。為加快工程施工進度，縮短交付期，工程管理者常常安排多個活動并行執(zhí)行，使得單位時間內空間需求總量增加，引起空間干涉，如空間沖突、擁擠，導致作業(yè)效率降低或中斷、參建主體間發(fā)生沖突，甚至會引發(fā)安全事故[6-7]。因此，工程空間資源調度目標是確保在施工現場并行開展多種作業(yè)活動時，最大程度地規(guī)避空間干涉，確保作業(yè)空間充足、有效[8]。

許多學者基于計算機仿真和可視化技術（如4D CAD、BIM 等），設計活動空間干涉識別與應對的流程和方法[9-12]。Zhang等[10]在BIM 中融入遙感技術，利用GPS定位系統(tǒng)跟蹤施工人員位置并實時判斷其作業(yè)空間，基于BIM 平臺將作業(yè)空間信息可視化，進而識別潛在的空間干涉并及時應對。Choi等[11]設計了一種作業(yè)空間規(guī)劃的流程框架，包括生成4D BIM、識別作業(yè)空間、表征空間占用、識別空間干涉以及解決空間干涉問題等5個階段，避免施工中的空間干涉及其不良影響。這類研究主要是在已知調度計劃方案的前提之下，實時地、局部地識別空間干涉并調整調度方案，但缺乏考慮空間干涉的總體調度方案設計的理論研究。

另外，經典的資源受限項目調度問題（RCPSP）模型時常被應用于工程領域。RCPSP 解決的問題是在滿足項目活動的工序和資源量限制的前提下，制定調度方案以達到工期最短、成本最低、資源利用率最大等目標[13-14]。RCPSP問題中，受限的資源并沒有具體的指代，而是將資源類型大致分為可再生資源（如人力資源）和非再生資源（如材料資源等），并將兩類受限資源的一般性特征體現在不同的約束式中，包括非再生資源總量限制約束以及可再生資源在每個時段上的用量限制約束。近年來，關于RCPSP的研究主要集中在優(yōu)化算法設計上。由于RCPSP是典型的NP-hard問題，研究表明，許多啟發(fā)式算法，如模擬退火、遺傳算法、粒子群算法等，在解決RCPSP及其延伸問題（如多模式資源受限的項目調度問題）時，在算法性能、拓展性、操作便利性等方面均更具優(yōu)勢[15-16]。空間資源作為一類有限的可再生資源，是RCPSP 問題中的受限資源的具體化，因此，RCPSP模型及相關算法設計對其也適用。但目前鮮有學者將項目調度理論模型與空間干涉問題相結合。

綜上所述，可以看出，關于考慮空間干涉特征的總體工程調度方案設計，建立考慮空間干涉約束的工程調度優(yōu)化理論模型等方面的研究尚未深入開展。為此，本文創(chuàng)新性地研究考慮空間干涉的工程調度優(yōu)化問題，對工程的空間資源和空間干涉進行系統(tǒng)地分類，建立帶有多重空間干涉約束的工程調度理論模型。為了有效求解該問題，創(chuàng)新性地設計了考慮多重空間干涉的調度生成機制，并提出一種禁忌模擬退火（Tabu Simulated Annealing，TSA）啟發(fā)式算法。最后，圍繞一個現實的工程案例和隨機生成的算例群進行計算實驗，驗證模型和方法的有效性。

1 工程活動的空間需求與空間干涉

空間是工程活動實施的必要條件之一。工程活動涉及的材料、人、設備等資源以及工程構件都需要占據一定的空間[11]。按占用物內容和用途劃分，工程活動空間需求可分為6類，分別為工程構件空間、人力空間、設備空間、危害空間、保護空間和臨時空間[6]。

針對這6類空間，按空間占用物特性，可將其劃分為：①實空間。空間的占用物是實際的、具體的，如設備、人員、工程的物理構件等。②虛空間。空間的占用物是虛擬的、抽象的，如危害空間、保護空間中的“危害”“保護”等。

進一步，按實體占用物對空間的獨占性，實空間又可分為：①剛性空間。占用物所占用的空間不可被壓縮，占用物對需求空間獨占。例如，工程物理構件所占用的空間，大型設備所占用的空間。②彈性空間。占用物所占用的空間可以被一定程度的壓縮，空間可以在一定程度上被其他活動占用。例如，人員或小型靈活型設備所需空間。

綜上所述，空間分類關系圖如圖1所示。

圖1 空間資源分類示意圖

空間干涉是指工程實施過程中，某作業(yè)活動所需的空間被其他活動占用，致使自身的作業(yè)空間不足，并進而引發(fā)各類不良后果。引發(fā)空間干涉的兩個必要條件是：①活動并行，即執(zhí)行時間存在重疊。②兩個以上的活動占用同一空間，即空間需求存在重疊。不同的空間相互干涉會產生如下4種不同類型的后果：

（1）安全威脅。危害空間與人力空間的干涉。當一個活動的危害空間和另一活動的人力空間產生干涉時，會對員工生命安全造成威脅。例如，物體高空掉落。

（2）物理沖突。剛性空間與實空間的干涉。若空間被某些實體占用且被要求獨占，則該空間排斥任何其他實體的占用。例如，某些物理結構。

（3）破壞沖突。保護空間與實空間、危害空間的干涉。保護空間可能被實空間中的實體或者危害空間產生的危險破壞。例如，混凝土養(yǎng)護。

（4）擁堵。彈性空間之間的干涉。彈性空間具有共享性，但擁擠的環(huán)境會引起人員或設備資源的安全性以及工作質量的下降，從而降低項目的整體質量[7，17]。

本文將安全威脅、物理沖突、破壞沖突統(tǒng)稱為空間沖突。空間沖突一般表現為物理上的不可行或可能造成較嚴重的后果（破壞性的、危險的），在工程中應盡可能避免發(fā)生。輕度的彈性空間干涉可以提高空間利用率，提高活動的并行性從而加快項目進程，但過度擁堵會影響員工和設備的工作質量。因此，擁堵需要控制在一定范圍內。

2 問題描述與一般數學模型

本研究是在經典的RCPSP 模型基礎上，創(chuàng)新性地融入了各類空間干涉約束，使求解的最優(yōu)調度方案不僅滿足工序約束，還能避免和控制活動間的空間干涉，有效應對工程現場空間資源有限，活動空間易沖突或擁堵的實際場景。核心問題旨在已知活動工序、工期以及各類空間需求的條件下，安排各活動的開始時間，使其不僅滿足活動工序約束，還能避免安全威脅、物理沖突和破壞沖突等3類空間沖突發(fā)生，并將擁堵控制在一定范圍內，最終實現項目總完工時間最小化的目標。本研究的創(chuàng)新點和難點在于如何數學化表示各類空間干涉。

模型的建立基于4個前提假設：

（1）活動的各類空間需求已知且固定，空間需求不隨時間而改變。

（2）活動所需的其他資源供應充足。

（3）安全威脅、物理沖突和破壞沖突是杜絕發(fā)生的，擁堵在一定程度上是被允許的。

（4）活動質量與擁堵程度呈線性負相關，即活動質量隨著擁堵程度增加而線性降低。值得注意的是，本文建立的模型及算法并不局限于線性的質量影響函數，也可以采用其他函數形式，如二次、指數和S型曲線等。

采用AON（Activity-On-Node）的項目網絡，記項目G=｛N，A｝。AON 網絡中節(jié)點集合N=｛1，2，…，｝表示個項目活動，不失一般性，虛擬項目的開始和結束節(jié)點不妨記為O和Θ。0/1矩陣｛aij｝，i，j∈N表示活動之間的工序關系，若i是j的緊前活動，則aij=1，否則為0。設項目整個計劃的時間范圍為[0，T]，并離散化為時間片集合T= ｛1，2，…，N T｝，由N T個單位時間間隔構成。建立工程現場空間的三維坐標系，活動的各類空間均定義在該坐標系下。所有已知參數和變量符號含義：

d i—— 活動i的工期

—— 執(zhí)行活動i需要的實空間

—— 執(zhí)行活動i需要的剛性空間

—— 執(zhí)行活動i需要的彈性空間

—— 執(zhí)行活動i產生的危害空間

—— 執(zhí)行活動i需要的人力空間

—— 執(zhí)行活動i需要的保護空間

——活動i的彈性空間對被活動j的彈性空間占用的敏感性

Qi—— 可接受的活動i質量下限，Qi∈[0，1]

—— 活動i的質量對空間擁堵的敏感性

x i≥0—— 開始作業(yè)活動i的時間

Γt?N——t時間片上正在作業(yè)的活動集合

Λi?T—— 活動i正在作業(yè)的時間集合

∈[0，1]—— 活動i完成的擁堵因子

qi∈[0，1]—— 活動i完成的質量因子

fMS——項目總完工時間

基于上述符號定義，建立如下考慮空間干涉的工程調度優(yōu)化的一般數學模型：

目標式（1）表示最小化項目完工時間fMS，即虛擬結束節(jié)點的開始時間。約束式（2）表示項目活動工序約束，活動的開始時間應不早于其緊前活動的結束時間。式（3）避免安全威脅、物理沖突和破壞沖突的任何一種空間沖突的發(fā)生，表示在任意時間片t上并行作業(yè)的活動關于3種空間沖突的空間需求都不重疊（重疊空間體積之和為0）。其中的三重積分計算空間的體積，空間重疊用交集運算符∩表示。例如，dxdydz計算活動i的危害空間和活動j的人力空間重疊的空間體積。式（4）計算執(zhí)行活動i的擁堵因子，表示在活動工期內，活動i的總體彈性空間平均被其他活動占用總空間的百分比。其中，

3 禁忌模擬退火算法

模擬退火算法（Simulated Annealing，SA）在求解許多NP-hard問題，尤其是項目調度問題方面具有操作簡單和快速收斂的特點。為克服算法搜索陷入局部極值，提高收斂速度，本文在基本的模擬退火優(yōu)化算法中引入禁忌表，設計TSA 算法。尤其在算法的調度生成機制（SGS）設計上，創(chuàng)新性地融入多重空間干涉約束，即避免安全威脅、物理沖突、破壞沖突以及控制擁堵程度。

圖2 TSA 流程圖

啟發(fā)式算法的關鍵在于如何將多重空間干涉約束反映到TSA 的內核——調度生成機制（Schedule Generation Scheme，SGS）上，即將AL解碼為一個滿足時間和空間約束的調度方案。本文設計的SGS基于傳統(tǒng)的串行調度生成機制（SSS）創(chuàng)新性地融入多重空間干涉的約束條件。

為方便計算機處理，首先將空間網格化（離散化），設網格粒度Δ= （δx，δy，δz）。工程現場的整體空間被劃分為K個網格，每個網格空間大小相同，體積為δx·δy·δz。基于網格化空間，定義已知參數和 變 量。定 義0/1 參 數?i∈N，k∈K表示活動i的空間占用情況。=1表示活動i的第h類空間需求包含網格k，h∈｛S，G，T，R，W，B｝；反之為0。定義0/1變量，?k∈K，t∈T表示在t時間段的網格空間k的占用情況。=1表示空間網格k在第t時段被h類需求空間占用；反之為0。網格化后，空間體積的計算表示為占用的網格體積求和。

基于網格化空間，SGS算法偽代碼如下：

SGS根據AL中的活動順序依次安排每個活動的開始時間，活動開始時間是滿足各約束條件（工序約束、空間沖突約束、質量約束）下的最早開始時間。具體地，針對任意活動i，工序約束要求活動i的最早開始時間應不早于其緊前活動的最晚結束時間，活動i的最早開始時間Pi｝。初始化令活動i的開始時間為t iE，接著進行循環(huán)操作，判斷空間沖突約束和質量約束是否都滿足。若約束滿足，則當前時間是活動i的開始時間；否則，令活動i的開始時間延遲一單位時間，繼續(xù)判斷約束條件是否滿足。依次循環(huán)，直至找到滿足所有約束的開始時間。針對空間沖突約束，不等式組（7）計算各類空間重疊的體積，進而判斷是否存在安全威脅、物理沖突和破壞沖突。其中，“or”條件表示當不等式組中任意一個公式成立，空間沖突發(fā)生。針對質量約束，式（8）、（9）計算當前活動與已安排的活動之間彈性空間干涉（擁堵）影響下的質量因子。若質量因子大于下限，則說明擁堵在可接受范圍內，分配當前時間為活動的開始時間；否則，不可接受，需將活動開始時間延遲一單位時間，繼續(xù)上述判斷，直至質量約束滿足。由于有限的時間延遲操作能減少或避免活動時間重疊，從而減少或避免空間干涉，故SGS可以在有限次迭代中產生滿足空間干涉約束的調度方案。當所有活動的開始時間確定，得到一個滿足所有約束的活動調度方案，SGS算法結束。

4 計算實驗與結果分析

4.1 實際案例分析

基于文獻[6]中的真實案例，本文設計的工程案例是一個由9個活動構成的建設項目，各活動基本信息如表1 所示。根據表1，加上虛擬開始節(jié)點0和結束節(jié)點10，項目的AON 項目網絡如圖3所示。設置網格粒度Δ= （0.5，0.5，0.5），各個活動的空間需求可視化表示如圖4所示。例如，活動3、4、5搭建的腳手架需要臨時空間的最小頂點位置為（0，-3.5，0），最大頂點位置為（40，-1.5，9），空間體積為720 m3。其他已知參數以及TSA 算法的參數按表2設置，其中，函數??表示向下取整。

表1 活動信息表

圖3 AON 網絡

圖4 三維空間需求

表2 參數設置

執(zhí)行TSA 算法求解算例，算法在軟件MATLAB R2013a上編譯，算例實驗在CPU 主頻2.53GHz、內存2GB、32位操作系統(tǒng)配置的個人計算機上運行實現。僅耗時164.73 s，迭代收斂生成最優(yōu)調度方案的總工期fMS=15。最優(yōu)調度方案具體表示為甘特圖，如圖5所示。由圖5可以看出，該調度方案避免了活動6 產生的安全威脅以及活動3、4、5與其他活動可能發(fā)生的物理沖突。活動7、8的彈性空間在時間段（2，4]上相互干涉，但只是產生輕微擁堵，活動7、8 的擁堵對活動質量的影響被控制在小于0.02的范圍內，活動7、8的質量因子分別是0.983 3和0.999 7，均大于0.98，其他活動質量因子均為1。該方案不僅滿足活動工序約束，還避免了空間沖突的發(fā)生并控制擁堵在可接受的范圍內。

圖5 最優(yōu)調度方案甘特圖

4.2 隨機算例實驗分析

隨機生成一組算例，算例規(guī)模分別為10、20、30、40、50，每個規(guī)模下隨機生成5個算例數據，包括項目計劃網絡以及每個活動的各類空間需求。不妨將每個算例命名為Js-n，其中，s為規(guī)模，n為算例編號。例如，J30-2表示規(guī)模30的第2個算例。其他已知參數的隨機生成規(guī)則為：

其中，函數U表示均勻分布。TSA 算法參數設置如表3所示，并令=0.95。

表3 質量下限影響分析

為了驗證算法的有效性，采用本文提出的方法（考慮空間干涉）和傳統(tǒng)調度方法（不考慮空間干涉）求解算例問題。統(tǒng)計各問題規(guī)模下的平均工期和平均質量，如圖6所示。由圖6可以看出，兩種方法求解出最優(yōu)方案的工期基本相同，但考慮空間干涉的最優(yōu)方案的平均質量更高。這說明，用本文提出的方法求解的調度方案在確保工期最小的情況下，資源擁堵程度更低。事實上，除了算例J40-4之外的其他所有算例，兩方法得到的最優(yōu)工期均相同。即便對于算例J40-4，不考慮空間干涉的最優(yōu)工期為38，考慮空間干涉的最優(yōu)工期為39，僅僅延長了一個單位時間。

圖6不考慮和考慮空間干涉工程調度工期和質量對比圖

圖7所示為不考慮空間干涉約束時最優(yōu)調度方案的各類空間沖突和總空間沖突水平。由圖7可以看出，不考慮空間干涉時，調度方案容易產生空間沖突，并且空間沖突水平隨著算例規(guī)模的增大而增大。相比之下，本文設計的方法在解碼SGS 流程中已經避免了空間沖突，3類空間沖突水平和總空間沖突水平均為0。

圖7 不考慮空間干涉時的各類空間沖突

以J50-1為例，研究質量下限Qi對結果的影響。保持其他參數取值不變，設置Qi取值分別為1，0.9，…，0.5。每組參數做3次實驗，統(tǒng)計結果見表3。可以看出，隨著質量因子下限的不斷降低，最優(yōu)調度方案的總工期逐漸縮短（由79逐漸降至68）。這是因為，當Qi降低，算法允許活動間存在更大程度的擁擠，活動并行的時間增加，故總工期得以壓縮。但是總工期對參數改變的靈敏度不同，在[0.8，1]區(qū)間內，Qi每降低0.1，總工期下降3～4個時間單位；而在[0.5，0.7]區(qū)間內，Qi每降低0.1，總工期只下降了一個時間單位，工期的壓縮幅度隨Qi的下降呈現逐漸減緩的趨勢。此外，隨著參數值下降，算法耗時也逐漸減少。這是因為Qi越低，質量約束越容易滿足，解碼算子（SGS）中的循環(huán)次數減少，從而解碼速度得以提高。最優(yōu)方案的平均質量因子和最低質量因子值隨著Qi的降低均逐漸下降，但確保活動質量大于等于Qi。

綜上分析，本文設計的方法能有效避免安全威脅、物理沖突和破壞沖突等3類空間沖突，有效控制擁堵，將擁堵對活動質量的影響控制在可接受的范圍之內，并且盡可能地縮短總工期。本文提出的方法能有效地保證工程調度的效率和質量。

5 結語

在工程實踐中，減少活動之間的空間干涉是保障工程進度和質量的重要措施。研究帶有多重空間干涉的工程調度優(yōu)化問題，創(chuàng)新性地將空間從多個角度分類并定義了4類空間干涉。建立考慮多重空間干涉約束的工程調度數學規(guī)劃模型，設計應對該問題的TSA啟發(fā)式算法，尤其是在SGS的設計中融入了多重空間干涉約束條件。例舉一個工程實例和隨機生成的算例群進行計算實驗，結果表明，TSA 生成的最優(yōu)工程調度計劃方案能有效地避免安全威脅、物理沖突和破壞沖突3類空間沖突發(fā)生，控制擁堵在一定范圍內并盡可能地縮短項目工期。本文研究的問題、模型及算法可依據具體的工程特點，自定義空間需求、干涉約束和質量影響函數，具有一定的普適性和可擴展性，為工程管理者提供決策支持。未來可以在空間需求的動態(tài)性特征、空間干涉對作業(yè)效率的影響以及算法性能提升等方面做進一步研究。