直升機(jī)垂直補(bǔ)給的任務(wù)載重層次調(diào)度算法

田立軍

(中國人民解放軍91404部隊，河北 秦皇島 066001)

垂直補(bǔ)給的主要對象是水面上的各種艦船,顧名思義,垂直補(bǔ)給是指在空中利用直升機(jī)對海上的艦船進(jìn)行物資補(bǔ)充。隨著補(bǔ)給技術(shù)的日益進(jìn)步，海上補(bǔ)給已經(jīng)由縱向拖帶補(bǔ)給、橫向靠幫補(bǔ)給向縱橫向和垂直綜合立體補(bǔ)給方向發(fā)展[1]。目前,面向垂直補(bǔ)給調(diào)度策略方面的研究工作還處于起步階段，尚未形成系統(tǒng)化理論方法，由于缺乏良好的調(diào)度策略，制約了補(bǔ)給貨物的體積和重量，影響了補(bǔ)給效率[2]。

通過分析直升機(jī)多次往返吊運(yùn)的特點，本文提出一種分層次的垂直補(bǔ)給調(diào)度算法。該算法的基本內(nèi)容主要包括直升機(jī)任務(wù)載重的分層，補(bǔ)給貨包按重量分類和補(bǔ)給貨包分波次三個部分。對直升機(jī)任務(wù)載重進(jìn)行分層，利用任務(wù)載重層次按重量將補(bǔ)給貨包進(jìn)行分類，將補(bǔ)給貨包分波次，得出垂直補(bǔ)給任務(wù)的調(diào)度計劃[3]。通過與簡單調(diào)度算法進(jìn)行對比仿真試驗，說明了該算法能有效地提高垂直補(bǔ)給效率。

1 垂直補(bǔ)給調(diào)度模型

垂直補(bǔ)給調(diào)度是指將任務(wù)分配至資源的過程，一個垂直補(bǔ)給任務(wù)可以描述為一個四元組VM=(P，S，F(xiàn)，A)，其中，P為補(bǔ)給貨包集合，S為補(bǔ)給目標(biāo)船集合，F(xiàn)為任務(wù)用直升機(jī)集合，A為垂直補(bǔ)給操作區(qū)集合。

將補(bǔ)給貨包運(yùn)往補(bǔ)給目標(biāo)船就是一項任務(wù)，而直升機(jī)和操作區(qū)是可以利用的資源，將補(bǔ)給貨包分配到操作區(qū)和直升機(jī)并運(yùn)往目標(biāo)補(bǔ)給船，就是垂直補(bǔ)給調(diào)度[4]。由于直升機(jī)以及垂直補(bǔ)給操作區(qū)是垂直補(bǔ)給流程中的關(guān)鍵因素，為了更好地描述垂直補(bǔ)給調(diào)度模型，首先需要給出直升機(jī)補(bǔ)給能力模型，以及垂直補(bǔ)給操作區(qū)模型。

1.1 直升機(jī)補(bǔ)給能力模型

直升機(jī)補(bǔ)給能力模型描述的是直升機(jī)在參與垂直補(bǔ)給作業(yè)過程中的運(yùn)載能力，工作方式以及相關(guān)制約因素[5]。

首先我們給出與直升機(jī)起飛屬性相關(guān)的約束。設(shè)參與補(bǔ)給任務(wù)直升機(jī)集合F={f1,f2,f3…fK},F∈VM，補(bǔ)給直升機(jī)數(shù)量K∈N*(N*是正整數(shù)集合)。直升機(jī)作業(yè)時應(yīng)滿足以下條件：

Gall(fj)=Ghfj)+Gl(fj)+Gf(fj)+Gp(fj)+Ge(fj)

(1)

Gt(fj)≥Gall(fj)

(2)

Gf(fj)=Gs(fj)+Gu(fj)

(3)

Gf(fj)≤Gfmax(fj)fj∈F

(4)

