航母编队补给船动态补给路径规划模型及算法研究

王城超 邹 强 贾汝娜

（海军航空大学 烟台 264001）

1 引言

从航母编队作战的实际情况来看，航母编队作战物资消耗很快，特别是弹药等作战物资，其消耗规律难以准确预测，这就导致航母编队海上补给路径规划具有动态性，所以开展更符合航母编队实战的多补给船动态补给路径规划方面的研究显得尤其重要。目前，国外对海上补给路径规划研究［1］较成熟，Williams［2］将海上补给路径规划将其视为车间调度问题（VRP）。在多补给船动态补给路径规划方面，虽然没查到编队内动态补给规划策略方面的现成文献，但是从美军航母战斗群建立的全球范围内的多战斗群后勤保障等建模与仿真模型［3～6］和BGLCSS［7］等后勤物资保障系统中可以看出其动态补给规划的策略。国内对航母编队海上补给路径规划研究较晚，主要是针对编队单补给船海上补给路径规划［8～10］方面的相关研究，主要是将该问题视为TSP问题进行求解，在编队多补给船动态补给路径规划方面难以查到相关文献。基于此，本文开展航母编队补给船动态补给路径规划方面研究。

航母编队补给船补给模式主要有三种，即送报男孩（delivery boy）模式，加油站（gas station）模式，巡回牧师（circuit rider）模式，考虑到后两者模式下编队海上补给路径规划很难实现准时动态化，故本文只研究送报男孩模式下带时间窗的航母编队补给船动态补给路径规划，本文将该问题描述为带有时间窗的动态补给路径规划问题（Dynamic Replen⁃ishment Routing Scheduling Problem with Time Win⁃dows，DRRSPTW），本文的研究可以为我军航母编队的后勤物资保障系统建设提供理论和策略支撑。

2 数学模型的建立

2.1 模型假设条件

在航母编队实际作战中，DRRSPTW问题涉及和考虑的因素较多，在建立的数学模型对其进行求解时，建立的数学模型肯定与真实情况下的DRRSPTW问题有部分差异。所以为了能够准确地对DRRSPTW问题进行建模，必须根据实际情况对模型做出一定的假设。带时间窗的航母编队多补给船补给路径规划，对补给时机要求极为严格，属于硬时间窗条件下的多补给船补给路径规划，基本假设如下：

1）航母编队有k艘伴随补给船对编队中作战舰艇进行伴随弹药补给，k艘伴随补给船没有航行距离限制；

2）补给船从初始位置出发，依次对各待补作战舰艇进行弹药补给，补给结束后补给船回到初始位置，该段时间也被称为编队补给时间；

3）补给船的弹药储备量可满足编队作战舰艇的所有补给需求；

4）补给船的对每艘待补作战舰艇的开始补给时间满足时间窗口约束；

5）伴随补给船可在战斗中随时对编队内待补作战舰艇进行弹药补给；

6）每艘作战舰艇只补给一次。

本文用图论的方法来描述多补给船补给路径规 规 问 题 。 定 义 无 向 图G=(V ，A ) ，点 集V={0 ，1，…，n} ，其中{0}表示补给船的初始位置，V{0}表示待补作战舰艇的位置集合；弧线集合窗约束。

2.2 符号定义

A={( i ， j)|i，j∈V，i≠j} 表示连接2个待补作战舰艇之间的航行路线的集合，当i或j的值为0时，表示处于补给船的初始位置；补给船集合为k，k∈K。

数学模型中的参数含义及决策变量如下。

n表示航母编队中待补作战舰艇的数量；k表示补给船索引变量，k∈K={1 ，2，…，M } ；ri表示伴随补给船对待补作战舰艇i的补给作业时间；tsi和tei分别表示伴随补给船对待补作战舰艇i补给开始前的准备和撤离时间；dij表示伴随补给船从作战舰艇i航行至作战舰艇（j包括补给船初始位置）的时间；Tia表示补给船到达作战舰艇i的时间；Tis补给船对作战舰艇i的开始补给时间；Tja补给船到达作战舰艇j的时间；补作战舰艇i补给的时间窗为［ETi，LTi］。

