基于舰机协同的岛礁巡航路径规划

doi:10.12382/bgxb.2024.0505

摘要/Abstract

摘要：

为进一步提升海上巡航效率,对基于舰船和无人机动态协同的岛礁巡航路径规划问题进行研究。该问题具有舰机动态协同、时空精确耦合、离散与连续变量同时优化等复杂特点。构建一种混合整数2阶锥规划模型以最小化巡航任务完成时间,实现对舰船航行路径、无人机飞行路径及无人机起降位置等的组合优化。应用自适应大邻域搜索(Adaptive Large Neighborhood Search, ALNS)算法,设计3种破坏算子、2种修复算子及其自适应机制进行求解。基于某海域若干岛礁数据开展案例分析,证明舰机协同模式下巡航时间可减少45%以上。算例实验结果表明,ALNS算法可在90s内求解最多包含80个岛礁的算例,其求解能力和效率显著优于CPLEX求解器和两阶段启发式算法。新提出的基于舰机协同的岛礁巡航路径规划方法,为高效遂行海上维权执法任务提供了方法参考。

关键词: 岛礁巡航, 舰机协同, 路径规划, 混合整数2阶锥规划, 自适应大邻域搜索算法

Abstract:

The route planning issue for island and reef cruise based on the dynamic collaboration among ships and drones is investigated to enhance the efficiency of maritime cruise. The issue is characterized by the dynamic cooperation among ships and drones, the precise spatio-temporal coupling, and the simultaneous optimization of discrete and continuous variables. Accordingly, a mixed-integer second-order cone programming model to minimize the mission completion time is developed for a combined optimization of the ship navigation path, the drone flight trajectory, and the drone takeoff and landing positions. The adaptive large neighborhood search (ALNS) algorithm is applied to design three destruction operators, two repair operators, and their adaptive mechanisms. A case analysis is conducted based on data from several islands and reefs in a specific maritime area, demonstrating that the cruise time can be reduced by more than 45% under the ship-drone coordination mode. The computational results indicate that the ALNS algorithm can solve the instances with up to 80 islands and reefs within 90 seconds, significantly outperforming the CPLEX solver and the two-stage heuristic algorithm in terms of solution quality and efficiency. The proposed route planning method for island and reef cruise based on ship-drone collaboration provides a reference for efficiently conducting maritime rights protection and law enforcement missions.

Key words: island and reef cruise, ship-drone collaboration, route planning, mixed-integer second-order cone programming, adaptive large neighborhood search algorithm

中图分类号:

E917

张闯, 卫超强, 李延通, 喻妍, 刘锦超. 基于舰机协同的岛礁巡航路径规划[J]. 兵工学报, 2025, 46(5): 240505-.

ZHANG Chuang, WEI Chaoqiang, LI Yantong, YU Yan, LIU Jinchao. Ship-drone Collaboration Routing for Island and Reef Cruise[J]. Acta Armamentarii, 2025, 46(5): 240505-.

图/表 9

图1 舰机协同巡航示意图

Fig.1 Illustration of ship-drone collaborative cruise

表1 决策变量定义

Table 1 Definition of decision variables

变量	定义
e_i	巡航岛礁i的无人机起飞点
l_i	巡航岛礁i的无人机降落点
x_ij	0-1变量,1表示舰船巡航岛礁i后立刻前往岛礁j巡航,否则为0
D_ij	舰船从岛礁i的降落点l_i到岛礁j的起飞点e_j之间的航行距离
$t s i$	舰船巡航岛礁i时,从起飞点e_i到降落点l_i之间的航行时间
$t i e$	无人机从起飞点e_i飞抵岛礁i的飞行时间
$t i l$	无人机从岛礁i返回降落点l_i的飞行时间
T_i	无人机到达岛礁i的时间
T_max	单次巡航的任务完成时间

表1 决策变量定义

Table 1 Definition of decision variables

变量	定义
e_i	巡航岛礁i的无人机起飞点
l_i	巡航岛礁i的无人机降落点
x_ij	0-1变量,1表示舰船巡航岛礁i后立刻前往岛礁j巡航,否则为0
D_ij	舰船从岛礁i的降落点l_i到岛礁j的起飞点e_j之间的航行距离
$t s i$	舰船巡航岛礁i时,从起飞点e_i到降落点l_i之间的航行时间
$t i e$	无人机从起飞点e_i飞抵岛礁i的飞行时间
$t i l$	无人机从岛礁i返回降落点l_i的飞行时间
T_i	无人机到达岛礁i的时间
T_max	单次巡航的任务完成时间

