随机多需求环境下远程中继保障网络设计优化问题建模与求解

2021-07-05肖依永王宏宇

系统工程与电子技术 2021年7期

杨培, 肖依永, 王宏宇

(1. 北京航空航天大学可靠性与系统工程学院, 北京 100191;2. 中国人民解放军陆军航空兵学院, 北京 101116)

0 引言

现代信息化战争具有作战强度高、节奏快、持续时间短、战场环境复杂多变等特点,面对近岸岛屿联合作战中的保障问题,其保障点既涉及基地级陆地保障点,也涉及中继级海上保障点,保障网络更为复杂、灵活。面对这样的保障网络,中继保障点的选择以及保障路线的优化对实施及时保障响应起到非常重要的作用。国内学者对近岸岛屿联合作战保障问题的研究主要集中在人工岛屿建设、海域保护战略、船艇装备保障力量部署方针、以及岛屿文化安全现状分析与对策方面。任兆瑞从岛上进攻装备保障面临的难点着手分析,从跨海作战、装备物资供应困难、装备力量易受攻击了个难点进行分析,提出了进攻作战装备保障的主要对策[1]。段祺麟从文化和安全现状问题对东海的局势做了一个概括分析[2]。刘增勇从约束满足问题的理论方法入手,实现近岸岛屿联合作战中船艇装备保障力量的部署优化[3]。除了上述关于保障理论问题的研究,以任骥为代表的国内学者研究了战场不确定环境下的后勤物资供应网络设计优化问题,考虑了供应和需求的不确定性,建立了优化问题的整数规划模型,并开发了基于拉格朗日松弛的启发式求解算法[4]。童声针对执行战场物资供应任务之前,不确定环境下的战场物资供应任务规划问题进行研究,并建立了相应的不确定规划模型,引入一种新的启发式算法——蜂群算法[5]。国内学者主要是针对一个大范围的作战保障问题进行整体的规划部署。在面对于海上作战问题的研究,目前有较多的作战理论方针政策进行战略性指导,缺乏一定的数学模型作为技术支撑。针对作战的后勤保障问题,20世纪80年代末,以美国为首的西方国家率先提出了以“配送式后勤”为主要标志的军事后勤变革理念[6-8]。1990年开始的海湾战争中,美军就开始实践配送式后勤保障理论,但受限于当时的科学技术水平较低,在保障过程中遇到前方部队后勤保障需求不明、后勤物资配送网络不通畅等许多的难题,产生了“资源迷雾”和“需求迷雾”现象,严重影响了配送效果和保障效率。美军吸取了海湾战争配送式后勤保障的经验和教训,于1996年提出了“主动配送”的新模式,并将其界定为信息、后勤和运输技术的融合。Hanson[9]提出在进行保障部署问题时,应从社会,经济以及历史的综合维度进行考虑。当前关于作战后勤保障部署的理论大多借鉴商业领域供应链管理的相关研究成果,所提出的理论用于指导后勤保障体制、编制以及装备的变革,在具体落实当前关于这种近岸岛屿联合作战问题保障部署的过程中还需要进一步对相关的模型进行改进,才能使相关保障部署理论真正在现代近岸岛屿联合海上作战的问题中发挥作用。

由于高新技术在现代海上局部战争中的广泛应用, 作战方式发生了深刻变化, 实行全方位、多层次、连续不断的后勤支援保障显得越来越重要。其中受保障资源约束下,中继保障点的优化选址以及保障任务执行路线的优化,对保障的快速响应起到十分重要的作用。

本文面对海上保障点进行中继浮岛保障点的连续选址研究,其中连续选址问题的研究也经过了不少学者的探讨。Dinler[10]针对单个选址和多个选址问题建立了两个模型,对于单个选址问题,归因于一个二阶锥规划问题,可以在多项式时间内进行求解,对于多个选址问题,归因于一个多项式复杂程度的非确定性问题(non-deterministic polynomial, NP),难以在多项式时间内求解,因此采取了3种启发式算法进行比较,并在需求区域为矩形区域时,提出一种特殊的启发式算法以提高求解速率。Meira通过创建ε-近似中心集进行聚类来解决连续选址问题[11]。

在连续选址的各种方法[12-13]中,以给定一个初始位置选址,然后不断迭代寻找更好的选址为主要思路。学者通过对模拟退化算法、遗传算法的应用来找到较优的选址位置。本文试图在Xie[14]、Yang[15]研究的基础上将连续选址问题转化为线性规划问题,通过调用CPLEX求解器进行求解,使得求解过程较为简单。

由于在本文的研究中,除了进行中继保障点的选址外,还要研究最短支援路线的选择,总的来说本文研究的问题是在带有中继点选址的网络设计(network design problem with relays,NDPR)问题下进行的。中继点在不同的应用场景下具有不同的应用特征。在运输网络中,选择中继点交换驾驶员或改变运输方式。在绿色出行中,优化加油/充电的中继站选址从而减少能源消耗。在电信网络中,中继器是扩展光信号范围的再生器。

