基于活動圖的建筑工程施工規(guī)劃與調(diào)度方法研究

林張紀(jì)

（福建水利電力職業(yè)技術(shù)學(xué)院 建筑工程系，福建 永安 366000）

由于建筑工程需要使用大量的材料、成品以及工程設(shè)備，并且涉及大量的勞動力，因此建筑工程通常具有施工周期長、資金成本高的特點。由于建筑工程中各項施工活動之間可能具有依賴性，因此需要對施工活動進(jìn)行合理地規(guī)劃和調(diào)度[1]。在現(xiàn)實中，由于施工現(xiàn)場情況復(fù)雜，工程設(shè)備（如卡車）與現(xiàn)場工作人員發(fā)生碰撞的事故時有發(fā)生?，F(xiàn)有關(guān)于建筑工程施工規(guī)劃和調(diào)度的研究大多數(shù)以降低工程總成本和縮短工期為目標(biāo)[2]，因此無法滿足安全需求。為了平衡建筑工程成本、安全和工期之間的矛盾，本文以活動圖為基礎(chǔ)，設(shè)計了行之有效的施工活動規(guī)劃與調(diào)度方法。

1 系統(tǒng)模型

1.1 活動圖模型

活動圖是一個有向無環(huán)圖，用 G = ( V， E)表示，如圖1所示。其中，邊(v， v′)∈E表示活動v∈V是另一個活動v′∈V的前置條件。集合Vs∈V表示沒有輸入邊的一組起始節(jié)點，集合Vf∈V表示沒有輸出邊的一組終點節(jié)點。施工計劃用序列 P = (v1， v2，...，vn)表示，P體現(xiàn)了活動之間的前置關(guān)系。假設(shè)施工時間為T，施工現(xiàn)場出現(xiàn)的靜態(tài)障礙物初始集合為 O ( t) ? W ， t∈ T 。由于施工現(xiàn)場可能會出現(xiàn)新的障礙物，同時舊的障礙物可能會隨著施工進(jìn)行而消失，因此 O ( t)會隨著時間的變化而發(fā)生變化。

將單個活動的系統(tǒng)狀態(tài)空間定義為 Xv。系統(tǒng)狀態(tài) xv∈Xv由描述一個子問題的參數(shù)組成。xv中的參數(shù)可以是移動物體（例如卡車）的配置、方向和速度以及活動所使用的資源量（例如土壤和混凝土量）。時變狀態(tài)空間Z是系統(tǒng)狀態(tài)空間和時間的笛卡爾積，即Z = X × T ，時變狀態(tài)z∈Z表示為z=(x， t)。系統(tǒng)中的移動設(shè)備用集合表示。結(jié)合移動體和靜態(tài)障礙物，將障礙物狀態(tài)空間定義為將自 由活動空間定義為將初始狀態(tài)定義為zI∈Zfree，將目標(biāo)狀態(tài)集合定義為

1.2 增強離散事件模型

活動圖中高級構(gòu)建計劃的每個節(jié)點都表示為增強離散事件系統(tǒng)規(guī)范（DEVS）[3-4]模型。 該模型與施工現(xiàn)場的幾何信息一起用于生成移動物體的無障礙路徑和策略?；顒訄D中的每個節(jié)點都與增強的DEVS模型相關(guān)聯(lián)。

DEVS用于進(jìn)行離散事件模擬，是有限狀態(tài)自動機(jī)的擴(kuò)展。在對原始的DEVS模型進(jìn)行擴(kuò)展后，得到本文的增強DEVS模型。對于活動v，增強 DEVS事件調(diào)度模型ESv可以被表示為。 其 中Zν=Xν×T是系統(tǒng)狀態(tài)的子集。施工現(xiàn)場的任何活動都由一系列事件組成。第i個事件用ηi表示，Ev表示有限事件集合，ELv表示事件列表。

根據(jù)活動圖G= (V，E)，可以得到多個候選施工計劃P1， P2，…，Pk。為了對每個計劃進(jìn)行仿真，需要為Zfree空間中的移動設(shè)備和工人計算無碰撞軌跡。

對于查找移動設(shè)備的無碰撞軌跡，給定初始配置xI，一組目標(biāo)狀態(tài)XG和一組靜態(tài)障礙物O (t)，找到無碰撞軌跡使得