2.3 模型建立

在满足流程约束、时间窗约束和整数性与非负性约束等条件下，建立以完成编队作战舰艇弹药补给的最小化补给船数量和最小化补给航行时间为目标的数学模型。

目标函数：

流程约束条件

时间窗约束条件：

式（1）为目标函数，其中 p1、p2为整数，且有p1≫p2。目标函数是一种组合化的目标函数，第一目标为最小化补给船的使用数量，第二目标为编队最小化补给航行时间。

式（2）～（6）为流程约束条件，保证了补给船从初始位置出发，补给结束后回到初始位置。式（2）～（3）表示每艘作战舰艇仅由一艘补给船补给弹药，且确保了每艘作战舰艇都能被一艘补给船补给一次。式（4）是为了确保线路的连续性，且输入输出弧相等。式（5）～（6）是为了确保补给船从初始位置出发，并保证补给结束后返回初始位置。

式（7）～（8）为时间窗约束条件。式（7）表示补给船到达作战舰艇的时间约束，保证了补给时间的连续性。式（8）表示补给时间窗约束，补给船对待补作战舰艇i的最早开始补给时间满足作战舰艇i的补给时间窗

3 DRRSPTW模型求解策略设计

3.1 两阶段求解策略

将DRRSPTW模型求解策略概述为两阶段求解策略，即预期补给路径规划阶段和动态局部补给路径规划阶段。DRRSPTW模型的两阶段求解策略流程图如图1。

3.2 动态局部补给路径规划求解策略

由于预期补给路径规划是一种比较传统的静态补给路径优化问题，求解过程比较简单，在这不再过多赘述，下面重点对动态局部补给路径规划进行重点阐述。

动态局部补给路径规划阶段，即补给船的动态补给时间段[Ts，Tk]，研究的对象是因作战舰艇补给时间窗不确定而引起的DRRSPTW，可以将作战舰艇补给时间窗不确定情况分为新增作战舰艇补给需求、原作战舰艇补给需求取消、原作战舰艇补给时间窗变更（延误或提前）等三类。

用基于时间的分批处理策略来求解动态补给时间段路径优化问题的基本思路如下：

1）首先将补给时间段[Ts，Tk] 划分为n个时间片段T，且这n个时间片段T必须是等间隔的时间片段，可依次表示为(T1、T2、T3…Tn)。

2）采用最晚指派策略，将动态补给转换为瞬时静态补给。在每个时间片段结束之前只接受动态信息但不进行处理，补给船依旧按照原补给路径规划方案执行补给任务，直到每个时间段的末尾时刻，即t=T，对该时间片段内的动态信息进行一次性批量处理。

图1 DRRSPTW模型的两阶段求解策略流程图

将DRRSPTW转化为瞬时静态补给路径规划问题之后，根据补给船补给过程中的实时动态信息，判断作战舰艇补给需求类型，可分为原作战舰艇补给需求取消、原作战舰艇补给时间窗变更和新增作战舰艇补给需求三种类型，设计相应的补给子策略。

下面分别对三种情况下作战舰艇补给时间窗变动后的补给子策略进行相关阐述。

1）原作战舰艇补给需求取消

假设航母编队内所有补给船的出发时间是使得补给船航行至第一艘作战舰艇的时刻刚好就是第一艘作战舰艇补给时间窗的开启时间。

在t=T时刻，对于原作战舰艇补给需求取消的情况，可以将原作战舰艇分三类进行分析，具体分析如下。

（1）取消补给需求的是某艘补给船补给路径规划的起始作战舰艇

如果补给船还没有离开初始位置，则补给船继续留在初始位置；如果补给船已经离开初始位置，则以该时刻补给船所在的位置为起点；上述两种情况都是将该补给船原计划补给路径规划方案中的第二艘作战舰艇作为下一个计划补给的对象，补给船的出发时间以原补给路径规划方案中的第二艘作战舰艇的补给时间窗约束为准。

