中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Task Planning & Firepower Allocation

Intelligent mission planning of materials supply for sea islands

  • YU Changren ,
  • QIAO Han ,
  • HAN Mengyao ,
  • ZHANG Guojie
Expand
  • Army Logistics Academy, Chongqing 401331, China

Received date: 2022-09-23

  Revised date: 2022-12-29

  Online published: 2023-10-13

Abstract

The materials supply for sea islands is the basis for ensuring survival needs of persons on sea islands. Considering factors such as transportation cost, storage cost, recycling demand and transportation capacity, it is a vehicle path planning problem with time window and capacity limit to use many transportation tools to supply materials for sea islands within a time cycle. The intelligent algorithm provides a preferable solution to solve this complex irregular optimization problem. The paper establishes a mathematical model of mission planning of materials supply for sea islands, explores the solving process of genetic algorithm, and uses an example to calculate it. The optimization result shows that the scheme can save transportation costs and storage costs, and also meet the need of materials supply cycle, which can provide a reference for scientific mission planning of materials supply for sea islands.

Cite this article

YU Changren , QIAO Han , HAN Mengyao , ZHANG Guojie . Intelligent mission planning of materials supply for sea islands[J]. Command Control and Simulation, 2023 , 45(5) : 104 -109 . DOI: 10.3969/j.issn.1673-3819.2023.05.014

岛礁是维护我国海洋权益的前哨,是我国领土不可分割的组成部分,派驻人员守卫岛礁对保障我国领土完整具有重要的意义。远海海域诸岛礁距离大陆较远,位置相对分散[1],岛上物资匮乏,为维持驻岛人员生存生活需要,需定期由陆上保障中心派出补给船对岛礁进行补给,制定科学的物资保障方案,提高保障的效益[2]
岛礁物资补给有特定的保障目标和影响因素,主要解决物资补给任务规划问题。岛礁物资补给任务规划问题指在满足自然停泊环境、保障时间、运输工具装载量限制等条件下,使得保障目标达到最优,保障目标包括运输工具燃油经济性、物资储存成本等,所以其本质是一个车辆路径规划(Vehicle Routing Problem, VRP)[3]问题,这类问题有精确算法与启发式算法等[4]。精确算法主要运用线性规划、整数规划、非线性规划等严格的数学方法求解,比较适合特定的问题,而启发式算法适合解决一些不规则优化问题。VRP问题常有容量约束或时间窗限制[5-6],也可能两者兼而有之,这类问题是NP(Non-deterministic polynominal,多项式复杂程度的非确定性)[7-8]难问题。智能算法作为启发式算法的一种,适合解决大规模的组合优化问题,能在解空间内高效率地寻找出极优解,典型的组合优化问题有旅行商问题(Traveling Salesman Problem, TSP)[9]、调度问题、0-1背包问题、装箱问题等。优化目标是在可行解域内找到近似解来代替最优解,减少求解需要付出的代价。智能算法包括但不限于模拟退火、蚁群算法、遗传算法、禁忌搜索算法等。

1 岛礁物资补给任务规划问题建模

1.1 模型考虑的因素

岛礁物资补给由后勤补给中心运用各型补给舰船对海域岛礁实施运输补给。考虑补给时间、补给需求和补给效益,运输投送方案最优化受自然条件、经济成本和运输工具等多种因素影响。
1)自然地理条件。岛礁附近海底地貌、岸滩底质各不相同,靠泊条件各异,对于靠泊港口大的岛礁,补给舰可直接补给,对于靠泊港口小的岛礁,补给舰须在距岛礁附近某处锚泊,通过配套小型补给艇进行转运实现间接补给,或采用某岛礁上的拖船完成物资倒运。
2)运输工具。可运用不同型号的大型补给舰,从特定的补给中心出发,补充一定数量的岛礁后再返回该补给中心。一条运输路线上仅有一艘大型补给舰。补给舰配备若干小型补给艇,拖船也可以用于短距离的物资转运。
3)运输成本。某海域领域广阔,岛礁位置相对分散,岛礁间距较远,距离是影响保障成本的主要因素。各型补给舰各有不同的燃油经济成本。规划不同的保障路径将产生不同的运输成本。拖船与小艇产生的短距离运输成本可忽略不计。
4)运输与装卸时间。各型补给舰航行速度已知,假设补给舰装有固体、液体两类物资,固体、液体的装卸也有不同的速度。各种运输工具(补给舰、小型补给艇、拖船)所载燃油能满足其去各岛补给的需要,即不考虑燃油耗尽需返回的问题。补给舰(艇)卸载固体物资和液体可同时进行,互不影响,回程时,需要从岛礁装载固体回收物。
5)储存成本。某海域岛礁大多属于热带、亚热带海洋性气候,具有高温、高湿、高盐的突出特点,各类物资易腐烂变质,长期存储需采取低温冷藏保鲜。物资储存成本也是物资补给应考虑的重要方面。固体、液体储存成本以储存天数和吨位数平均计算,单位为元/吨·天。
6)补给要求。各岛礁存储空间有限,固体、液体物资均有最大储存量,各岛礁补给之前有一定的剩余储备量,固体、液体消耗速度以日均消耗量(吨)计量。需要补给一个时间周期内的物资需要,且要求在岛礁剩余物资消耗完毕之前进行补充。

