直升機垂直補給的任務載重層次調度算法

田立軍

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

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

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

1 垂直補給調度模型

垂直補給調度是指將任務分配至資源的過程，一個垂直補給任務可以描述為一個四元組VM=(P，S，F，A)，其中，P為補給貨包集合，S為補給目標船集合，F為任務用直升機集合，A為垂直補給操作區集合。

將補給貨包運往補給目標船就是一項任務，而直升機和操作區是可以利用的資源，將補給貨包分配到操作區和直升機并運往目標補給船，就是垂直補給調度[4]。由于直升機以及垂直補給操作區是垂直補給流程中的關鍵因素，為了更好地描述垂直補給調度模型，首先需要給出直升機補給能力模型，以及垂直補給操作區模型。

1.1 直升機補給能力模型

直升機補給能力模型描述的是直升機在參與垂直補給作業過程中的運載能力，工作方式以及相關制約因素[5]。

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

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) 表示任何時刻直升機fj的總重量 ，Gh(fj) 表示直升機fj的空機重量，Gl(fj) 表示直升機fj的任務載重量，Gf(fj) 表示直升機fj的燃油重量，Gp(fj)表示直升機fj的人員重量，Ge(fj)表示直升機fj裝備的重量；Gt(fj)表示直升機fj的最大起飛重量；Gs(fj)表示直升機fj的安全余油標準量，Gu(fj) 表示直升機fj的任務用油量；Gfmax(fj)表示直升機fj的最大載油量。

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

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

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

(5)

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

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

(6)

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

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

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

(7)

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

1.2 垂直補給操作區排放模型

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

1.3 垂直補給調度模型

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

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

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

(8)

即一個波次中的貨包個數小于等于直升機任務用油量除以一次吊運用油的下取整。

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

垂直補給調度的優化目標是完成任務所需時間最短，可得到目標函數如下

(9)

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

(10)

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

垂直補給任務的目標補給船數量可設為1(單目標任務)，當垂直補給任務的補給目標船為多個時，可以把任務劃分為多個單目標任務，然后對每個單目標任務進行調度，以下討論如何對單目標任務進行調度[9]。根據實際垂直補給作業情況，一般使用同一型號的直升機進行作業，直升機的性能是統一的。所以垂直補給任務中對不同貨包執行一次吊運流程的用時相等，則根據式(8)和(10)可以將式(9)化簡為

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

(11)

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

依據以上建立的垂直補給調度模型，本文提出兩種算法，即簡單調度算法和任務載重層次調度算法。

2 簡單調度算法

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

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

(12)

(13)

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

3 任務載重層次調度算法

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

利用任務載重層次調度算法進行垂直補給調度需要滿足以下條件：1)補給貨包使用同一型號的貨筐打包；2)補給貨包重量小于直升機一次吊運任務載重。

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

(14)

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

3.1 任務載重分層

將直升機任務載重能力分層，根據任務用直升機fj的自身屬性以及補給目標船的相對距離，可得

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

(15)

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

3.2 補給貨包分類

將垂直補給任務中包含的補給貨包按重量依據任務載重層次進行分類，計算貨包px的層次類別公式：

Z(px)=Zy,Zy+1

(16)

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

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

3.3 分波次調度

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

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

圖1 調度算法流程圖

4 仿真實驗與分析

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

E=Wall/Tall

(17)

Eimprove=E2-E1

(18)

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

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

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(pb)是可以用簡單調度算法進行調度的垂直補給任務算例中的貨包重量，Wmin為補給貨包重量下限。

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

圖2 兩種調度方法的補給效率

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

圖3 貨包數量對補給效率的影響

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

圖4 任務時間參數對補給效率的影響

圖5給出了一次往返吊運用時和一次飛機加油用時分別對提高補給效率的影響。

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

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

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

5 結束語

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