（2）取消补给需求的是某艘补给船补给路径规划的中间作战舰艇

如果该时刻该补给船的下一个计划补给对象是该作战舰艇，则将该时刻该补给船所在的位置为起点，并以该补给船原计划补给路径规划方案中该作战舰艇的下一艘作战舰艇作为下一阶段的补给对象。

（3）取消补给需求的是某艘补给船补给路径规划的末端作战舰艇

如果该时刻该补给船的下一个计划补给对象是该作战舰艇，则将该时刻该补给船所在的位置为起点，该补给船直接返回其初始位置。

2）原作战舰艇补给时间窗需求变更（延迟或提前）

假设当出现原作战舰艇补给时间窗需求变动的情况，可能会影响该补给船所规划的补给路径，但是不会影响其他补给船的补给路径规划。原作战舰艇补给时间窗需求变更策略如图2。

图2 原作战舰艇补给时间窗变更策略流程图

方案1：当原作战舰艇补给时间窗需要变更时，在补给调度中心查看该作战舰艇所属补给船的补给路径规划情况，在不改变其他补给船所规划补给路径的前提下，以该时刻该补给船所在位置为起点，按照余下未补给作战舰艇变更后的补给时间窗进行补给路径的局部优化。如果该补给船出现多艘作战舰艇的补给时间窗冲突情况，则需做进一步判断分析。

方案2：从补给船初始位置调用闲置补给船对该作战舰艇进行补给。如果补给船初始位置无闲置补给船可调用，则转入方案3。

方案3：调用穿梭补给船来对该作战舰艇进行弹药补给作业。

3）新作战舰艇补给需求

新增作战舰艇补给需求的动态补给策略流程图如图3。

图3 新增作战舰艇补给需求的动态补给策略流程图

动态补给策略流程图中第三步中的“一定的规则”的含义如下：假设Q中有m艘补给船，分别记为k1、k2、…ki…km。 Dki表示t时刻补给船 ki所在的位置与新增作战舰艇位置和补给船ki余下未补给的所有作战舰艇的距离平方和，其中i=1，2…m 。

若Dku=min( )Dki，则选取补给船ku对新增作战舰艇进行补给作业。若该补给船ku对新增和余下未补给作战舰艇补给路径进行规划时，出现两艘作战舰艇补给时间窗冲突，则按照距离平方和Dki从小到大的顺序，依次选择补给船对新增作战舰艇进行补给作业，直到满足补给要求为止。

4 改进C-W算法

在动态局部补给路径规划阶段，瞬时静态补给路径规划问题的实质是基于时间窗的TSP。由于传统C-W算法［11～12］不能直接用于求解带有时间窗的TSP，所以本文采用改进C-W算法来对该补给船余下作战舰艇弹药补给路径进行重新优化。

4.1 改进C-W算法的基本原理

对于带有时间窗的TSP，在连接两点时检验连接后是否满足时间窗条件，构造能求解该问题的启发式算法（简称改进C-W算法）。传统C-W算法中节约值一般是距离的节约值，而改进C-W算法中节约值表示时间的节约值，故本文讨论的是满足时间窗条件下的补给船最小化补给航行时间的补给路径优化问题。

假设s(i，j)表示连接两个待补作战舰艇所在位置i和（j简称两个点i和j）的时间节约值（以下简称节约值），在连接两点i和j后，可能会导致补给船到达后面作战舰艇补给需求点的时间改变，即可能导致补给船到达后面待补作战舰艇补给需求点的时间不能满足既定时间窗要求。假设EFj表示连接i和j点前后到达j点时间变化量，具有如下公式：

EFj=Ri+Ti+tij-Rj

其中，Ri表示补给船到达处于补给需求点i的待补作战舰艇的时间，Rj表示连接前补给船到达处于补给需求点j的待补作战舰艇的时间，Ti表示补给船对处于补给需求点i的作战舰艇进行弹药补给的时间，tij表示补给船从一艘作战舰艇的补给需求点i航行至另一艘作战舰艇的补给需求点j的所花费的时间。