1.2 模型建立的变量

模型建立的数学变量见表1
表1 变量说明

Tab.1 Variable description

R i l M i l D i l P i l 分别表示岛礁i现有液体存储量、最大液体存储量、需补充的液体量、液体消耗速度
R i s M i s D i s P i s 分别表示岛礁i现有固体存储量、最大固体存储量、需补充的固体量、固体消耗速度
D S i s 岛礁i固体回收需求量
n、m n个岛礁(用1…n表示,补给中心用0表示),m表示补给航线上运输工具的数量
Ltki、L t k i l、L t k i s 表示第k艘运输工具在岛礁i所补充物资最大装卸时间、液体装卸时间、固体装卸时间
C i l C i s 分别表示岛礁i液体存储单位成本、固体存储单位成本(元/吨·天)
Ck 第k艘运输工具单位里程(海里)的燃油成本
Q k l Q k s 分别表示第k艘运输工具液体最大装载容量、固体最大装载容量
L k l L k s 第k艘运输工具装卸液体的速度、装卸固体的速度
dij 岛礁i与岛礁j之间的距离(海里)
t k i 第k艘运输工具由补充中心0出发后,到达岛礁i的时间
Vk 第k艘运输工具航行速度

1.3 目标函数与约束条件

多艘补给舰从补给中心出发,遍历所有岛礁后返回当前补给中心[10],且多艘补给舰的路线不能重叠,总运输费用最小,这是典型的多旅行商(MTSP)[11-12]问题。旅行商问题是车辆路径规划问题的一种,如表1所述,点0表示出发的地点:补给中心。点1,2,…,n表示m个旅行商(补给舰)要访问的地点(某海域的各个岛礁)。
定义变量:
xijk= 1   k i j 0
yki= 1   k i 0
该问题的数学模型可表示为
目标函数:
$Z_{1}=\min \left(\sum_{k=1}^{m}\left(\sum_{i=0}^{n} \sum_{j=0}^{n} C_{k} d_{i j} x_{i j k}\right)\right) $
Ckdij表示第k艘运输工具经过对应弧段(i,j)所花费用(距离与运输工具k单位运输成本的乘积)。目标函数Z1表示使所有旅行商的费用最小化。
$\begin{array}{c} Z_{2}=\min \sum_{i=1}^{n}\left(C_{i}^{l} \frac{\left(R_{i}^{l}+P_{i}^{l}\right) R_{i}^{l}}{2 P_{i}^{l}}+C_{i}^{l} \frac{\left(D_{i}^{l}+P_{i}^{l}\right) D_{i}^{l}}{2 P_{i}^{l}}+\right. \\ \left.C_{i}^{s} \frac{\left(R_{i}^{s}+P_{i}^{s}\right) R_{i}^{s}}{2 P_{i}^{s}}+C_{i}^{s} \frac{\left(D_{i}^{s}+P_{i}^{s}\right) D_{i}^{s}}{2 P_{i}^{s}}\right) \end{array}$
目标函数Z2表示所有岛礁剩余物资(固、液体)储存成本与补充后的物资储存成本和最小。
约束条件:
k = 1 myki= m   i = 0 1 i = 1,2 , , n
i = 0 nxijk=ykj
j = 0 nxijk=yki
约束条件(3)表示从地点0出发,每个将被访问地点有且仅有一个旅行商经过;约束条件(4)表示任一条弧的终点仅有一个起点地方与之相连;约束条件(5)表示任一条弧的起点地方仅有一个终点地方与之相连[13]
与此同时,还要考虑时间窗与各运输工具容量限制。各岛礁所需物资最早在其剩余物资刚消耗时进行补充,最晚于剩余物资耗尽时进行补充,再补充时可以按最大储存量进行补充。所以有以下约束条件:
M i l- R i l D i l M i l
M i s- R i s D i s M i s
约束条件(6)、(7)分别表示岛礁i需补充的固体、液体的取值范围。因物资卸载时,固体、液体可同时进行,并回收固体垃圾。第k艘运输工具运送的物资在岛礁i的装卸时间为Ltki=max D i l L k l , D i s + D S i s L k s,取装卸液体或装卸固体(含回收的固体)的时间最大值。因所运输物资最晚须于岛礁剩余物资消耗完毕之前进行补充,故有以下限制条件:
t k i+Ltki≤min R i l P i l , R i s P i s
约束条件(8)表示第k艘运输工具到达岛礁i的时刻加上物资装卸时间须小于岛礁i剩余物资消耗完毕所耗费的时间。因运输工具有容量限制,还有关系式:
i = 1 n D i l yik Q k l
i = 1 n D i s yik Q k s
约束条件(9)、(10)分别表示第k艘运输工具所补充岛礁液体需求量小于其最大液体载重量、最大固体载重量。

