警戒海域反潜直升机优化调度研究

曾 斌, 姚 路, 李厚朴

(1. 海军工程大学管理工程与装备经济系, 湖北 武汉 430033;2. 海军工程大学导航工程系, 湖北 武汉 430033)

0 引 言

反潜战是海军作战的主要样式之一,是同对方潜艇兵力作斗争的海上作战。由于海洋环境复杂多变,潜艇具有非常强的隐蔽性,给反潜作战带来很大难度。随着无人水下航行器的发展,反潜的地位和作用更为重要,其中舰载反潜直升机由于其具有飞行速度快、搜潜范围广、隐蔽性好以及攻击效率高等优点,是海上舰艇编队对潜作战的主要兵力[1]。

从作战目标上看反潜分为护航反潜和区域反潜,本文主要针对区域反潜,区域反潜又细分为:① 反潜封锁区,使用阵地防潜器材和机动反潜兵力以阻止对方潜艇通过的海区;② 海洋反潜区,将海洋划分成若干个反潜区,各区编组一定的机动反潜兵力,分区负责反潜搜索和跟踪;③ 反潜警戒线,在沿海和岛屿附近的海岸声纳组网,以便提供反潜预警,并辅助反潜兵力进行反潜搜索。

近年来,反潜模式也由平台中心战向网络中心战转型[2],以此缩短反潜观察-调整-决策-行动闭环的时间。通过各类传感器等预警侦察手段,获得准确的战场态势;利用反潜机的快速机动能力,实施召唤式快速搜索[3]。

反潜警戒海域栅格化为若干监测区,在水下声纳网络[4-5]、巡逻反潜、侦察卫星、无线电侦听配合下,为重点海域(海上武器试验区、重要航道、海上保障基地、舰艇编队等)提供反潜预警;当发现水下可疑目标后向反潜指挥部门发出警报,警报中包含该目标随处区域以及反潜需求;指挥部门接到警报后,再调度我方反潜直升机到达该监测区实施搜潜、跟踪、攻击或驱逐,反潜机完成任务后返回待召。

随着无人水下航行器(unmanned underwater vehicle,UUV)的发展,反潜作战面临的挑战更加艰巨。蓝方往往频繁地从多处对红方警戒海域进行水下侵入,再加上水下环境复杂[6],水下预警系统也存在误报的情况,而反潜直升机资源数量有限,传统的就近派遣策略无法满足这种多次数多分散地点的反潜需求。因此，优化的调度策略更显重要。

直升机反潜是当前军事领域研究热点问题之一。例如,文献[7]利用贝叶斯网络推理潜艇意图。文献[8]提出了适合于双机搜潜的“前堵后追”法。文献[9]提出了一种直升机协同搜潜的阵型最优化方法。文献[10]研究了联合反潜作战中反潜机的搜索模式问题。文献[11]将搜索海域栅格化,给出了舰载直升机吊放声纳区域反潜搜索算法。文献[12]研究了反潜机应召搜索时声纳浮标阵的评估模型。文献[13]从协同反潜角度研究了对潜艇的探测模型。以上文献主要研究反潜直升机起飞后的搜潜策略,但反映出反潜作战的背景特征,如潜艇位置的随机性和搜索海域栅格化等思路,对本文具有较大启发。

文献[14]以提高覆盖率为目标,建立了多舰联合搜潜的概率方程,并提出基于概率距离函数的优化算法来求解。文献[15]研究了濒海战斗舰的反潜规划问题。文献[16]研究了应召反潜中,水面舰艇和反潜机协同反潜中拖曳声纳和反潜直升机的部署问题。文献[17]利用无人艇执行搜潜任务,提出了改进的遗传算法来提高累积探测概率。文献[18]研究了反潜直升机的优化攻击地点。文献[19]设计了反潜机的探测距离估算模型。以上文献在反潜监测概率和优化部署方面对本文具有一定启发。