Adel[16]在电信和配电网有关的研究背景下提出了一个混合下降法来解决带有中继站点且两边不相交的网络设计问题。Chen[17]提出了一个带中继的随机最优路径问题,目标是在保持合理到达概率的同时便一般预期成本最小化，研究在给定的一对节点间寻找出驾驶范围有限的车辆的最优路径问题。如果节点对之间的最小距离超过范围限制,则必须在指定的站点为车辆加油。由于一条可行路径可能由多个中继组成,因此该问题被称为具有中继的最优路径问题(optimal path problem with relays, OPPR)。研究有中继站的最小成本路径问题的目的在于确定权值约束下的最小成本路径和中继站的位置选择。Markus[18]研究了有向-中继的网络设计问题(directed NDPR, DNDPR),其目的是构造一个最小成本网络,使给定的一组起始点-目的地能够进行通信,研究分支-切割算法并考虑有效的不等式,以加强得到的对偶界并加快收敛速度。Zhou[19]考虑了在固定的预算下,如何获得最少中继节点数,以设计一个在固定预算约束下具有“最大连通性”网络的问题。无人机(unmanned aerial vehicle, UAV)作为一种半双工解码转发(decode and forward, DF)中继设备,在紧急情况下为室内用户和室外基站建立了可靠的链路。Cui[20]设计了一个按功率分配以及带宽分配的公平位置优化算法,通过合理的功率和带宽分配,可以快速确定无人机的最佳位置,并使中断概率最小。该算法最大限度地保证了用户的公平性,中继链路间的中断概率差距在1%以内。Lu[21]分析了两个利用几何关系构造中继网络的直观解决方案,提出基于预测的动态中继模型,然后证明其相对于静态部署解决方案的优势; 其次,基于动态中继模型,提出了一种中继网络部署算法。单向电动汽车共享系统有望成为未来交通系统的一个组成部分,在减少交通拥堵和碳排放方面发挥重要作用。Zhang[22]建立了电动汽车的分配模型并考虑了中继车辆的影响,使用户能够通过顺序乘坐两辆车来完成更长的行程。Li[23]提出了一种基于禁忌搜索的迭代元启发式算法,在两个步骤内迭代求解带有中继点的网络设计问题:首先生成路径,然后确定与这些路径相关联的最优中继分配。Ma[24]研究了通过选择额外的中继节点来构建具有网络可重构性的无线传感器网络问题。针对此问题,提出了一个包括覆盖阶段和连接阶段的工作框架。Ilhan[25]针对使用解码转发中继的基于下行链路正交频分多址的用户中继辅助蜂窝网络,提出了能源效率最大化问题。针对建立的混合整数非线性规划模型,提出了一种实用的两阶段解决方案。Khaled[26]在考虑两种干扰情况的同时将移动中继节点用于“室外”(外部)小区边缘以改善其连通性。Khan[27]设计了基于预测的移动性的可获利的中继选择算法,用于协作通信。Xiao[28]基于高效运送商品的背景提出了一种基于可变邻域搜索的混合方法。可变邻域算法搜索每种商品的路线,并用隐式枚举算法确定给定路线集的最佳中继位置。Konak[29]指出,通过解决集合覆盖问题,可以为给定路径集优化确定中继位置,并开发了一种混合遗传算法完成路径搜索,通过解决集合覆盖问题来确定中继位置。随后,Konak[30]应用相同的原理解决了两个边缘不相交的NDPR,其中中继位置由拉格朗日启发式算法确定。Kabadurmus[31]也通过考虑边容量来研究两个边不相交的NDPR问题,并基于问题的数学表达式提出了一个三阶段启发式算法。

基于以上的研究,本文在近岸岛屿联合海上作战提供保障支援的应用背景下,研究了带有中继点的保障网络设计问题,针对海上区域往往需要陆地上的基地级保障点提供远程支援,而海上保障点除一些可以通过离散选址得到的岸基保障点外,还需要通过连续选址得到的浮岛、保障船等作为中继保障设施,受到保障资源约束,提出了连续离散相结合选址下的中继点的选择,同时进行最低成本路径选择,以使得支援路径成本最小,保障资源消耗最低,并且能达到最快响应的目的。

1 远程中继保障网络模型

1.1 问题描述

假设在远海海域的多个目标区域内具有发生安全事件的概率。一旦发生安全事件,则需要从大陆保障基地派遣飞机进行紧急支援和救援。每个事发点根据事发严重程度不同,需求的支援机队的数量也不同。由于支援机队的航程半径约束,途中需要降落至中继节点,在完成加油保障之后继续飞往救援区域,受中继保障点的保障资源约束,中继节点(包括岛礁和浮岛中继保障点)的数量也受到一定的限制。为了加快支援的响应速度,节省支援路径成本,节省设立中继保障点的资源,本文旨在优化选择近海岸位置、海面海岛或岛礁，从而建立合适的中继节点,并且优化保障支援路径,使救援活动能够得到保障,使在满足保障需求的同时运用更少的资源,能够达到最低期望救援成本的目的。