其中，Gall(fj) 表示任何時刻直升機(jī)fj的總重量 ，Gh(fj) 表示直升機(jī)fj的空機(jī)重量，Gl(fj) 表示直升機(jī)fj的任務(wù)載重量，Gf(fj) 表示直升機(jī)fj的燃油重量，Gp(fj)表示直升機(jī)fj的人員重量，Ge(fj)表示直升機(jī)fj裝備的重量；Gt(fj)表示直升機(jī)fj的最大起飛重量；Gs(fj)表示直升機(jī)fj的安全余油標(biāo)準(zhǔn)量，Gu(fj) 表示直升機(jī)fj的任務(wù)用油量；Gfmax(fj)表示直升機(jī)fj的最大載油量。

式(1)給出了直升機(jī)總重量所包含的內(nèi)容。式(2)說明任何時刻直升機(jī)的總重量必須小于直升機(jī)最大起飛重量。根據(jù)直升機(jī)安全要求，作業(yè)中的直升機(jī)需攜帶油量應(yīng)至少達(dá)到安全余油標(biāo)準(zhǔn)。式(3)表示直升機(jī)的燃油重量包括兩部分，分別是安全余油標(biāo)準(zhǔn)量和任務(wù)用油量。式(4)說明任何時候的直升機(jī)燃油重量必須小于直升機(jī)的最大載油量。

在垂直補(bǔ)給任務(wù)中空機(jī)重量Gh(fj), 人員重量Gp(fj), 裝備重量Ge(fj), 安全余油標(biāo)準(zhǔn)量Gs(fj)為已知量，所以定義任務(wù)中直升機(jī)的固定載重為Gr(fj)=Gh(fj) +Gp(fj)+Ge(fj)+Gs(fj), 將式(1)、(2)和(3)化簡為

GL(fj)≥Gr(fj)+Gl(fj)+Gu(fj)

(5)

由式(5)可得到關(guān)于垂直補(bǔ)給任務(wù)中的兩個可變量即任務(wù)載重量Gl(fx)與任務(wù)用油量Gu(fj)之間的關(guān)系式

Gl(fj)+Gu(fj)≤Gt(fj)-Gr(fj)

(6)

式(6)表示補(bǔ)給直升機(jī)的任務(wù)載重量與任務(wù)用油量之和不能大于直升機(jī)最大起飛重量減去固定載重量Gr(fj)。

由式(3)和(4)可得到關(guān)于任務(wù)用油量的約束式如下

Gu(fj)≤Gfmax(fj)-Gs(fj)

(7)

式(6)和(7)說明了在垂直補(bǔ)給過程中與直升機(jī)起飛屬性相關(guān)的兩個重要變量即任務(wù)載重量與任務(wù)用油量的約束條件。

1.2 垂直補(bǔ)給操作區(qū)排放模型

垂直補(bǔ)給操作區(qū)指的是在補(bǔ)給船的甲板上劃定的用來進(jìn)行垂直補(bǔ)給作業(yè)的區(qū)域。垂直補(bǔ)給操作區(qū)排放模型描述的是補(bǔ)給貨包在操作區(qū)域內(nèi)的排放方式[6]。設(shè)垂直補(bǔ)給操作區(qū)集合A={a1,a2,a3…av},A∈VM,操作區(qū)數(shù)量v∈N*(N*是正整數(shù)集合)。一個垂直補(bǔ)給操作區(qū)可以描述為一個五元組a={L,W,l,w,α}，其中，操作區(qū)橫向總長L，縱向總長W，橫向排放間距l(xiāng)，縱向排放間距w是規(guī)定值，α是操作區(qū)內(nèi)貨包到排放順序的映射。

1.3 垂直補(bǔ)給調(diào)度模型

設(shè)補(bǔ)給貨包集合P={p1,p2,p3…pn},P∈VM補(bǔ)給貨包個數(shù)n∈N*。由垂直補(bǔ)給任務(wù)的定義可知，一次補(bǔ)給任務(wù)可能需要向多個補(bǔ)給目標(biāo)吊運(yùn)多個補(bǔ)給貨包[7]。由于直升機(jī)一次加油后可以完成的吊運(yùn)流程次數(shù)是有限的，且補(bǔ)給操作區(qū)排包數(shù)量的限制，為了計劃垂直補(bǔ)給任務(wù)的執(zhí)行過程，引入波次的定義，將垂直補(bǔ)給任務(wù)分解為多個波次進(jìn)行調(diào)度。