另外,国外军事研究人员,特别是美国海军也针对反潜直升机的作战使用展开了相关研究。文献[20]设计了一个上下文驱动的决策支持工具来解决反潜调度和规划问题,提出了一个隐马尔可夫模型来对反潜资源和搜索规划建模,并提出了二阶段算法(进化算法和拍卖算法)来求解。文献[21-22]利用零和博弈对反潜作战建模,利用线性规划算法计算反潜资源(反潜机或舰艇)的优化部署问题。文献[23]利用非零和网络阻断博弈对区域反潜建模,并采用强Stackelberg均衡策略解决了反潜资源的分配问题。文献[24-25]以提高覆盖率为目标,研究了反潜规划问题,并运用解析法建立了反潜责任区防潜兵力的配置模型。文献[26]研究了带吊放声纳的反潜直升机搜索模式和吊放频率。文献[27]进一步研究了反潜直升机搜索策略以及油料和载荷的优化配置问题。但现有文献缺少从水下网络中心战角度研究多监测区-多反潜机的调度问题。

本文的研究目标是:把警戒海域划分为多个监测区,通过历史数据或经验预估监测区的报警率和期望搜潜时间,在此基础上,计算得到优化的多反潜直升机部署地点以及分派策略(优先顺序),从而达到最大覆盖警戒海域的目的。

多监测区-多反潜机调度中存在的两个问题增加了优化过程的复杂性:① 需要综合考虑不同类型反潜直升机的调度,不同类型反潜直升机各有自己的优缺点,如何在反潜作战中相互配合,扬其所长,避其所短,是调度模型的一个重点研究目标;② 各反潜直升机的负载平衡问题,如果调度(部署和分派策略)不当,将导致某一架或几架直升机工作负载过大,这会加大飞行员的疲劳度,同时也会增加飞机的故障率,从而降低整个反潜系统的可用率。

因此,本文的主要创新点和贡献是从水下网络中心战的角度出发,为了达到最大覆盖警戒海域的研究目标,特别针对以上两个问题,提出反潜直升机部署和调度模型及求解算法。在技术上借鉴了超立方体排队模型来研究反潜调度问题,该模型主要用于分析应急服务系统的最大覆盖问题,在紧急医疗设施[28]和急救车部署[29-30]方面取得了较好的性能。但相关研究没有考虑不确定情况下,多优先级任务同时出现时不同服务单元的配置问题,这也是本文的研究难点。

本文分两个阶段进行优化：第1阶段建立超立方体反潜调度排队模型和求解算法,以输入的报警率作为事件到达率,期望响应时间为平均服务时间,输出校正系数和直升机繁忙概率等统计结果；第2阶段建立反潜调度规划模型,以第1阶段输出作为规划模型的输入参数,从而得到反潜直升机的部署及分派策略。

1 排队模型及求解算法

超立方体排队模型是对常规排队模型的扩展,适用于应急反应系统的概率选址,反映了服务器与客户需求之间更为复杂的分配关系,对多服务器排队系统进行了扩展,增加了服务器状态空间的描述,能够更为精确地刻画排队系统的时空复杂性[31]。某一时间段内服务器可能处于忙(1)或闲(0)两种状态,系统中多个服务器的状态组合构成了系统状态空间。例如状态{1,1,0}表达了一个三服务器系统,其中1号服务器空闲,2号和3号服务器繁忙,从中可以看出一个三服务器系统的状态空间可以由立方体的8个顶点表示,如果系统中服务器数量多于3个,则称之为超立方体。如果给定排队系统参数,例如服务器数量、分管区域数量(客户数量)、客户请求到达率以及服务器的平均服务时间等,利用超立方体排队模型可以计算稳态状态下系统的一些关键性能指标,包括服务器的繁忙概率、工作强度以及服务器与客户之间的分配概率等。

反潜直升机数量有限,在警戒海域执行大规模搜潜任务时不能处于随时可用状态,所以计算其繁忙概率对于应召搜潜调度而言非常重要。另外直升机执行反潜任务时存在协作关系,因此本文还需要计算校正系数来补偿排队系统中服务器无关性的假设。

1.1 参数描述

由于排队模型中引用参数较多,在这里首先统一进行描述。