若EFj＞0，则表示连接点i和j之后，补给船到达作战舰艇补给需求点j的时间推迟。

若EFj=0，则表示连接点i和j之后，补给船到达作战舰艇补给需求点j的时间不变。

若EFj＜0，则表示连接点i和j之后，补给船到达作战舰艇补给需求点j的时间提前。

假设TBj表示连接i和j点之后，j点和j点后面作战舰艇补给需求点允许到达的最大提前时间；TAj表示连接i和j点之后，j点和j点后面作战舰艇补给需求点允许到达的最大推迟时间，则有如下公式

其中r表示补给需求点j和j点后面作战舰艇补给需求点，作战舰艇补给需求点r的补给时间窗为[E Tr，LTr]。

当 EFj＜0，且 | EFj|≤TBj时，则有连接后补给船到达作战舰艇补给需求点r的时间不会早于ETr，即连接后到达作战舰艇补给需求点r的时间满足时间窗上限要求。

当 EFj＞0 ，且 EFj≤TAj时，则有连接后补给船到达作战舰艇补给需求点r的时间不会晚于LTr，即连接后到达作战舰艇补给需求点r的时间满足时间窗下限要求。

4.2 改进C-W算法流程

图4 改进C-W算法流程

下面对图4中改进C-W算法的部分重点步骤进行详细阐述。

Step1：初始解的确定，并计算该初始解的总航行时间。初始解设置为派出K艘补给船分别对K艘作战舰艇进行补给，补给结束后分别回到初始位置的路径规划，即K条o→i→o的补给路径，初始解的总航行时间如下：

其中doi表示补给船从初始位置航行至作战舰艇补给需求点i的时间；dio表示补给船补给结束，从补给需求点i返回初始位置的航行时间。

Step2：计算补给需求点i和j连接后的节约值s(i，j)，即计算连接后路径o→i→j→o比原路径o→i→o和o→j→o的节约值。

Step3：将节约值s(i，j)按照由大到小的顺序进行排序，并构成集合M={s ( i，j)| s(i，j) ＞0} 。

Step4：“三个条件”依次如下。

1）作战舰艇补给需求点i和j都不在已构成的补给路径上，即存在补给回路 o→i→o和o→j→o，此时则将补给路径 o→i→j→o作为候选连接补给路径。

2）作战舰艇补给需求点i和j中的一个点在已构成的补给路径上，且该补给需求点与o点相连，而另外一个补给需求点不在已构成的补给路径上。假设补给需求点i在已构成的补给路径上（即存在补给回路o→i→…o或o…→i→o），补给需求点j不在已构成的补给路径上（即存在补给回路 o→j→o）。此时则把补给回路o→j→i→…o或 o…→i→j→o作为候选连接补给路径回路。

3）作战舰艇补给需求点i和j分别在已构成的不同补给路径上，且补给需求点j为补给路径中的第一个补给需求点，补给需求点i为补给路径中的最后一个补给需求点，即有 o→j→…o和o…→i→o 。 此 时 则 把 补 给 回 路o…→i→j→…o作为候选补给路径回路。

Step5：假设作战舰艇补给需求点j位于补给路径上i补给需求点之后，分别计算EFj、TBj和TAj，然后再根据EFj、TBj和TAj三个值作进一步判断。

5 实例分析

本文以一种典型双航母编队的海上补给路径规划为例，编队构成包括2艘航母母舰、3艘伴随补给船、15艘编队附属水面舰艇，对所提出的求解航母编队补给船动态补给路径规划的模型与方法进行验证。由于论文篇幅有限，故只给出新增作战舰艇补给需求情况下的实例结果。

5.1 初始输入数据和相关参数设置

1）初始输入数据

假设3艘伴随补给船的初始位置都处于坐标中心，编队中伴随补给船的初始位置编号1，各作战舰艇补给需求点位置依次编号2、3、…、17。由于保密原因，本文的初始输入位置等是人为给定的，具体如下。