1.4 智能算法求解

如前所述,VRP问题可运用的算法有多种,但此问题有诸多的约束条件,可采用智能算法如模拟退火、禁忌算法、遗传算法(Genetic Algorithm, GA)[14]甚至是多种算法的结合进行求解。这些算法不存在对函数求导或连续性等限制,对多目标规划具有较好的全局搜索最优解能力。岛礁物资补给任务规划问题中若岛礁数量不太多时,可采用一种具有代表性的算法如GA进行求解,GA是一种智能进化算法[15],通过把问题参数编码为“染色体”,利用迭代运算方式,设定适应度函数,使经选择、交叉和变异等操作后的“染色体”最终符合优化目标。
1)染色体编码。岛礁物资补给路径规划问题可采取实数编码方式,即补给中心为0,各岛礁为1,2,…,n,编码长度为n+m。如岛礁数量为8、运输工具数量为2时,若编码为{0,1,2,5,0,3,4,6,8,7}表示路径为0-1-2-5-0和0-3-4-6-8-7-0。按此编码方式生成一定规模的初始种群。
2)适应度函数。遗传算法是一个不断从种群中选择适应度高的个体的迭代优化过程,该任务规划问题中,目标函数取极小值,故以目标函数的倒数为适应度函数F
3)选择算子。从种群中选择优异的个体,使其以较高概率成为父代基因进入下一代种群中。采用轮盘赌法则,设种群规模为U,个体被选中的概率计算公式为Pi= F i i = 1 U F i
4)交叉算子。采取部分映射杂交,对初始解中两个基因串中的随机片断进行交叉操作,还是以n=8,m=2为例,对下列两基因中的第4、7位中间数据进行交叉,交叉后有部分数据冲突,用*表示,再采用部分映射的方法消除重复,得到以下结果。
5)变异算子。在父代基因中随机选择两个断点,将断点之间的基因逆序排列或交换断点位置,从而产生一个新的个体。
6)重新插入初始种群得到更新后的新种群。进行迭代运算,以适应度函数为选择准则,不断把问题的可行解进行收敛,从而得到最优解。

2 实例运用