假設(shè)施工現(xiàn)場有m個工人 A1， A2，…，Am，他們必須從其初始位置xI到達(dá)目的地區(qū)域XG。對于查找工人安全軌跡的問題，給定初始配置xI，一組目標(biāo)狀態(tài)XG、一組靜態(tài)障礙物 O (t)以及移動設(shè)備的軌跡 B (t)，找到一個無障礙軌跡使得

1.3 安全評估模型

需要為每個計劃P1， P2，…，Pk計算安全評分以選擇最佳方案。為了計算單個計劃的安全評分，通過模擬所有節(jié)點來評估整個計劃。安全評分函數(shù)定義為R:Z~→[0，1]，其中，0是最安全的分?jǐn)?shù)，而1是最危險的分?jǐn)?shù)。因此，嘗試最小化安全評分。根據(jù)軌跡路徑計算計劃的安全評分，即給定一組時變系統(tǒng)軌跡Z~，計算相應(yīng)計劃P的安全分?jǐn)?shù)。

在得到計劃的安全分?jǐn)?shù)后，需要選擇最佳計劃，該最佳計劃可以提供最少的完成時間和最佳安全分?jǐn)?shù)。

一旦為備用計劃計算了安全分?jǐn)?shù)，計劃經(jīng)理就需要提取最佳計劃，該計劃可以提供最少的完成時間和最佳安全分?jǐn)?shù)。

2 活動規(guī)劃和調(diào)度

圖1顯示了本文系統(tǒng)框圖：活動調(diào)度器負(fù)責(zé)生成活動的候選序列，它與事件調(diào)度器通信以模擬一個或多個活動。然后，事件調(diào)度器使用移動規(guī)劃器為移動物體生成路徑，使用人員移動規(guī)劃器生成工作人員的路徑，然后協(xié)調(diào)器計算出無沖突的調(diào)度方法。

圖1 系統(tǒng)框圖

無論是移動的還是靜止的障礙物，對施工計劃的安全性都有不同的影響。同樣，不同的計劃序列會產(chǎn)生不同的安全評分。

2.1 基于活動圖的計劃提取

采用拓?fù)渑判蛩惴▉硖崛∷锌赡艿挠行в媱潯＝o定n個頂點和一組整數(shù)索引對(i，j)，拓?fù)渑判蛩惴康氖钦业揭粋€排列v1，v2，…，vn，使得對于所有(，)i j，i都出現(xiàn)在j的左側(cè)。

活動圖中可能有多個開始和結(jié)束活動。因此，將兩個虛擬活動sv和fv作為持續(xù)時間為零的開始和結(jié)束活動添加到圖中，以便創(chuàng)建單個開始和結(jié)束點。另外，通過將sv作為父級，將fv作為其子級節(jié)點，將浮動活動節(jié)點（無前置條件約束）添加到G中。默認(rèn)情況下，sv被標(biāo)記為已訪問，并且是所有初始節(jié)點的父級，而fv是所有結(jié)束活動的子級。給定由拓?fù)渑判蛩惴ㄉ捎媱漃，算法1用于調(diào)度P內(nèi)的活動。

算法1 活動調(diào)度器

計劃中的每個節(jié)點都需要通過我們的事件模擬方法進(jìn)行評估。從活動調(diào)度器接收活動隊列Q，其中每個活動都是事件η∈E的集合。

算法2結(jié)合了本文的增強DEVS模型，模擬活動圖中的多個節(jié)點。為了進(jìn)行仿真，首先為每個節(jié)點創(chuàng)建一個事件調(diào)度模型，提取初始狀態(tài)∈，并從事件集中獲取第一個事件以初始化事件列表。然后對來自多個活動的所有事件進(jìn)行調(diào)度。如果列表中有多個事件，則選擇最小的即時事件。接下來使用動作規(guī)劃器生成軌跡，每個軌跡包含一系列配置。由于系統(tǒng)的狀態(tài)涉及建筑工人在工作區(qū)中移動，因此使用人員動作規(guī)劃器生成移動工作人員的軌跡。

算法2 事件調(diào)度器

2.2 無碰撞軌跡生成

由動作規(guī)劃器生成的移動設(shè)備軌跡序列并不能確保沒有碰撞發(fā)生，因此跟隨軌跡移動的物體可能會與其他移動的物體或正在移動的工人碰撞。給定m個運動物體，用m維協(xié)調(diào)空間 [0，1]mΓ=來表示無碰撞路徑。Γ中的第i個坐標(biāo)表示路徑的定義域 Γi=[0，1]。假設(shè)γi是空間 Γi中的一個點，那么物體與物體之間的障礙物區(qū)域為因此有

