Ship-drone Collaboration Routing for Island and Reef Cruise

doi:10.12382/bgxb.2024.0505

Abstract

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

CLC Number:

E917

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-.

Figures/Tables 9

Fig.1 Illustration of ship-drone collaborative cruise

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	单次巡航的任务完成时间

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	单次巡航的任务完成时间

Fig.2 Locations of some islands in certain sea

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

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)

Fig.3 Ship-drone collaborative cruise process

Fig.4 Computational results of key parameters

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

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

References 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.