一個垂直補(bǔ)給波次可以描述為一個五元組VB={P′,s,f,a,λ}, 其中P′∈P為本波次要運(yùn)送的補(bǔ)給貨包集合，s∈S為本波次的目標(biāo)補(bǔ)給船，f∈F為本波次的任務(wù)用直升機(jī)，a∈A為本波次使用的補(bǔ)給操作區(qū)，λ={(px,s)|px∈P′,s=sequence(px,P′)}是一組貨包到吊運(yùn)順序的映射，給出了本波次中貨包的補(bǔ)給順序[8]。

為了便于實際操作，每一波次的補(bǔ)給貨包需要在該波次開始吊運(yùn)前，排放在補(bǔ)給船的垂直補(bǔ)給操作區(qū)，一個波次中的補(bǔ)給貨包由一架直升機(jī)向一個補(bǔ)給目標(biāo)船進(jìn)行吊運(yùn)。所以，貨包的重量應(yīng)足式(6)和(7)的約束，同時，貨包的個數(shù)N應(yīng)符合約束

(8)

即一個波次中的貨包個數(shù)小于等于直升機(jī)任務(wù)用油量除以一次吊運(yùn)用油的下取整。

把垂直補(bǔ)給任務(wù)分配到垂直補(bǔ)給波次，得到垂直補(bǔ)給調(diào)度定義。對一個垂直補(bǔ)給任務(wù)進(jìn)行垂直補(bǔ)給調(diào)度指的是，將一個垂直補(bǔ)給任務(wù)VM合理的劃分成m個波次執(zhí)行，可表示為VS(VM)=[VB1,VB2,VB3,...,VBm]，最終完成補(bǔ)給任務(wù)。

垂直補(bǔ)給調(diào)度的優(yōu)化目標(biāo)是完成任務(wù)所需時間最短，可得到目標(biāo)函數(shù)如下

(9)

T(VBk)=N×Tv(si,fj)

(10)

其中,T(VBk)表示完成波次VB的用時，T(Rf(fj))表示直升機(jī)fj進(jìn)行一次加油的用時。

垂直補(bǔ)給任務(wù)的目標(biāo)補(bǔ)給船數(shù)量可設(shè)為1(單目標(biāo)任務(wù))，當(dāng)垂直補(bǔ)給任務(wù)的補(bǔ)給目標(biāo)船為多個時，可以把任務(wù)劃分為多個單目標(biāo)任務(wù)，然后對每個單目標(biāo)任務(wù)進(jìn)行調(diào)度，以下討論如何對單目標(biāo)任務(wù)進(jìn)行調(diào)度[9]。根據(jù)實際垂直補(bǔ)給作業(yè)情況，一般使用同一型號的直升機(jī)進(jìn)行作業(yè)，直升機(jī)的性能是統(tǒng)一的。所以垂直補(bǔ)給任務(wù)中對不同貨包執(zhí)行一次吊運(yùn)流程的用時相等，則根據(jù)式(8)和(10)可以將式(9)化簡為

Obj(VS)=min(n×Tv+m×T(Rf))

(11)

其中，n是垂直補(bǔ)給任務(wù)中貨包個數(shù)，Tv是執(zhí)行一次吊運(yùn)流程的用時，m是波次數(shù)量，T(Rf)是一次加油的用時。分析可知，調(diào)度優(yōu)化目標(biāo)就是在滿足每一波次的約束條件的同時,使波次數(shù)量m最小。

依據(jù)以上建立的垂直補(bǔ)給調(diào)度模型，本文提出兩種算法，即簡單調(diào)度算法和任務(wù)載重層次調(diào)度算法。

2 簡單調(diào)度算法