根据文献[16]给出的实例,由补给中心点C为岛礁(D1~D9)运送所需物资,由AB两种型号补给舰执行物资补给任务,每条补给舰各配备2艘小艇。补给舰回程运回固体垃圾。补给方案应包括补给舰种类、补给路线、补给数量、转运方式、物资装卸与回收材料的数量等。各岛礁(含补给中心)位置、储物情况、补给舰(艇)信息见该文献相关数据。
VRP问题中,目标函数与约束条件的处理较为复杂,总目标函数通常可取多个目标函数的加权平均,考虑约束条件时,遗传算法编码生成的初始种群及交叉(变异)后种群还要验证其是否满足约束条件,若是不可行解,需要一系列复杂的处理,总体计算量大,迭代较慢。在岛礁物资补给问题中,可以具体问题具体分析,灵活处理目标函数与约束条件。补给舰的燃油成本及各岛礁物资储存成本是一个多目标取优问题,通过计算,可发现物资储存成本远小于运输成本,故在目标函数上可以运输成本为主,为使储存成本最低,补给原则是在满足岛礁物资保障不间断的前提下尽量延长补给时间,待各岛礁剩余物资耗尽后再进行补充。与此同时,还要考虑运输工具的容量限制,基于上述分析,可运用分步优化的思路,运用智能算法先找出符合成本最低的运输路径,然后基于该路径做出微调以符合时间窗要求和为各岛礁分配物资数量。

2.1 遗传算法仿真运行结果

为任务规划的均衡性,可设定每条路线所经历的岛礁数量至少为2个以上[17]。通过编程,使用Matlab2013b程序进行仿真,得出优化结果见图1,遗传代数为25。虚粗线表示A舰航行路径C-D2-D9-D4-D3-C,实细线表示B舰航行路径C-D1-D5-D8-D6-D7-C
图1 双舰补给路径规划图

Fig.1 Supply paths planning of dual ships

2.2 优化方案的确定

1)最优路径顺序的选择
使用AB舰给岛礁实施物资保障时,要求使得各岛礁至少维持一个特定的供给周期。补给总的原则是:①优先补给资源即将耗尽的岛屿,如D1、D2、D3、D4等;②尽量使得补给在现有物资耗尽之后再补充,并且补充周期内所需最大库存,因为这样可以使储存成本减少;③现有库存物资与后续补充的物资可用天数之和至少能满足一个补给周期所需。
确定最优路径后,需要进一步安排AB舰补给各岛的顺序,考虑AB舰保障的各岛当前储存物资可消耗天数情况,在图1所示的路径基础上,应对此做出微调,A舰先保障D2,再D3,尔后D4,再D9;由于D9是小岛,应于小岛外抛锚,再由小艇倒送物资。由于D8的可维持天数较长,而D6、D7保障时效要求更强,还应对B舰路径再做出微小调整,B舰先保障D1,再D5,尔后D6,再D7;由于D8需求量不大,时间又较为宽松,可利用2艘小艇同时由D7向D8运输物资。调整后的路线为A舰的C-D2-D3-D4-D9-C,路径长1574.07海里;B舰为C-D1-D5-D6-D7-C,路径长1 288.04海里,见图2
图2 调整后的优化路径

Fig.2 Adjusted optimization paths

2)各岛礁物资补给的数量与时间
在规划好AB 舰路径后,物资分配应按各岛礁能支持消耗一个补给周期的量分配,即按每天的消耗水平乘以补给周期再减去当前储存量,这样可以使得补给物资满足容量限制。进一步计算AB舰到各岛的航行时间与装卸物资时间。需要注意的是D8、D9比较特殊,对于A舰来说,需要停靠D9外某处,同时用2小艇倒运舰上物资保障D9岛所需,计算出小艇运输与装卸总耗时为17.27小时。对于B舰来说,停靠于D7后再保障D8所需,由于D8固体、液体的保障量较小,可以考虑运用2小艇来进行倒运物资,计算出总耗时为46.21小时。AB舰到达各岛的补给量与固体回收量、航行时间与物资装卸时间计算结果见表2
表2 A舰、B到达各岛的补给量、航行时间与物资装卸时间

Tab.2 Supply volume, sailing time and material loading time of ship A and ship B arriving at each island