nA(nB)为系统中A类型(B类型)反潜机数量，nA+nB=n;

LA(LB)为A类型(B类型)反潜机候选部署地点集合,LA+LB=L,包括多个地点l∈L;

Z为警戒海域内监测网格区集合,当预警系统发现可疑目标后,向反潜调度系统发出包括目标大致所在区域(监测区编号)的警报,由调度系统通知反潜机前往该区域实施搜潜,包括多个监测区z∈Z;

T为报警类别集合,本文把警报类别分为4类:① 只能分配给A型机处理的警报TA;② 如果A型机都忙时,可以分配给B型机处理的警报TAB,即优先要求A类型机;③ 如果B型机都忙时,可以分配给A型机处理的警报TBA;④ 只能分配给B型机处理的警报TB,TA、TB、TAB、TBA⊆T;

λt为类型为t的警报发生率,t∈T;

λtz为在第z监测区发出的类型为t的警报发生率,λt=∑z∈Zλtz,z∈Z,t∈T;

λ为系统级所有警报发生率,λ=∑z∈Z,t∈Tλtz;

τAlzt(τBlzt)为l地点的A型机(B型机)执行z区t类别警报任务的期望响应时间(从收到警报到抵达目标区域z所花费的时间);

τA(τB)为系统级A型机(B型机)的平均响应时间;

θt为t类别警报对响应时间指标的要求,本文以规定响应时间内得到处理的t类别警报数量比例来作为衡量指标;

ρA(ρB)为A型机(B型机)的工作强度;

pAl(pBl)为部署在l地点的A型机(B型机)的繁忙概率;

pA(pB)为系统级A型机(B型机)的繁忙概率,pA=(∑l∈LApAl)/nA;

aAztk(aBztk)为A型机(B型机)的排序调度表,表示当z区域发出t类别警报时,作为第k顺位分配的反潜机地点,如果t∈TA∪TAB,k=1,2， …,nA,如果t∈TBA,则k=nB+1,nB+2,…,nB+nA;

dAlztk(dBlztk)为A型机(B型机)的分配概率,表示当z区域发出t类别警报时,作为第k顺位的l地点A型机(B型机)被分派到处理该警报的概率;

PAk(PBk)为由于k个A型机(B型机)的繁忙,造成警报无法处理的概率,即损失率;

RAlzt(RBlzt)为表示当z区域发出t类别警报时,l地点的A型机(B型机)能够在规定响应时间(与警报类别有关)内到达z区域执行搜潜任务的概率;

QA(nA,ρA,k)或QB(nB,ρB,k)为超立方体模型的校正系数,可看作输入参数为反潜机数量nA(nB),反潜机工作强度ρA(ρB)以及派遣顺位k的函数。

本文假设z区域t类型警报的到达率服从参数为λtz的泊松分布,如果某警报需要多架反潜机协同反潜,可以发出多个虚拟警报来处理。

1.2 排队模型

为了避免重复,本文中主要描述A型机的数学模型,B型机的模型与A型机相同。

1.2.1 校正系数的计算模型

当出现警报时,在前面连续j架反潜机都繁忙,第k+1顺位的反潜机空闲的概率是在排队论服务器无关性假设下计算得到的,在反潜系统中,反潜机的调度往往存在协作关系,因此需要在模型中加入无关性校正系数QA(nA,ρA,k)来修正[32]。设PAnA表示所有的nA架A型反潜机繁忙的概率,PA0表示没有A型机繁忙,即所有A型机空闲的概率,设k=0,1,…,nA-1,则有

QA(nA,ρA,k)=

(1)

1.2.2 分配概率的计算模型

在排队模型中,如果要计算服务器的繁忙概率,必须先计算服务器-客户对的分配概率。在本文中,服务器表示为反潜机,客户可表示为监测区,所以分配概率既是dAlztk或dBlztk的值。分配概率与排序调度表aztk有关,如果a1A2=3,表示1号区域发出只能由A型机反潜的警报时,位于3号地点的反潜机将作为第2顺位被分配去处理。另外分配概率与警报类别有关,因为对于TBA类别的警报,必须要B型机都繁忙时才轮到分配A型机去处理,所以对于处理TA∪TAB类别的警报和处理TBA类别的警报,其分配概率的计算是不同的。特别是当t∈TB时,因为该类警报只能由B型机处理,所以这时dAlztk=0。综上所述,dAlztk的计算公式分以下两种情况:

(1)如果t∈TA∪TAB,z∈Z,k=1,2,…,nA,l∈LA,则

(2)

(2)如果t∈TBA,z∈Z,k=nB+1,nB+2,…,nB+nA,l∈LA,则

(3)

1.2.3 繁忙概率的计算模型

地点l的A型机繁忙概率pAl计算公式为

(4)

式中,rAl表示地点l的A型机分配执行搜索任务的频率,计算公式为

(5)

式(5)中第二项表示地点l的A型机分派给TBA类别警报任务的频率,同第1.2.2节分派概率的计算,加入PBnB项的原因是,在t∈TBA时,所有的B型机都繁忙时,才只好找A型机调度。而且这时A型机的分派优先级顺序都排在B型机后面,所以优先序号j从nB+1开始。

1.2.4 平均响应时间的计算模型

平均响应时间的计算公式如下:

(6)

式中,平均响应时间是单架机响应时间τAlzt与归一化的分派概率dAlztk/(1-PAnA)的乘积,乘积结果再用警报到达频率(λtz/λ)加权。

1.3 排队模型的求解算法

由于稳态时第1.2节的排队模型无法求得精确解,只能采用近似算法迭代计算。近似算法步骤如下。

算法输入参数:①λtz,警报发生率;②τAlzt,l地点的A型机响应时间;③aAztk,可由第2节规划模型求解算法输入。

初始化:初始化平均响应时间为

(7)

按埃尔朗损失率公式初始化所有A型机繁忙的概率,即

(8)

式中,A型机初始空闲概率PA0,0为

(9)

设Lz为距离监测区z最近的反潜机地点集合,则反潜机的初始繁忙概率为

(10)

迭代计数器h设为0。

步骤 1利用上一次迭代计算的平均服务时间τA,h-1(如果为第1次迭代,则利用初始化的τA,0)更新损失率,计算公式为

(11)

式中，A型机空闲概率为

(12)

步骤 2设k=0,1,…,nA-1,按式(1)计算本次迭代的校正系数QA,h(nA,ρA,h,k),其中工作强度ρA,h=λτA,h-1/nA。

步骤 3按式(2)和式(3)计算本次迭代h的分配概率dAlztk,h,需要的参数中繁忙概率使用上一迭代的计算值,校正系数取步骤2的计算结果。

步骤 4按式(6)计算本次迭代的平均响应时间τA,h,需要的参数中分派概率使用步骤4的计算结果,损失率使用步骤1的计算结果。

步骤 5按式(4)和式(5)计算当前h迭代时的反潜机繁忙概率pAl,h,需要的参数中优先级排序的繁忙概率使用上一迭代的计算值,校正系数取步骤2的计算结果。

步骤 6若对于所有地点的A类反潜机,其前后两次迭代的计算结果大于某一阈值ε,即|pAl,h-pAl,h-1|>ε,其中l∈LA,则跳转步骤1继续迭代,否则返回繁忙概率和校正系数。

2 规划模型

反潜机调度规划模型的目标函数是最大化规定时间内完成高优先级反潜任务的数量比例,并且在此同时实现对低优先级警报的一定(给定阈值内)覆盖率,这样折中实现对所有警报的及时处理。

2.1 排队模型相关参数的定义

排队模型近似求解算法的输出用作规划模型的输入参数。规划模型目标函数和约束条件中用到的两个系数与超立方体排队模型输出相关。一个系数捕捉系统分派策略满足时限要求的性能,本文称之为及时率;另一个系数捕捉系统的工作负载。

