尹 靜，楊阿慧

（北京建筑大學機電與車輛工程學院，北京100044）

作為施工現(xiàn)場運輸提升建筑材料的關鍵特種設備，塔式起重機（以下簡稱塔機）目前廣泛應用于建筑工程施工過程，特別是在高層建筑、異形建筑等工程量密集的中心城市區(qū)域［1］。塔機的作業(yè)時間不僅直接影響施工進度、工期成本，并且會對設備自身健康以及施工現(xiàn)場帶來巨大的安全隱患。目前，塔機駕駛人員和現(xiàn)場調度人員往往根據個人主觀經驗管理塔機工作過程，沒有形成規(guī)范的作業(yè)計劃以及科學的理論體系。因此，施工現(xiàn)場迫切需求優(yōu)化塔機服務序列，減少作業(yè)流程時間，提升塔機作業(yè)效率，該研究具有工程應用價值與理論意義。

當前，國內外有關塔機提升作業(yè)的相關研究可分為兩類：塔機的布局優(yōu)化研究和塔機提升過程中效率的研究。Zhang等［2］提出一種確定塔機最優(yōu)位置的方法，通過定位吊鉤總運動時間最小的點來優(yōu)化位置。Tam等［3］提出一種利用遺傳算法（GA）和人工神經網絡（ANN）確定最優(yōu)塔機位置，即總成本最小點的方法（總成本=移動時間×所需成本）。Sacks等［4］設計一種方法，將監(jiān)測設備安裝在塔機上，自動收集數(shù)據并將數(shù)據應用于項目管理。近年來，越來越多的塔機管理研究使用了建筑信息模型（BIM）。Lee等［5］設計一種塔機導航系統(tǒng)，該系統(tǒng)利用BIM對塔機操作人員不可見的起重物料進行導航，并開發(fā)一種利用傳感器和攝像機實時監(jiān)測下降物料位置來優(yōu)化塔機物料升降的方法。已有的研究成果中大多圍繞塔機布局、塔機監(jiān)控、塔機提升量等方面。2014年，Zavichi等［6］首次提出塔機的服務序列問題（Crane Service Sequence Problem，CSSP），并將其轉化為TSP（Traveling Salesman Problem）問題進行求解。Monghasemi等［7］基于博弈論方法，對起重機服務序列的等待時間進行了優(yōu)化。本文重點考慮物料請求任務帶有交貨期的情形，通過計算吊鉤行程時間設計了一種動態(tài)搜索啟發(fā)式算法（DSF），得到服務序列優(yōu)化方案，在滿足交貨期約束的同時最大化縮短塔機作業(yè)流程時間。

1 塔機服務調度問題描述

塔機服務調度問題可以使用與行程時間相關聯(lián)的圖形（即頂點和連接邊的集合）描述。圖1表示施工現(xiàn)場的工作人員（C）和物料（M）節(jié)點組成的圖表布局，中央的塔機接收指揮人員的任務信號后把相應的物料從儲存位置移到指定的工作人員位置（物料需求位置）。決策者應以總操作時間最小化為目標，以任務到期時間和優(yōu)先級等不同的約束來實現(xiàn)目標。

圖1 塔機布局說明Fig.1 Tower crane layout description

假設某施工現(xiàn)場塔機在進行作業(yè)，現(xiàn)場有I個物料供應地點Si，其中i=1，2，…，I；有J個物料需求地點Dj，j=1，2，…，J；有M個物料請求任務Rm，m=1，2，…，M；且每個任務具有交貨期DDRm。優(yōu)化目標是滿足任意完工時間Rm≤DDRm，并且所有任務的最大流程時間最短。該問題共有M！個調度方案，屬于NP-hard問題。

2 吊鉤行程時間計算

最小化塔機作業(yè)流程時間需要準確計算出吊鉤行程時間。本文采用基于供應地、需求地和設備物理位置的塔機作業(yè)時間分析模型計算塔機吊鉤行程時間。以塔機位置為基準建立坐標系統(tǒng)［7］，如圖2所示，塔機位置PT=（xT，yT）=（0，0），物料供應地A位置為（xA，yA），物料需求地B位置為（xB，yB）。

圖2 塔機運動水平面坐標系Fig.2 Tower crane motion horizontal coordinate system

吊鉤行程時間計算過程如下：