补给舰 岛礁 与前站
点距离/
海里
航行
时间/
h
固体装
卸时间/
h
液体装
卸时间/
h
装卸
时间/
h
固体补
给量/
t
液体补
给量/
t
固体回
收量/
t
A舰(补给
中心C)
D2 455.2 22.8 1.48 2.06 2.06 7.4 31 2
D3 327.7 16.38 3 3.7 3.7 15 55.5 22
D4 63.5 3.17 3.4 5.33 5.33 17 80 5
D9 60.5 3.03 - - 17.27 1.5 9.75 1
B舰(补给
中心C)
D1 554.1 27.7 2.16 8.75 8.75 21.6 175 6
D5 46.3 2.3 1.08 2.08 2.08 10.75 41.5 16
D6 112.9 5.64 0.52 0.85 0.85 5.2 17 2.2
D7 24.95 1.24 0.46 0.8 0.8 4.6 16 2
D8 30.6 - - - 46.21 2.05 9.25 10
通过计算,AB两舰需装载补充的固体总量为85.1 t。A舰固体量为40.9 t,B舰固体量为44.2 t。A多出的0.9 t固体可以放小艇中。AB两舰需装载补充的液体总量为435 t。A液体量为176.25 t,B液体量为258.75 t。
3)最终方案成本分析
各岛补充后的物资储存总成本为66 690.9元。加上补充前的当前已有物资储存成本8 650.15,共75 341.05元。根据前面的优化路径,A的运输里程为1 574.07海里,B的运输里程为1 288.04海里,总费用为2 232 482元。最终的运输成本加上储存成本合计为2 307 823.05元。

3 结束语

文章建立了岛礁物资补给任务规划模型,分析了智能算法的求解过程,结合一个实例,采用算法进行仿真运算,综合利用数据分析,得出了优化方案[18-19]。方案从现实复杂问题出发,考虑保障任务较高的构成成本——岛礁物资运输成本,其次考虑储存成本、容量限制、补给周期等,分步进行优化调整,符合物资补给实际需要[20]。当然,考虑模型的拓展性,还需要进一步结合实际情况中的多种条件如天气情况对物资保障的影响,考虑把某些岛礁作为中转站进行二次补给的情况进行规划,这些还需在未来的研究中进一步深化。
[1]
王诺, 丁凯, 吴迪, 等. 面向远海岛礁群的双向物流网络规划[J]. 运筹与管理, 2019, 28(6):122-132.

WANG N, DING K, WU D, et al. Bidirectional logistics network planning of remote islands and reefs[J]. Operations Research and Management Science, 2019, 28(6): 122-132.

[2]
孔德鑫, 刘洋, 赵金, 等. 密集岛礁环境下的无人艇的路径规划[J]. 信息通信, 2020(3):14-17.

KONG D X, LIU Y, ZHAO J, et al. Unmanned surface vehicle path planning in dense island reef environment[J]. Information & Communications, 2020(3): 14-17.

[3]
郁磊. MATLAB智能算法30个案例分析[M]. 北京: 北京航空航天大学出版社, 2015:178-187.

YU L. Analysis of 30 cases of Matlab intelligent algorithm[M]. Beijing: Beijing University of Aeronautics and Astronautics Press, 2015: 178-187.

[4]
浮萍萍, 叶春明, 李佳桐. 物流配送车辆调度路径优化问题算法研究[J]. 物流科技, 2015, 38(3):5-8.

FU P P, YE C M, LI J T. Research on the algorithm of logistics vehicle routing optimization problem[J]. Logistics Sci-Tech, 2015, 38(3): 5-8.

[5]
李珍萍, 周文峰, 张煜炜, 等. 考虑卸载顺序约束的成品油二次配送车辆路径问题[J]. 控制与决策, 2020, 35(12):2999-3005.

LI Z P, ZHOU W F, ZHANG Y W, et al. Vehicle routing problem of refined oil secondary distribution considering unloading sequence constraints[J]. Control and Decision, 2020, 35(12): 2999-3005.

[6]
刘云, 张惠珍. 多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J]. 公路交通科技, 2016, 33(6):95-100.

LIU Y, ZHANG H Z. A partheno-genetic hybrid ant colony algorithm for solving multi-objective vehicle routing problem with time window[J]. Journal of Highway and Transportation Research and Development, 2016, 33(6): 95-100.

[7]
Damir H, Eric T. Gene tree reconciliation including transfers with replacement is NP-hard and FTP[J]. Journal of Combinatorial Optimization, 2019, 38(2):502-544.

DOI

[8]
孙翀翚. 利用光纤网络求解典型的NP完全问题[D]. 北京: 北京交通大学, 2017: 9.