表1 输入初始数据

（2）相关参数设置

1）补给船的平均航速v=25节（海里/小时）；

2）改进GA的相关参数设置为：种群大小n=60，最大迭代次数M=200，交叉率Pc=0.9，变异率Pm=0.1。

5.2 初始补给路径规划结果

表2 预期补给路径规划方案

图5 补给船预期补给路径规划图

5.3 新增作战舰艇补给需求后的补给船补给路径规划结果

新增作战舰艇补给需求相关信息如表3。

表3 新增作战舰艇补给需求相关信息表

从表3可看出，实时动态信息的处理时刻为t=19h，此时补给船补给路径图如图6。

从图6中可看出，t=19h时刻，1号补给船正位于图中的0点，坐标为（-23.46，29.59），6号作战舰艇未补给；2号补给船正位于图中13点，坐标为（25.52，-48.38），剩下12号作战舰艇未补给；3号补给船正位于图中10点，坐标为（38.57，45.96），剩下9号作战舰艇未补给；19号为新增作战舰艇，坐标为（-2，30）。

图6 补给船t=19h时刻补给路径图

通过计算可得，Dk1=854.74；Dk2=3585.41；Dk3=7937.67。故选择1号补给船对新增19号作战舰艇进行补给。采用改进C-W算法对1号补给船所在路径上的新增作战舰艇和剩余作战舰艇补给路径进行局部再修正，结果如下。

表4 新增作战舰艇后补给船补给路径规划方案

图7 新增作战舰艇后补给船补给路径修正图

6 结语

本文研究带时间窗的航母编队补给船动态补给路径规划问题。针对战时航母编队海上补给路径规划具有动态性，建立了DRRSPTW问题的数学模型，设计了求解策略，设计了改进C-W算法来求解该模型。最后选取了一种典型航母编队补给船动态补给路径为案例，进行了实例分析，新增作战舰艇补给需求后的补给路径规划方案和补给路径规划图。计算结果验证了该模型与方法的合理性，本文的研究可以为我军航母编队的后勤物资保障系统建设提供理论和策略支撑。

［1］ Conley T E，Hughes W P.Analysis of Pacific Fleet Un⁃derway Replenishment data［J］.Analysis of Pacific Fleet Underway Replenishment Data，1988.

［2］Williams T M.Heuristic Scheduling of Ship Replenish⁃ment at Sea［J］.Journal of the Operational Research Soci⁃ety，1992，43（1）：11-18.

［3］Schrady D A.Measures of Effectiveness in Logistics［J］.Technical Reports Collection，1989.

［4］Beveridge JD.An analytical and computer simulation ap⁃proach to the problem of replenishing task forces at sea［J］.1970.

［5］Brooks B C.Structured Vesus Objective-Oriented Design of Battle Group Logistics Simulation System［M］.califor⁃nia：Naval Postgraduate School，1970.

［6］Schrady D A.Operational Logistics：OA 3610，Introduction to Naval Logistics［M］.california：Naval Postgraduate School，1997.

［7］Hall W，Naval Postgraduate School（U.S.The Battle Group Logistics Comparative Analysis Model（BGL⁃CAM）：A Comparative Analysis Tool for Multi-Battle Group Logistics Support［J］.1997.

［8］余鹏，何学军.基于蚁群算法的舰艇编队海上补给路径规划方法［J］.海军工程大学学报，2014，26（2）：108-112.

［9］周晓光，赵厚仁，王述运，等.航母编队补给船海上补给航路规划［J］.系统工程与电子技术，2014，36（9）：1756-1760.

［10］黄必佳，王公宝.航母编队油料伴随补给规划模型及算法研究［J］.兵工自动化，2015，34（9）：78-83.

［11］郑英，孟志青.基于节约算法的烟草物流配送线路优化［J］. 中国管理信息化，2010，13（23）：41-43.

［12］崔宏志，龚加安.带时间窗车辆路径问题的改进节约算法［J］. 纯粹数学与应用数学，2011，27（5）：688-693.