及时率系数cAlztk或cBlztk表示当z区域发出t类别警报时,作为第k顺位的l地点的A型机(B型机)能够在规定响应时间(与警报类别有关)内到达z区域的数量比例,为反映监测区的优先级,本文使用监测区z的警报率(λtz/λt)对及时率系数加权。假设同一类型反潜机的繁忙概率相同时,及时率的计算类似于分派概率,其计算公式为

(1)如果t∈TA∪TAB,z∈Z,k=1,2,…,nA,l∈LA,则

cAlztk=(λtz/λt)RAlzt[QA(nA,ρA,k)(1-pA)(pA)k-1]

(13)

(2)如果t∈TBA,z∈Z,k=nB+1,nB+2,…,nB+nA,l∈LA,则

cAlztk=(λtz/λt)RAlztPBnB[QA(nA,ρA,k)(1-pA)(pA)k-1]

(14)

式中,校正系数与A型机繁忙概率pA都为超立方体排队模型的计算结果。及时率系数计算过程中考虑了两个不确定因素的影响:① 在校正系数补偿下反潜机可用性的不确定性,比地点l更优先的k个反潜机繁忙时至少有一个反潜机空闲的概率为(1-pA)(pA)k-1,再乘以校正系数QA,表示有k-1架反潜机优先于l调度,但l仍然被调度的概率;②RAlzt表示飞行和搜潜时间的不确定性。

同样地,负载系数gAlztk或gBlztk,分别表示A型机或B型机的工作负载,A型机负载系数计算公式为

(1)如果t∈TA∪TAB,z∈Z,k=1,2,…,nA,l∈LA,则

gAlztk=(λtz/λt)τAlzt[QA(nA,ρA,k)(1-pA)(pA)k-1]

(15)

(2)如果t∈TBA,z∈Z,k=nB+1,nB+2,…,nB+nA,l∈LA,则

gAlztk=(λtz/λt)τAlztPBnB[QA(nA,ρA,k)(1-pA)(pA)k-1]

(16)

式中,τAlzt表示l地点的A型机执行z区t类别警报任务的期望响应(服务)时间。B型机计算公式类似,负载系数用于平衡同一类型反潜机的工作负载。

2.2 规划模型的定义

首先定义反潜规划模型的决策变量,为了完成反潜调度的两个主要目标,反潜规划模型相应也包含两套决策变量。布尔变量hAl和hBl决定A型机和B型机的部署地点,如果hAl=1,表示有A型机部署在l地点(l∈LA),否则hAl为0。hBl与hAl相似,如果hBl=1,表示有B型机部署在l地点(l∈LB),否则hBl为0。

第二套决策变量为mAlztk和mBlztk也为布尔变量,表示A型机和B型机分派至监测区的排序调度表,与aAztk或aBztk可以相互转化,一方面用于表示对于不同类别警报的分派顺序,例如TA类别警报任务只能由A型机执行,TAB类别警报任务先由A型机执行,如果没有A型机空闲时才交由B型机执行,TB和TBA也是类似。另外,也可以表示当发生某警报时,同一类型反潜机内部的分派顺序,如果mAlztk=1,表示当z区域发出t类别警报时,地点l的A型机作为第k顺位分配,如果t∈TA∪TAB,k=1,2,…,nA,如果t∈TBA,则k=nB+1,nB+2， …,nB+nA;其他情况时mAlztk=0。mBlztk的设计与mAlztk相似。

以上决策变量的设计把反潜调度规划转化为二元线性规划模型,目标函数为

(17)

该目标函数的目的是最大化高优先级警报TA的期望覆盖率,在反潜调度规划模型中,只有A型机可以执行TA警报任务。

约束关系如下:

(18)

nB+1,nB+2,…,nB+nA

(19)

(20)

k=nA+1,k=nA+2,…,nA+nB

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

mAlztk≤hAl,∀l∈LA,z∈Z,t∈TA∪TAB,

k=1,2,…,nA

(31)

mAlztk≤hAl,∀l∈LA,z∈Z,t∈TBA,k=nB+1,

nB+2,…,nB+nA

(32)

mBlztk≤hBl,∀l∈LB,z∈Z,t∈TB∪TBA,

k=1,2，…,nB