该问题可抽象为一个无向图G(V,E)来描述,其中V表示顶点的集合,E表示边的集合。顶点位置坐标表示为(Xi,Yi),边的长度表示为dij,其在i∈V,j∈V, (i,j)∈E。令集合S和T分别表示救援活动的出发节点和目标节点,且有S⊂V和T⊂V。再令飞机类型的集合为H,以L表示救援线路集合。对于每一支救援路线 (h,s,t)∈L,其中h∈H,s∈S,t∈T,均需要从s节点出发,途径经停图G的部分顶点后,到达目标节点t,并满足飞机的航程约束。

此问题的特殊性体现在如下几个方面。

(1) 多任务不确定环境

由于现场环境复杂多变,接收到的任务需求也在时刻变化,并且可能同时存在两个或两个以上的保障任务需求,保障支援路径需要根据目标点的分布,结合提供远程中继保障的基地级保障点的位置,进行中继保障点的最优选址,从而能够通过优化后的中继保障点的选址,针对不同的保障任务选择响应最快的保障路径。此外还考虑不同事发点的事发频率作为需求的权重。

(2) 多种飞机机型及性能约束

由于保障任务需求的多样化,需调派不同类型的支援机以响应对应的保障任务。每种机型的飞机性能,尤其以飞行半径为主要性能代表，对中继保障点的位置选取具有较大的影响。因此问题中考虑中继保障点位置选址时,还要综合考虑多种支援机的飞机性能。

(3) 离散与连续选址混合

对于中继保障点的选址,在海岸沿线可以预选一些合适的地点作为中继保障点的预选址,在此类固定预选点的岸基保障点中进行选址属于离散选址。此外,考虑事发地点处于远离岸基的海洋上,仅仅设定岸基或离海岸线较近的岛屿保障点不能完全满足保障的较快响应,因此需要设定海上浮岛或保障船保障点,以更快满足保障需求。而海上浮岛保障点的选址范围较大,较难应用离散选址问题进行求解,因此采用在限定范围内进行连续选址的方法进去求解,本文中还将对连续选址的求解方法进行进一步的探讨。

(4) 混合整数规划模型

由于本问题中,涉及离散和连续选址问题相结合,既涉及到整数变量,也涉及到了连续变量。设计的数学模型为混合整数规划数学模型,其约束中涉及了非线性约束,下文将针对此类NP-hard问题的求解进行较为详细的解释,并通过将线性约束转化为非线性约束的方法,求解此混合整数规划模型。其中非线性约束转化为线性约束通过几何近似来实现。

面对如上问题描述,在实际进行保障支援时首先开展区域保障需求分析,确定目标保障区域的范围界定和保障需求估算,行程保障区域的特征参数。同时,分析保障方的保障能力,分析各种可能的保障点建设方案(岸基保障点、岛礁保障点、浮岛/保障船),分析各种保障方案的保障能力和容量约束,获得各类保障方案的能力特征参数。然后,建立局域保障配置优化数学规划模型,研究模型的最优化求解方案和开展仿真实验验证与分析。此模型的主要输入和输出如图1所示。

图1 模型输入输出框架图Fig.1 Frame diagram of input and output of model

1.2 参数符号及混合整数规划模型

T:保障目标的集合。

S:机场节点的集合。

H:飞机机型集合。

L:支援路线方案集合L(H,S,T)。

W(h,s,t):从S起飞到达T,需求飞机数量。

Rh:不同飞机类型的最大飞行距离,h∈H。

Pt:某地发生战事的可能性概率,t∈T。

N:路线节点集合。

ai:节点的类型,ai=1表示基地级保障点;ai=2表示中继点(岛礁);ai=3表示中继点(浮岛);ai=4表示保障目标。

Chj:岛礁/浮岛的容量(可驻停飞机最大数量,正对不同类型)。

e:岛礁保障点的个数。

f:浮岛保障点的个数。

i:路线节点,i∈N。

j:路线节点,j∈N。

(Xmax,Ymax):保障点的选址范围(最大X、Y坐标)。

(Xmin,Ymin):保障点的选址范围(最小X、Y坐标)。

Dij:节点之间的距离。

ri:是否可以经停(即:是否建造岛礁/浮岛)。

X(h,s,t)ij:飞机路径选择变量。

Pθ:欧式距离精度表示。

M:一个大数。

d(h,s,t)ij:保障区域与浮岛保障点的欧式距离, 如果不是服务关系则为0。

ri:是否可以经停(即:是否建造岛礁/浮岛),1-是;0-否。

目标函数:

min Total_Weighted_Dis=

(1)

约束条件:

(2)

(3)

∀{(h,s,t)∈L,∀i∈N|i≠s∩i≠s}

(4)

(5)

(6)

(7)

(8)

x(h,s,t)ij≤ri

∀{i∈N,j∈N,(h,s,t)∈L|i≠j,ai≥2}

(9)

(10)

(11)

(12)

(13)

(14)

(15)

d(h,s,t)ij=x(h,s,t)ijDij

∀{i∈N,j∈N,(h,s,t)∈L|ai≠3∩aj≠3}

(16)