SUN C H. Solving the typical NP complete problems using optical fiber network[D]. Beijing: Beijing Jiaotong University, 2017: 9.

[9]
张硕航, 郭改枝. 多旅行商模型及其应用研究综述[J]. 计算机科学与探索, 2022, 16(7):1516-1528.

DOI

ZHANG S H, GUO G Z. Review of multiple traveling salesman model and its application[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1516-1528.

[10]
邓南明, 唐世轩, 张迪. 基于模拟退火算法的岛礁补给路径规划[J]. 兵工自动化, 2017, 36(5):30-32.

DENG N M, TANG S X, ZHANG D. Reefs supply path planning based on simulated annealing algorithm[J]. Ordnance Industry Automation, 2017, 36(5): 30-32.

[11]
鲍逸群. 基于类MTSP模型和精英集策略遗传算法的多机器人任务分配研究[D]. 武汉: 武汉科技大学, 2017.

BAO Y Q. Research on multi-robot task allocation based on similar MTSP and GA with elite set strategy[D]. Wuhan: Wuhan University of Science and Technology, 2017.

[12]
ZHUKOVA G N, ULYANOV M V, FOMICHEV M I. A hybrid exact algorithm for the asymmetric traveling salesman problem: construction and a statistical study of computational efficiency[J]. Automation and Remote Control, 2019, 80(11): 2054-2067.

DOI

[13]
刘天宇, 叶军, 曹欣芹, 等. 基于动态网络图的兵力投送优化算法研究[J]. 国防交通工程与技术, 2017, 15(6):21-25.

LIU T Y, YE J, CAO X Q, et al. A study of the dynamic-network-diagram-based optimization of the computation methods for force projection[J]. Traffic Engineering and Technology for National Defence, 2017, 15(6): 21-25.

[14]
李江成. 基于启发式遗传算法的岛礁物资补给任务规划[J]. 军事运筹与系统工程, 2021, 35(2):12-17.

LI J C. Island-reef materials supply task planning based on heuristic genetic algorithm[J]. Military Operations Research and Systems Engineering, 2021, 35(2): 12-17.

[15]
皇甫尚乾. 改进罚函数分级遗传算法及其在结构优化设计中的应用[D]. 广州: 广州大学, 2018.

HUANGFU S Q. The hierarchical genetic algorithm with improved penalty function and its application in structural optimal design[D]. Guangzhou: Guangzhou University, 2018.

[16]
刘晨生, 宋士兵. 基于混合遗传算法的岛礁物资补给任务规划模型[J]. 军事运筹与系统工程, 2019, 33(4):27-32.

LIU C S, SONG S B. Island reef material replenishment task planning model based on hybrid genetic algorithm[J]. Military Operations Research and Systems Engineering, 2019, 33(4): 27-32.

[17]
王梓行, 姜大立, 王丰, 等. 战时单周期的远海岛礁战储物资供应保障任务规划模型[J]. 军事交通学院学报, 2019, 21(12):53-59.

WANG Z X, JIANG D L, WANG F, et al. Planning model of reserve materials supply support mission for offshore islands and reefs with single cycle in wartime[J]. Journal of Military Transportation University, 2019, 21(12): 53-59.

[18]
李坦, 肖晨, 钟普查. 部分扩散与试错混合量子搜索算法的性能和最优参数分析[J]. 信息工程大学学报, 2019, 20(6):758-762.

LI T, XIAO C, ZHONG P C. Performance and optimal parameters analysis of the hybrid partial diffusion and trail-and-error quantum search algorithm[J]. Journal of Information Engineering University, 2019, 20(6): 758-762.

[19]
张诗尧, 曾子维, 程子为. 无线传感器网络蚁群路由优化算法[J]. 辽宁科技大学学报, 2019, 42(3):209-214.

ZHANG S Y, ZENG Z W, CHENG Z W. An ant colony routing optimization algorithm for wireless sensor networks[J]. Journal of Liaoning University of Science and Technology, 2019, 42(3): 209-214.

[20]
QU Y H, ZHANG Y T, ZHANG Y M. A global path planning algorithm for fixed-wing UAVs[J]. Journal of Intelligent & Robotic Systems, 2018, 91(3-4):691-707.

Outlines

/