（1）徑向運動時間和角行程時間。

根據塔機的制造規(guī)格可以確定徑向速度（Vr）、角速度（Va）和垂直速度（Vv）。吊鉤在A點和B點之間的徑向時間（Tr(i，j)）和角行程時間（Ta(i，j)）可以使用如下公式計算：

（2）吊鉤水平行程時間。

根據徑向時間和角行程時間合成吊鉤在水平方向上的行程時間，考慮引入λ參數(shù)反映操作者在徑向和角度方向上同時移動吊鉤的能力，即徑向運動和角度方向上運動的重疊程度。其中，λ是連續(xù)的正數(shù)，取值在0≤λ≤1之間，λ的值越小反映徑向和角度方向移動吊鉤的同時性越高。吊鉤水平行程時間Th可以使用如下公式計算：

（3）吊鉤垂直行程時間。

假設點A和B，正視圖如圖3所示，塔機的垂直行程時間（Tv(i，j)）可以計算如下：

式中：ZA、ZB分別為點A和B的z（高度）坐標；h為最小提升高度；因子2為距離被遍歷兩次（加載和卸載）。

圖3 塔機垂直平面內的運動系統(tǒng)Fig.3 Motion system in the vertical plane of the tower crane

（4）吊鉤總行程時間。

根據吊鉤水平行程時間和吊鉤垂直行程時間合成吊鉤的總行程時間：

式中：η、μ為連續(xù)的正數(shù)，取值為0≤η≤1，1≤μ≤∞；參數(shù)η為操作者在水平和垂直方向上同時移動吊鉤的能力。由于施工現(xiàn)場存在天氣、障礙物等不可控的條件，塔吊作業(yè)流程時間可能因此而發(fā)生變化，參數(shù)μ用于說明施工現(xiàn)場的不可控條件。η的值越小表明操作者在水平和垂直方向上移動吊鉤的同時性越高。參數(shù)μ的值越小則反映施工現(xiàn)場的操作條件比較好。λ、η、μ的具體數(shù)值需要根據施工現(xiàn)場的施工情況來進行取值。

3 塔機服務調度優(yōu)化

符號定義：

PT：塔機吊鉤的位置；