利用簡單調(diào)度算法進(jìn)行垂直補(bǔ)給調(diào)度需要滿足以下條件：1)補(bǔ)給貨包使用同一型號的貨筐打包；2)補(bǔ)給貨包重量小于直升機(jī)滿油任務(wù)載重。

其中直升機(jī)滿油任務(wù)載重指的是直升機(jī)裝滿油的時候可以一次吊運(yùn)貨包的重量。將式(7)取等號代入式(6)得

(12)

(13)

其中，C(a)表示操作區(qū)a的可以排包數(shù)量，由于補(bǔ)給任務(wù)滿足條件(a)，所以可以計算出垂直補(bǔ)給操作區(qū)最多排包的個數(shù)max(C(a))。式(12)表示，取直升機(jī)最多往返吊運(yùn)次數(shù)與操作區(qū)最多排包個數(shù)兩個值中的較小值，作為一個波次最多吊運(yùn)貨包的個數(shù)。

3 任務(wù)載重層次調(diào)度算法

根據(jù)直升機(jī)補(bǔ)給能力模型的分析可知，在一個補(bǔ)給波次中，隨著已完成吊運(yùn)次數(shù)的增多，直升機(jī)載重能力會由于直升機(jī)燃油重量的減少而增加[10]。為了提高垂直補(bǔ)給效率，利用直升機(jī)的可變的載重能力，可以提高補(bǔ)給貨包重量的最大上限。

利用任務(wù)載重層次調(diào)度算法進(jìn)行垂直補(bǔ)給調(diào)度需要滿足以下條件：1)補(bǔ)給貨包使用同一型號的貨筐打包；2)補(bǔ)給貨包重量小于直升機(jī)一次吊運(yùn)任務(wù)載重。

其中，一次吊運(yùn)任務(wù)載重指的是當(dāng)直升機(jī)的任務(wù)用油量還可以支持一次往返吊運(yùn)時，直升機(jī)可以吊運(yùn)貨包的重量。取Gu(fx) =Uv(si,fj) ，代入式(6)得

(14)

任務(wù)載重層次調(diào)度算法的主要思想是利用直升機(jī)的可變載重能力。將直升機(jī)的任務(wù)載重進(jìn)行分層，并把補(bǔ)給貨包依據(jù)重量進(jìn)行分類，再將補(bǔ)給貨包分配到各個波次[11]。任務(wù)載重層次調(diào)度算法分三個步驟，分別是任務(wù)載重分層，補(bǔ)給貨包分類以及分波次調(diào)度。

3.1 任務(wù)載重分層

將直升機(jī)任務(wù)載重能力分層，根據(jù)任務(wù)用直升機(jī)fj的自身屬性以及補(bǔ)給目標(biāo)船的相對距離，可得

Zy={Gt(fj)-Gr(fj)-y×Uv(si,fj)}

(15)

其中，Zy為任務(wù)載重層,依據(jù)式(17)計算可得到直升機(jī)fj的任務(wù)載重層次[Z1，Z2,…,ZZnom]，任務(wù)載重層次數(shù)量為Znom個，Znom∈Z+(Z+為正整數(shù))。

3.2 補(bǔ)給貨包分類

將垂直補(bǔ)給任務(wù)中包含的補(bǔ)給貨包按重量依據(jù)任務(wù)載重層次進(jìn)行分類，計算貨包px的層次類別公式：

Z(px)=Zy,Zy+1

(16)

px∈P，i∈[1,Znom],ZZnom+1=0

其中Z(px)表示補(bǔ)給貨包px的層次類型，Znom表示任務(wù)載重層次數(shù)量。依據(jù)式(16)可得到所有補(bǔ)給貨包所屬的任務(wù)載重層次Z(p)[12]。

3.3 分波次調(diào)度

將分類后的補(bǔ)給貨包分波次。用式(13)計算得到一個波次最多吊運(yùn)貨包的個數(shù)Bmax。任務(wù)載重層次調(diào)度算法流程如圖1。