(33)

mmlztk≤hBl,∀l∈LB,z∈Z,t∈TAB,k=nA+1,

nA+2,…,nA+nB

(34)

(35)

(36)

(37)

(38)

式(18)表示对于警报t∈TA∪TAB,在排序调度表中同一顺位只能选择一架A型机执行。式(19)表示对于警报t∈TBA,首先分派B型机执行,如果B型机都繁忙才分派给A型机,而且在排序调度表中同一优先级顺位只能选择一架A型机执行。式(20)和式(21)与式(18)和式(19)表示的意义相同,但针对的是B型机。式(22)～式(25)表示某反潜机l不能同时是某监测区z的多个顺位分派机,比如不能既是z的第1顺位分派机又是z的第2顺位分派机。式(26)～式(28)保证低优先级的警报(TAB,TBA,TB)的期望覆盖率大于某个阈值θt。式(29)和式(30)为反潜机的数量约束。式(31)～式(34)表示只有已部署到指定地点的反潜机才能被调度。式(35)和式(36)约束同一型号反潜机之间负载平衡,即负载差不高于某一阈值δA(δB)。式(37)和式(38)约束反潜机的分派监测区相邻,即如果z的邻居z′分派给某反潜机l分管,则z才能被该反潜机分管。

本文中,由式(18)～式(34)构成的模型为基本调度模型,基本模型增加了式(35)和式(36)后为负载平衡模型,基本模型增加了式(37)和式(38)后增加了分管区域相邻的约束。所有约束构成了加强模型。另外假设反潜机在我方警戒海域可以就近补充油料,所以约束关系中没有包括油料限制。

3 调度算法及应用场景

由于排队模型求解算法中反潜机的繁忙概率与分派策略aAztk(aBztk)有关,而aAztk(aBztk)可以通过mAlztk(mBlztk)转换得到,规划模型又需要排队模型中的校正系数和繁忙概率,所以本文设计了迭代算法求解规划模型,其计算步骤如下。

步骤 1初始化;

步骤 1.1利用“分配最近空闲反潜机”策略初始化初始排序调度表aAztk(aBztk);

步骤 1.2调用第1.3节排队模型求解算法得到繁忙概率和校正系数;

步骤 1.3设置初始不平衡容忍度δ0=1;

步骤 1.4迭代次数i设为1;

步骤 2利用上次迭代(或初始阶段)生成的繁忙概率和校正系数求解规划模型,得到新的排序调度表aAztk,i;

步骤 3利用新的排序调度表aAztk,i,调用排队模型求解算法,得到新的繁忙概率pA,i和校正系数Qi,设置δA,i=1/2(maxpA,i-minpA,i);

步骤 4算法包括2个迭代停止条件。第1个停止条件为式(33)和式(34)无法满足,这时再减少不平衡容忍度δ会导致无法得到可行解;第2个停止条件为繁忙概率小于某个阈值。如果算法停止条件都没有达到,增加迭代次数i并跳转至步骤2;

步骤 5返回最新迭代计算的排序调度表和反潜机部署地点。

具体过程如图1所示。

图1 栅格化反潜警戒区示意图Fig.1 Schematic diagram of grid antisubmarine warning area

本算法的应用时机为需要对某海域布防警戒前,具体应用步骤描述如下。

步骤 1类似图1,把需要布防海域栅格化为若干监测区z,同时筛选出适合部署反潜直升机的候选地点l;

步骤 2通过历史数据、地点重要程度或敌方威胁程度预估各个监测区的报警率λtz,并根据l和z之间距离和反潜机速度估算出期望响应时间τAlzt(或τBlzt),如果可能也可以估计期望响应时间的不确定性参数RAlzt或RBlzt(缺省为1),θt根据相关条例推导指定;

步骤 3步骤1和步骤2的结果作为调度算法输入参数进行迭代计算。由于调度算法的步骤1需要计算第2.2节的规划模型(二元线性规划),而该规划模型中用到的及时率和工作负载2个系数需要用到排队模型输出的繁忙概率和校正系数,所以需要嵌入调用第1.3节的排队模型求解算法;