Si：物料供應地，Si∈S={Si|i=1，2，…，I｝；

Dj：物料需求地，Dj∈D={Dj|j=1，2，…，J｝；

Rm：物料請求任務，Rm∈R={Rm|m=1，2…M}；

u：物料類型，u=1，2，…，U；

Tloading：物料裝載時間；

Tunloading：物料卸載時間；

SRm：任務Rm的物料供應地，SRm∈S；

DRm：物料請求任務Rm的物料需求地，DRm∈D；

DDRm：任務Rm的交貨期；

TRm：任務Rm處理時間；

CRm：任務Rm完工時間；

Ttotal：任務集R={Rm|m=1，2，…，M｝最大流程時間。

3.1 優(yōu)化模型

本文針對帶有交貨期的物料請求任務，在最小化塔機總流程時間的同時滿足交貨期約束。每一個任務的處理時間由4部分組成：

式中：TT(PT，Sm)為塔機吊鉤從當前位置PT移動到物料供應位置Sm所用的行程時間；TT(Sm，Dm)為吊鉤從物料供應位置Sm到物料需求位置Dm所用的行程時間。

決策變量任務Rm的服務序列號XRm：

本文研究滿足以下幾點假設：

（1）?Rm∈R，物料請求任務Rm之間沒有先后順序約束，且無相互影響；

（2）?Rm∈R，物料請求量能夠一次完成；

（3）?Rm∈R，調度時刻均已到達。

3.2 動態(tài)搜索啟發(fā)式算法（DSF）

基于上述時間計算，根據塔機工作過程中運動特征，設計動態(tài)搜索啟發(fā)式方法進行求解，具體步驟如下：

步驟1初始化吊鉤位置PT、物料供應地集合S、物料需求地集合D、物料請求任務集合R。

步驟2設置待調度任務集合R'=R，循環(huán)變量z=1，z≤M，z++。

步驟3?Rz∈R'，TT(PT，Sz)和TT(Sz，Dz)的吊鉤徑向運動時間和角行程時間可以根據相關點的位置坐標利用式（1）～式（2）計算，再結合式（3）計算吊鉤的水平行程時間；利用式（4）計算吊鉤垂直行程時間，結合式（5）合成吊鉤總的行程時間；分別給定Tloading和Tunloading的值，根據式（6）得到處理時間TRz。

步驟4交貨期檢查。?Rz∈R'，計算完工時間CRz。

IfCRz≤DDRz，選擇minTRz，并將該任務的服務序列號記為XRz=z；更新代調度任務集合R'=R'-｛Rz｝。

步驟5IfCRz＞DDRz，選擇沖突任務記為XR'z；ifz=1，輸出無解，并跳出結束，否則，XR'z=z-1，z=z-1，更新代調度任務集合R'=R'-｛Rz｝+｛R'z｝；更新吊鉤位置PT=DR'z。

步驟6重復步驟2～步驟5，直到所有的物料請求任務執(zhí)行完成。

4 數(shù)值算例

4.1 問題參數(shù)

圖4 描述了某建筑施工現(xiàn)場的布局圖。3種物料M1、M2和M3，存放于4個物料供應點S1～S4。每個物料供應點位置坐標和可用物料類型如表1所示。物料需求點D1～D9位置坐標如表2所示。本例中共有10個物料請求任務，每個任務的物料供應地坐標、物料需求地坐標和各自的交貨期信息如表3所示。

圖4 建筑施工現(xiàn)場的布局Fig.4 Layout of the construction site

表1 材料供應地點的數(shù)據Tab.1 Material supply location data

表2 材料需求地的數(shù)據Tab.2 Material demand data

表3 物料請求任務數(shù)據Tab.3 Material request task data

現(xiàn)場使用重載4000 HC 100利勃海爾塔式起重機［8］。根據其制造規(guī)格，它的垂直速度Vv=136 m/min，徑向速度Vr=60 m/min，回轉角速度Va=0.5 rad/min。假設天氣條件良好，正常運行條件下材料供應位置和需求位置之間的吊鉤運動路徑沒有障礙物，并且不會引起額外的時間延遲，設置μ=1。對現(xiàn)場塔機操作者的能力進行評估，參數(shù)λ和η分別設定為1.0和0.25。材料加載時間Tloading和卸載時間Tunloading設定為1.0 min，并且恒定。

4.2 計算結果

針對上述具體問題和相關數(shù)據，采用動態(tài)搜索啟發(fā)式算法DSF進行計算，數(shù)據如表4所示，最大流程時間為51.24 min。

表4 DSF算法下任務的移動數(shù)據Tab.4 Mobile data of tasks under the DSF algorithm

4.3 算法比較

為了驗證所提算法的有效性，將其與先進先出（FIFS）和最短作業(yè)優(yōu)先（SJF）進行比較。FIFS計算吊鉤移動的路徑信息以及時間結果如表5所示，總流程時間為63.05 min。SJF根據供應地和需求地之間的吊鉤行程時間確定服務序列方案，計算結果如表6所示，總流程時間為59.23 min。

表5 FIFS算法下任務的移動數(shù)據Tab.5 Mobile data of tasks under FIFS algorithm

表7 為3種算法的比較結果?？梢钥吹?，采用動態(tài)搜索啟發(fā)式算法得到的服務序列進行塔機調度，能夠滿足10項任務的交貨期要求，并且作業(yè)時間性能優(yōu)于傳統(tǒng)啟發(fā)式方法。

表6 SJF算法下任務的移動數(shù)據Tab.6 Mobile data of tasks under the SJF algorithm

表7 3種啟發(fā)式方法的比較Tab.7 Comparison of heuristic methods

5 結語

本文旨在通過優(yōu)化塔機服務序列，在滿足物料請求任務交貨期的情況下最大限度地減少吊鉤的總行程時間，從而提高塔機的工作效率。通過解析吊鉤行程時間并提出動態(tài)搜索啟發(fā)式算法（DSF）對目標函數(shù)進行優(yōu)化，對有交貨期的作業(yè)進行及時合理的安排，避免進度延遲。通過數(shù)值實驗對DSF算法進行了驗證，并將其與FIFO和SJF進行比較，可以看到得到的物料請求服務序列方案能夠兼顧交貨期與流程時間，提升了塔機作業(yè)效率，可以為施工現(xiàn)場管理提供指導參考。