輸入：任務(wù)載重層次一共為Znom層，一波次最多包含貨包個數(shù)Bmax，任務(wù)總貨包個數(shù)Nall，輸出：調(diào)度波次集合[VB1,VB2,VB3,…,VBm]。

圖1 調(diào)度算法流程圖

4 仿真實驗與分析

本文通過仿真實驗對比簡單調(diào)度算法和任務(wù)載重層次調(diào)度算法的補(bǔ)給效率。關(guān)于補(bǔ)給效率，涉及很多方面，包括時間、空間、人力、物力、利用率等，本文只是用時間性指標(biāo)作對比分析，采用E作為調(diào)度策略評價指標(biāo)，并用補(bǔ)給效率提高值Eimprove做進(jìn)一步的比較分析。

E=Wall/Tall

(17)

Eimprove=E2-E1

(18)

其中，E指的是一次調(diào)度策略的補(bǔ)給效率，Wall代表補(bǔ)給貨包總重量，Tall代表補(bǔ)給任務(wù)執(zhí)行用時；E1為簡單調(diào)度方法的補(bǔ)給效率，E2為任務(wù)載重層次調(diào)度方法的補(bǔ)給效率，Eimprove代表E2相對于E1的補(bǔ)給效率的提高值。

算法采用Matlab語言編寫，垂直補(bǔ)給任務(wù)算例中貨包的重量利用以下公式生成：

W(pa)=(Gf-Gr-Uv-Wmin)×rand(0,1)+Wmin

(19)

W(pb)=(Gf-Gr+Gs-Gfmax-Wmin)×rand(0,1)+Wmin

(20)

Wmin

(21)

其中，W(pa)是可以用任務(wù)載重層次調(diào)度算法進(jìn)行調(diào)度的垂直補(bǔ)給任務(wù)算例中的貨包重量，W(pb)是可以用簡單調(diào)度算法進(jìn)行調(diào)度的垂直補(bǔ)給任務(wù)算例中的貨包重量，Wmin為補(bǔ)給貨包重量下限。

圖2給出了兩種調(diào)度方法的補(bǔ)給效率。垂直補(bǔ)給任務(wù)算例中包含貨包的個數(shù)為100，分別用任務(wù)載重層次調(diào)度算法和簡單調(diào)度算法對100個不同的垂直補(bǔ)給任務(wù)進(jìn)行調(diào)度，根據(jù)式(17)計算出每次調(diào)度的補(bǔ)給效率。

圖2 兩種調(diào)度方法的補(bǔ)給效率

圖3給出了垂直補(bǔ)給任務(wù)中的貨包數(shù)量對兩種調(diào)度算法補(bǔ)給效率的影響。垂直補(bǔ)給任務(wù)中的貨包數(shù)量以10為增長率，從1取到300，對不同貨包數(shù)量的任務(wù)分別做任務(wù)載重層次調(diào)度100次，取100次調(diào)度的補(bǔ)給效率平均值，作為任務(wù)載重層次調(diào)度補(bǔ)給效率，以同樣方法計算簡單調(diào)度補(bǔ)給效率。從圖3給出的兩組實驗數(shù)據(jù)結(jié)果可以看出，當(dāng)任務(wù)貨包數(shù)量小于27(一波次最多吊運(yùn)貨包數(shù)量)的時候，任務(wù)載重層次調(diào)度的補(bǔ)給效率波動較大。這是由于在貨包數(shù)量小時，貨包的重量會制約分波次的數(shù)量，當(dāng)貨包重量很大時，由于需要多個波次，使補(bǔ)給效率出現(xiàn)波動。兩種調(diào)度方法的補(bǔ)給效率都會隨著貨包數(shù)量的增加而趨于平穩(wěn)。而且對任何貨包數(shù)量的垂直補(bǔ)給任務(wù)，任務(wù)載重層次調(diào)度的補(bǔ)給效率高于簡單調(diào)度的補(bǔ)給效率。

圖3 貨包數(shù)量對補(bǔ)給效率的影響