步骤 4当调度算法退出时,生成两个决策变量的计算结果,反潜机的部署地点(hAl和hBl)以及排序调度表(mAlztk和mBlztk)。

指挥人员可以以本算法结果作为决策支持建议,在推荐地点部署反潜机搭载平台(驱逐舰或护卫舰)。如果某监测区出现威胁目标时,能够以排序调度表作为调度策略基础方案,按优先级次序(如果高优先级直升机已执行任务,则依次派遣低优先级直升机)派遣对应反潜机执行对应任务。

4 仿真实验

本文仿真背景案例采用了类似图1的栅格化警戒海域背景,整个海域分为85个监测区,其中32个区域可以作为反潜直升机搭载平台的候选部署地点,假设有10架A类机和4架B类机可供调度。从安全角度考虑,本文不讨论警戒海域和反潜机的具体参数。

在参数设置方面,期望响应时间τAlzt以小时为单位,按反潜机的部署地点l和报警区域z之间的距离除以反潜机的速度计算。τBlzt的计算与A类机类似,但考虑B类机可能采取双机协同,且综合性能较弱,所以其计算得到的响应时间乘以2作为惩罚因子。警报类别的概率分布为:TA为75%,TAB为20%,TBA为5%,仿真中不生成TB警报。系统级所有警报发生率λ=3 h,每一个监测区域的警报发生率相等。

当前算法在联想笔记本上即可运行,CPU为四核Intel-i5,基础频率1.6 GHZ,内存8 G,算法在VS2012下用C++实现,规划求解部分调用IBM ILOG CPLEX 12.9。容忍度设置为0.01时,平均运行时间统计如下:基本模型耗时约0.6 min,负载平衡模型耗时约6.2 min,加强模型耗时约11.3 min,3个规划模型中调用排队算法更新繁忙概率和校正系数的时间分别为0.1 min、0.65 min和0.6 min。

图2和图3为部署了全部10架A型机和4架B型机(B型机可以为双机协同)时,在迭代调度算法中调用排队模型求解算法得到的繁忙概率pAl(pBl),其中,l表示10架A型机和4架B型机的部署地点。图2中A型机的繁忙概率最低为0.052,最高为0.105,平均为0.075;图3中B型机的繁忙概率最低为0.225,最高为0.357,平均为0.310,所有机型的繁忙概率不超过其平均值的5%。

图2 不同部署地点的A型机繁忙概率Fig.2 Busy probability of type A aircraft in different deployment locations

图3 不同部署地点的B型机繁忙概率Fig.3 Busy probability of type B aircraft in different deployment locations

图4和图5为排队模型求解算法得到的不同派遣顺位对应的校正系数QA(nA,ρA,k)和QB(nB,ρB,k),其中nA=10,nB=4,ρA和ρB的计算见排队模型求解算法的步骤2。

图4 A型机不同派遣顺位对应的校正系数Fig.4 Correction coefficient of different dispatch order for type A aircraft

图5 B型机不同派遣顺位对应的校正系数Fig.5 Correction coefficient of different dispatch order for type B aircraft

从图4和图5中可以看出QA(nA,ρA,0)=QB(nB,ρB,0)=1,这是因为当所有反潜机空闲时,能够派遣反潜机的概率为1。

图6统计了TA类别警报发出后,分派A型机处理时得到的目标函数值,即TA警报的覆盖率。在这个仿真实验中,B型机数量固定为4,即nB=4,改变A型机数量nA,从中分析当增加或减少A型机数量时,调度算法的性能变化情况,除此以外,图6中还对警报发生率不同时,随A型机数量变化的算法性能进行了敏感性分析。

图6 不同警报发生率下的目标函数值敏感性分析Fig.6 Sensitivity analysis of objective function value under different alarm rates