图2 某海域部分岛礁位置

Fig.2 Locations of some islands in certain sea

表2 岛礁基本信息

Table 2 Basic information of the islands

岛礁编号	横坐标/km	纵坐标/km	巡航用时/h
0	0	0	0
1	-197.17	132.30	0.4
2	-327.19	-21.30	1
3	-333.57	-97.65	0.3
4	-165.35	70.6	0.2
5	-174.04	-3.21	0.3
6	-37.69	20.68	0.2
7	44.86	-93.34	0.6
8	31.58	97.26	0.5

表3 岛礁巡航次序及无人机起降坐标

Table 3 Cruise sequences and taking-off and landing coordinates

岛礁编号	巡航次序	起飞点坐标/km	降落点坐标/km
1	3	(-133.726,60.2535)	(-210.335,37.2061)
2	4	(-240.691,21.8868)	(-304.445,-26.439)
3	5	(-297.97,-28.0287)	(-219.641,-44.2956)
4	2	(-65.0645,68.3311)	(-125.316,61.2429)
5	6	(-198.434,-48.2265)	(-135.202,-59.9624)
6	7	(-113.286,-64.0247)	(-35.0724,-78.5233)
7	8	(-26.0274,-80.2001)	(3.31619,-6.89998)
8	1	(1.77129,12.3396)	(-54.0718,69.6244)

图3 舰机协同巡航过程示意图

Fig.3 Ship-drone collaborative cruise process

图4 关键参数计算结果

Fig.4 Computational results of key parameters

表4 常规算例组计算结果

Table 4 Computational results of common-sized instances

n	目标函数值			计算时间
n	CPLEX算法	TSH算法	ALNS算法	CPLEX算法	TSH算法	ALNS算法
5	15.35	15.35	15.35	0.49	0.01	2.16
10	20.78	20.78	20.77	269.79	24.19	8.51
15	26.52	26.42	26.55	3600.11	3600.03	30.98
20	31.13	32.12	29.80	3601.72	3603.34	102.05
25	37.65	36.52	32.47	3600.26	3600.18	308.50
30	54.34	48.37	38.76	3600.54	3600.39	1019.70
35	81.61	71.70	42.89	3600.54	3600.47	300.77
40	97.43	87.33	48.12	3600.77	3600.44	430.56
45	109.55	110.32	51.51	3600.89	3600.33	2070.16
50	110.75	109.77	57.08	3606.08	3603.68	2924.52
均值	58.51	55.87	36.33	2908.12	2883.31	719.79

表5 拓展算例组计算结果

Table 5 Computational results of extensive-sized instances

n	可行解数量/个			目标函数值/h
n	CPLEX	TSH	ALNS	CPLEX	TSH	ALNS
55	5	5	5	128.72	128.72	61.67
60	4	4	5	150.62	150.62	65.31
65	3	4	5	143.32	139.32	73.77
70	1	4	5	136.82	164.97	76.78
75	0	1	5	—	148.69	79.39
80	0	0	5	—	—	85.02
均值	2.17	3.00	5.00	—	—	73.66

参考文献 25

[1]	李延通, 张闯, 汤莲花. 母舰-舰载机协同路径规划问题研究综述[J]. 控制与决策, 2025, 40(2):387-403.
	LI Y T, ZHANG C, TANG L H. Review on mothership-vehicle collaborative routing problem[J]. Control and Decision, 2025, 40(2):387-403. (in Chinese)
[2]	LIU B L, WANG Y D, LI Z C, et al. An exact method for vessel emission monitoring with a ship-deployed heterogeneous fleet of drones[J]. Transportation Research Part C, 2023, 153:104198.
[3]	侯云霞. 船载无人机协同监测港口船舶大气污染路径规划[D]. 大连: 大连海事大学, 2022.
	HOU Y X. Synergistic path planning for ship-deployed multiple UAVs to monitor vessel pollution in ports[D]. Dalian: Dalian Maritime University, 2022. (in Chinese)
