直升机垂直补给的任务载重层次调度算法

田立军

(中国人民解放军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 结束语

垂直补给是海上补给的重要手段，本文以垂直补给调度模型为出发点，提出了简单调度算法和任务载重层次调度算法。任务载重层次调度方法是通过对直升机任务载重能力进行划分，提高补给货包重量的上限，从而增加垂直补给效率。仿真实验结果表明，在不同的任务补给货包数量及时间参数条件下，任务载重层次调度方法明显高于简单调度方法的补给效率。