圖4給出了任務(wù)時間參數(shù)對兩種調(diào)度方法的補(bǔ)給效率的影響。任務(wù)時間參數(shù)包括一次往返吊運(yùn)用時和一次飛機(jī)加油用時。取兩組任務(wù)時間參數(shù)不同的垂直補(bǔ)給任務(wù)算例，每組包含100個不同的垂直補(bǔ)給任務(wù)，每個任務(wù)中包含貨包的個數(shù)為100。第1組垂直補(bǔ)給任務(wù)的一次往返吊運(yùn)用時5分鐘，一次加油用時15分鐘，第2組垂直補(bǔ)給任務(wù)的一次往返吊運(yùn)用時20分鐘，一次加油用時60分鐘。從圖4可以看出，兩種調(diào)度方法在任務(wù)時間參數(shù)取值較小時的補(bǔ)給效率都高于任務(wù)時間參數(shù)取值較大的補(bǔ)給效率。用式(18)計算，可得出任務(wù)載重層次調(diào)度和簡單調(diào)度的補(bǔ)給效率提高值Eimprove，對比發(fā)現(xiàn)在時間參數(shù)較小的情況下，補(bǔ)給效率提高值較大。

圖4 任務(wù)時間參數(shù)對補(bǔ)給效率的影響

圖5給出了一次往返吊運(yùn)用時和一次飛機(jī)加油用時分別對提高補(bǔ)給效率的影響。

圖5(a)為一次吊運(yùn)用時對兩種調(diào)度的補(bǔ)給效率的影響。進(jìn)行兩組實驗，第一組實驗垂直補(bǔ)給任務(wù)的加油用時參數(shù)取10分鐘，第二組加油用時參數(shù)取60分鐘。每組實驗中對垂直補(bǔ)給任務(wù)中一次吊運(yùn)用時取值從1分鐘到60分鐘，以3分鐘為增長率，對每一種吊運(yùn)用時參數(shù)取值做100次不同垂直補(bǔ)給任務(wù)的調(diào)度，取平均補(bǔ)給效率作為該種吊運(yùn)用時取值的補(bǔ)給效率。從圖5(a)可以看出隨著一次吊運(yùn)用時的增加，任務(wù)載重層次調(diào)度比簡單調(diào)度的補(bǔ)給效率提高值逐漸降低。圖5(b)給出了加油用時對兩種調(diào)度的補(bǔ)給效率的影響。進(jìn)行兩組實驗，第一組實驗垂直補(bǔ)給任務(wù)的一次吊運(yùn)用時參數(shù)取5分鐘，第二組吊運(yùn)用時參數(shù)取20分鐘。每組實驗中對垂直補(bǔ)給任務(wù)算例中一次加油用時取值從1分鐘到60分鐘，以3分鐘為增長率，對每一種加油用時參數(shù)取值做100次不同垂直補(bǔ)給任務(wù)的調(diào)度，取平均補(bǔ)給效率作為該種加油用時取值的補(bǔ)給效率。從圖5(b)可以看出隨著一次加油用時的增加，任務(wù)載重層次調(diào)度比簡單調(diào)度的補(bǔ)給效率提高值逐漸降低。

圖5(a) 吊運(yùn)用時及加油用時對補(bǔ)給效率的影響

圖5(b) 吊運(yùn)用時及加油用時對補(bǔ)給效率的影響

5 結(jié)束語

垂直補(bǔ)給是海上補(bǔ)給的重要手段，本文以垂直補(bǔ)給調(diào)度模型為出發(fā)點，提出了簡單調(diào)度算法和任務(wù)載重層次調(diào)度算法。任務(wù)載重層次調(diào)度方法是通過對直升機(jī)任務(wù)載重能力進(jìn)行劃分，提高補(bǔ)給貨包重量的上限，從而增加垂直補(bǔ)給效率。仿真實驗結(jié)果表明，在不同的任務(wù)補(bǔ)給貨包數(shù)量及時間參數(shù)條件下，任務(wù)載重層次調(diào)度方法明顯高于簡單調(diào)度方法的補(bǔ)給效率。