图6的结果可以用于帮助指挥人员判别需要多少数量的A型机才能达到指定的监测覆盖率指标。例如,当警报发生率λ介于2.5和3.5之间时,如果需要在警戒海域达到90%以上的警报覆盖率,则需要部署6架A型机即可满足要求,但如果想在同样的警报发生率情况下达到95%的覆盖率,A型机数量至少需要达到9架。而且从图6中还可以发现随着A型机数量增加,目标函数值的增加逐渐减缓。例如当λ=3.0时,A型机数量从2架增加到5架时,覆盖性能呈现一个较大的增长,从53%增加到了90%,而当A型机数量从8架增加到10架时,性能增长幅度较小,从94%增加到95%。

下面比较本文提出的优化算法与常规“就近派遣”策略的性能。当有警报发出后,就近派遣策略按离警报区域的距离由近到远调度,很明显该策略的响应时间最短,因此覆盖率也相应最大。但警报率较高时可能导致反潜机处于繁忙状态,这时需要根据全局态势从长考虑,合理的做法可能是预留最近的反潜机以备更高等级的警报。其中就近派遣策略的实现步骤如下。

步骤 1根据候选部署点与85个监测区之间的平均距离,利用分簇排序方法选择了A型机和B型机的部署点;

步骤 2按照监测区与部署点的距离远近生成排序调度表;

步骤 3在步骤1和步骤2的基础上,设置2套决策变量hAl、hBl、mAlztk和mBlztk的相应值为1,按式(7)计算覆盖率。

图7显示了优化算法与就近策略的警报覆盖率性能指标,其中B型机数量设置为4,警报率λ=3,如图7所示,就近派遣策略也能取得不错的性能,但总体上优化算法比就近派遣策略占优,在反潜机数量较小时(nB=4,nA=2)就近派遣策略与优化算法性能相同。进一步比较当警报率变化时,从λ=1增加到10,优化算法与就近派遣的性能差异。

图7 就近派遣与优化算法的性能对比(不同A型机数量)Fig.7 Performance comparison between the closest dispatch policy and optimal algorithm (different number of type A aircraft)

同样地就近派遣策略的警报覆盖率也较高,图8中可以看出优化算法最大高于就近派遣1.71%,仿真中参数设置为nB=4,nA=10。尽管就近派遣策略在警报覆盖率上与优化算法的差异不大,但优化算法的优势在于构建排序调度表时避免了局部反潜机过忙的影响。例如在某些情况下(指挥人员凭经验难以识别),派遣较远的反潜机与就近派遣相比,可以在整体反潜性能不变的情况下,降低反潜机的繁忙率,从而延长整个反潜机系统的生命周期。同时,通过把任务尽可能平均分配到所有反潜机上,如图2和图3所示,可以提高反潜机的空闲率,从而较少警报区域的等待时间,最终增加了警报的期望覆盖率。而且优化算法能够产生一个合理的排序调度表,可以帮助指挥人员判别合适的预备反潜机。

图8 就近派遣与优化算法的性能(λ不同)Fig.8 Performance comparison between the closest dispatch policy and optimal algorithm (different λ)

5 结 论

当海上传感器平台监测到水下可疑目标并发出警报后,如何快速有效地派遣反潜机至警报区域是决定反潜成败的关键问题,如果响应过慢则会丢失目标而贻误战机。为此,本文提出了一个二元整数规划模型及相应求解算法,其主要目标包括:① 解决目前两种主力反潜直升机的优化部署问题;② 构造排序调度表以解决反潜机的分派问题。其中,如何利用有限的反潜机资源警戒大范围海域是本文的一个难点,这也是应召反潜的重点问题。为此,建立了一个排队模型计算直升机繁忙概率和无关性校正系数,以此作为规划模型的输入参数,以便更加准确地反映当前态势,提高规划模型的精确度。

尽管该模型以两种反潜机为例进行说明,但可以利用相似方法扩展到多类型反潜机优化调度上。当多处同时发现目标需要派遣多机反潜时,也可以考虑应用本文研究成果进行进一步扩展。另外,警报类别或优先级的划分对调度模型的性能影响较大,尽管当前有非常多的有关类别或优先级计算的模型和算法,但尚缺乏反潜领域应用的相关研究,这也是下一步工作的重点方向。