在狀態(tài)(0，0，…，0)∈Γ時，所有物體都處于其初始配置 x，而在狀態(tài)(1，1，…，1)∈Γ時，所有 物體都處于其初始配置。對于連續(xù)路徑h : [0，1]→Γfree，將 A*搜索算法[5]應(yīng)用于生成無碰撞的路徑h。允許一個物體以恒定的速度移動，或者使其保持靜止以便其他物體通過。由于搜索空間有限，因此該*A搜索算法僅需多項式時間。

2.3 計劃安全評估

假設(shè)邊界是一個理想的矩形區(qū)域。如果現(xiàn)實的邊界不是矩形區(qū)域，可以使用矩形對其進(jìn)行近似，然后將添加的區(qū)域轉(zhuǎn)換為靜態(tài)障礙物。需要將施工現(xiàn)場環(huán)境分解為多個區(qū)域，以便進(jìn)行安全評分，并生成風(fēng)險熱圖，以可視化方式顯示工作區(qū)中隨時間變化的危險區(qū)域。將施工現(xiàn)場W分解為δ個正方形區(qū)域。在t時刻，施工計劃的安全分?jǐn)?shù)評分由該時刻δ個正方形區(qū)域安全評分的總和構(gòu)成。每個正方形的安全評分是動態(tài)的，并且與到移動設(shè)備的距離成反比。

其中d(?) 是距離函數(shù)，而tQ是在時間t的活動隊列。參數(shù)α和β是獲得更好分?jǐn)?shù)的比例因子。障礙物內(nèi)部的正方形的安全性得分為

在時間t具有δ個正方形區(qū)域的平均安全評分為

2.4 最佳計劃選擇

工期較長的施工計劃會產(chǎn)生較好的安全性評分，但由于建筑項目具有成本、資源和時間限制，這樣的施工計劃是不可行的。因此，在對計劃P進(jìn)行劃分后，并行執(zhí)行每個劃分Qt中的所有活動，此時建設(shè)項目的總成本L為

需要選擇一個能同時優(yōu)化建筑成本、安全評分和完成時間的最優(yōu)計劃。值得注意的一點是，可能并不存在任意一個元組可以同時將所有目標(biāo)最小化，因此需要在各個目標(biāo)之間取得平衡。這樣的問題就是一個Pareto優(yōu)化[6]問題。

因此，設(shè)計了一個近似的方案，通過從所有元組中取每個目標(biāo)的最小值來計算最佳元組。如果元組中的每個目標(biāo)值均小于元組，那么計劃 Pi支配計劃 Pj。按照這個定義，能夠找到所有非支配解，這些非支配解就是Pareto最優(yōu)解。首先定義一個基準(zhǔn)元組，即

3 案例分析

在案例研究中，采用一個簡單的案例來對本文方法進(jìn)行研究和評估。該案例的活動圖包含一個虛擬開始節(jié)點和一個虛擬結(jié)束節(jié)點、兩項評估活動（分別是和）以及兩項施工活動（分別是和）。施工活動需要在評估活動完成后才可以開始，即活動和分別是活動和的前置條件。

使用Python編程語言實現(xiàn)了拓?fù)渑判蛩惴?，并生成三個包含活動順序的計劃，如圖2所示。然后，使用Python中的SimPy仿真模塊來仿真算法 2的離散事件調(diào)度程序，并使用移送策略庫（MSL）來生成用于不同活動的移動設(shè)備軌跡。三種計劃的施工成本、安全評分和工期如表1所示。由表1可知，計劃是最安全的，但與此同時具有最長的工期和最高的成本。因此，綜合成本、安全和工期三個重要指標(biāo)考慮，計劃是最理想的施工計劃。

圖2 三種計劃的活動順序

表1 不同計劃的各項指標(biāo)的結(jié)果對比

4 結(jié)論

本文兼顧施工總成本、安全和工期三個重要指標(biāo)，設(shè)計了有效的建筑工程規(guī)劃和調(diào)度方法，通過一種近似的方案來選擇合適的施工計劃。本文的結(jié)果能為項目經(jīng)理在規(guī)劃階段評估施工計劃的安全性提供寶貴的信息。在未來的工作中，將考慮建筑施工現(xiàn)場的不確定因素（例如工程車輛移動的不確定性），同時在三維模式下研究施工設(shè)備的運動，以避免碰撞的發(fā)生。在后續(xù)的工作中，使用涉及大型活動的大型建筑項目的信息來評估該方法。