[4]	SHEN L X, HOU Y X, YANG Q. Synergistic path planning for ship-deployed multiple UAVs to monitor vessel pollution in ports[J]. Transportation Research Part D, 2022, 110:103415.
[5]	LI Y T, WANG X Q, ZHANG S, et al. Vessel-UAV collaborative routing problem for offshore oil and gas fields inspection[C]//Proceedings of 2023 IEEE International Conference on Networking, Sensing and Control. Marseille, France:IEEE, 2023.
[6]	TANG L H, LI Y T. A new formulation for the multi-period vessel-drone routing problem[C]//Proceedings of 2023 IEEE International Conference on Networking, Sensing and Control. Marseille, France:IEEE, 2023.
[7]	LI Y T, WANG S J, ZHOU S S, et al. A mathematical formulation and a tabu search heuristic for the joint vessel-UAV routing problem[J]. Computers & Operations Research, 2024,169:106723.
[8]	XUE G Q, LI Y T, WANG Z. Vessel-UAV collaborative optimization for the offshore oil and gas pipelines inspection[J]. International Journal of Fuzzy Systems, 2023, 25(1): 382-394.
[9]	AMOROSI L, PUERTO J, VALVERDE C. Coordinating drones with mothership vehicles: the mothership and drone routing problem with graphs[J]. Computers and Operations Research, 2021, 136: 105445.
[10]	AMOROSI L, PUERTO J, VALVERDE C. A multiple-drone arc routing and mothership coordination problem[J]. Computers and Operations Research, 2023, 159:106322.
[11]	ZHANG X P, ZHANG F R, TANG Z. A MILP model on coordinated coverage path planning system for UAV-ship hybrid team scheduling software[J]. The Journal of Systems & Software, 2023, 206:111854.
[12]	朱益民. 多无人机舰机协同任务分配[D]. 合肥: 合肥工业大学, 2016.
	ZHU Y M. Cooperative task allocation method for ship and UAVs[D]. Hefei: Hefei University of Technology, 2016. (in Chinese)
[13]	马华伟, 朱益民, 胡笑旋. 基于粒子群算法的无人机舰机协同任务规划[J]. 系统工程与电子技术, 2016, 38(7):1583-1588.
	MA H W, ZHU Y M, HU X X. Cooperative task planning for ship and UAVs based on particle swarm optimization algorithm[J]. Systems Engineering and Electronics, 2016, 38(7):1583-1588. (in Chinese) doi: 10.3969/j.issn.1001-506X.2016.07.16
[14]	XIA J, WANG K, WANG S A. Drone scheduling to monitor vessels in emission control areas[J]. Transportation Research Part B: Methodological, 2019, 119:174-196.
[15]	ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4):455-472.
[16]	REN X, HUANG H, FENG S, et al. An improved variable neighborhood search for bi-objective mixed-energy fleet vehicle routing problem[J]. Journal of Cleaner Production, 2020, 275: 124155.
[17]	SUKSEE S, SINDHUCHAO S. GRASP with ALNS for solving the location routing problem of infectious waste collection in the Northeast of Thailand[J]. International Journal of Industrial Engineering Computations, 2021, 12(3): 305-320.
[18]	RAHIMI S K, RAHIMI D. An improved ALNS for hybrid pickup and drones delivery system in disaster by penalizing deprivation time[J]. Computers & Operations Research, 2024,170: 106722.
[19]	CHANG X N, SHI J M, LUO Z H, et al. Adaptive large neighborhood search algorithm for multi-stage weapon target assignment problem[J]. Computers & Industrial Engineering, 2023, 181:109303.
[20]	MARA S T W, NORCAHVO R, JODIAWAN P, et al. A survey of adaptive large neighborhood search algorithms and applications[J]. Computers & Operations Research, 2022,146:105903.
[21]	GUILMEAU T, CHOUZENOUX E, ELVIRA V. Simulated annealing: a review and a new scheme[C]// Proceedings of 2021 IEEE Statistical Signal Processing Workshop. Rio de Janeiro, Brazil: IEEE, 2021: 101-105.
[22]	CHANG Z, CHEN H X, YALAOUI F, et al. Adaptive large neighborhood search algorithm for route planning of freight buses with pickup and delivery[J]. Journal of Industrial and Management Optimization, 2021, 17(4):1771-1793.
[23]	GARONE E, NALDI R, CASAVOLA A, et al. Planning algorithms for a class of heterogeneous multi-vehicle systems[J]. IFAC Proceedings Volumes, 2010, 43(14):969-974.
[24]	GAMBELLA C, LODI A, VIGO D. Exact solutions for the carrier-vehicle traveling salesman problem[J]. Transportation Science, 2018, 52(2):320-330.
[25]	WEN X P, WU G H. Heterogeneous multi-drone routing problem for parcel delivery[J]. Transportation Research Part C, 2022, 141: 103763.