一种多车辆协同多植保无人机作业路径规划方法

doi:10.12068/j.issn.1005-3026.2024.02.019

摘要/Abstract

摘要：

在植保作业中多车辆协同多无人机能突破续航等限制，可大幅提高作业效率.针对多车辆-多植保无人机作业路径规划求解难度大等问题，建立一种多车辆协同多植保无人机路径优化模型，并以无人机最大作业时间最小化为优化目标.同时，提出改进的simulated annealing‐Lin Kernighan Helsgaun （SA-LKH）算法求解该模型.所提算法融合K-均值聚类法和凸包插入法生成初始解，利用LKH算法优化每组无人机和车辆路径.此外，构建有向扰动算子，通过扰动每次迭代过程中作业时间最大和最小的路径来实现算法的快速收敛.5种不同规模算例的结果表明，所提算法在求解质量和效率上均优于对比算法.

关键词: 车辆无人机协同, 多无人机路径规划, 车辆路径规划, 改进模拟退火算法, LKH算法

Abstract:

Multi-vehicle collaboration with multi-agricultural UAV operation can overcome limitations such as endurance and greatly improve efficiency. To address challenges in path planning for collaborative operations involving multi-vehicles and multi-agricultural UAVs， a path optimization model is constructed with the objective of minimizing the maximum operation time of UAVs. The improved simulated annealing-Lin Kernighan Helsgaun （SA-LKH） algorithm is proposed to solve the model. The proposed method combines K-means and convex hull methods to generate the initial solutions， and uses the LKH algorithm to optimize the paths of each group of UAVs and vehicles. Additionally， a directed perturbation operator is constructed to achieve rapid convergence of the algorithm by perturbing the paths with the maximum and minimum operation times during each iteration. The results of five different scale examples show that the proposed algorithm is superior to the comparative algorithm in terms of solution quality and efficiency.

Key words: vehicle and UAV collaboration, multi-UAV path planning, vehicle path planning, improved simulated annealing algorithm, LKH algorithm

中图分类号:

TB 114.1

徐金华, 汪飞, 韩飞, 李岩. 一种多车辆协同多植保无人机作业路径规划方法[J]. 东北大学学报（自然科学版）, 2024, 45(2): 296-304.

Jin-hua XU, Fei WANG, Fei HAN, Yan LI. A Method for Path Planning of Multi-vehicles Collaboration with Multi-agricultural UAVs[J]. Journal of Northeastern University(Natural Science), 2024, 45(2): 296-304.

图/表 8

图1 多车辆协同多植保无人机作业示意图

Fig. 1 Schematic diagram of multi‐vehicle collaboration with multi‐agricultural UAV operation

表1 模型符号定义

Table 1 Definition of model symbols

符号	说明	符号	说明
$U$	无人机集合， $U = 1,2, …, u$	$D j$	路径点 $j$ 农药需求量
$B$	车辆集合，车辆与无人机一一对应， $B = 1,2, …, b$ ，其中 $b = u$	$E h u$	无人机 $u$ 单位距离能耗
$O$	果树点坐标集， $O = O 1, O 2, …, O n$	$E t u$	无人机 $u$ 单位时间能耗
$R$	对接点集合， $R = r 1, r 2, …, r n$	$f m a x$	载重惩罚系数最大值
$R 0$	仓库点集， $R 0 = R 0$	$E m a x u$	无人机 $u$ 最大电量
$A$	所有点的集合， $A = O ? R ? R 0$	$Q m a x u$	无人机 $u$ 最大农药荷载
$A 0$	起点集合， $A 0 = O ? R ? R 0$	$E m a x b$	车辆 $b$ 所载可为无人机补给的最大电量
$A +$	终点集合， $A + = O ? R ? a + 1$ ，其中 $a + 1$ 为仓库点	$Q m a x b$	车辆 $b$ 所载可为无人机补给的最大农药量
$R b$	车辆 $b$ 有效对接点集，即无人机 $u$ 降落的对接点集合	$t j, k u$	无人机 $u$ 从点 $j$ 出发至离开点 $k$ 的耗时
$N b$	车辆 $b$ 的行程数， $N b = 1,2, …, n$	$T k u$	无人机 $u$ 离开路径点 $k$ 的时刻
$m r u$	无人机 $u$ 在对接点 $r$ 起飞则为1，否则为0	$T k b$	车辆 $b$ 离开路径点 $k$ 的时刻
$l r u$	无人机 $u$ 在对接点 $r$ 降落则为1，否则为0	$V u$	无人机 $u$ 飞行速度
$E k u$	无人机 $u$ 离开路径点 $k$ 时剩余电量	$V b$	车辆 $b$ 速度
$E j b$	车辆 $b$ 到达点 $j$ 可为无人机补给的剩余电量	$F u$	无人机 $u$ 农药喷洒速度
$E s u$	无人机 $u$ 的最低安全电量限值	$x j, k u$	无人机 $u$ 从点 $j$ 到点 $k$ 为1，否则为0
$Q k u$	无人机 $u$ 离开路径点 $k$ 时剩余农药量	$y j, k b, n$	车辆 $b$ 在行程n从点 $j$ 到点 $k$ 为1，否则为0
$Q j b$	车辆 $b$ 到达点 $j$ 时可为无人机补给的剩余农药量	$M$	大数
$d i, j$	点 $i$ 和点 $j$ 间距离

表1 模型符号定义

Table 1 Definition of model symbols

符号	说明	符号	说明
$U$	无人机集合， $U = 1,2, …, u$	$D j$	路径点 $j$ 农药需求量
$B$	车辆集合，车辆与无人机一一对应， $B = 1,2, …, b$ ，其中 $b = u$	$E h u$	无人机 $u$ 单位距离能耗
$O$	果树点坐标集， $O = O 1, O 2, …, O n$	$E t u$	无人机 $u$ 单位时间能耗
$R$	对接点集合， $R = r 1, r 2, …, r n$	$f m a x$	载重惩罚系数最大值
$R 0$	仓库点集， $R 0 = R 0$	$E m a x u$	无人机 $u$ 最大电量
$A$	所有点的集合， $A = O ? R ? R 0$	$Q m a x u$	无人机 $u$ 最大农药荷载
$A 0$	起点集合， $A 0 = O ? R ? R 0$	$E m a x b$	车辆 $b$ 所载可为无人机补给的最大电量
$A +$	终点集合， $A + = O ? R ? a + 1$ ，其中 $a + 1$ 为仓库点	$Q m a x b$	车辆 $b$ 所载可为无人机补给的最大农药量
$R b$	车辆 $b$ 有效对接点集，即无人机 $u$ 降落的对接点集合	$t j, k u$	无人机 $u$ 从点 $j$ 出发至离开点 $k$ 的耗时
$N b$	车辆 $b$ 的行程数， $N b = 1,2, …, n$	$T k u$	无人机 $u$ 离开路径点 $k$ 的时刻
$m r u$	无人机 $u$ 在对接点 $r$ 起飞则为1，否则为0	$T k b$	车辆 $b$ 离开路径点 $k$ 的时刻
$l r u$	无人机 $u$ 在对接点 $r$ 降落则为1，否则为0	$V u$	无人机 $u$ 飞行速度
$E k u$	无人机 $u$ 离开路径点 $k$ 时剩余电量	$V b$	车辆 $b$ 速度
$E j b$	车辆 $b$ 到达点 $j$ 可为无人机补给的剩余电量	$F u$	无人机 $u$ 农药喷洒速度
$E s u$	无人机 $u$ 的最低安全电量限值	$x j, k u$	无人机 $u$ 从点 $j$ 到点 $k$ 为1，否则为0
$Q k u$	无人机 $u$ 离开路径点 $k$ 时剩余农药量	$y j, k b, n$	车辆 $b$ 在行程n从点 $j$ 到点 $k$ 为1，否则为0
$Q j b$	车辆 $b$ 到达点 $j$ 时可为无人机补给的剩余农药量	$M$	大数
$d i, j$	点 $i$ 和点 $j$ 间距离

图2 算法流程图

Fig. 2 Algorithm flow chart

图3 路径编码示意图

Fig. 3 Schematic diagram of path coding

表2 各型号无人机性能参数

Table 2 Performance parameters of various UAVs

型号	$E m a x /$ mAh	$q m a x /$ L	$V u / (m · s - 1)$	$F / (L · s - 1)$
$U A V 1$	12 000	10	4.5	0.03
$U A V 2$	22 000	18	7.3	0.08
$U A V 3$	17 000	13	5.8	0.05
$U A V 4$	19 000	15	6.4	0.06

表2 各型号无人机性能参数

Table 2 Performance parameters of various UAVs

型号	$E m a x /$ mAh	$q m a x /$ L	$V u / (m · s - 1)$	$F / (L · s - 1)$
$U A V 1$	12 000	10	4.5	0.03
$U A V 2$	22 000	18	7.3	0.08
$U A V 3$	17 000	13	5.8	0.05
$U A V 4$	19 000	15	6.4	0.06

表3 各算法结果对比表

Table 3 Comparison of the results of different algorithms

算例编号	作业点数量	SA-LKH算法		改进差分进化算法		改进蚁群算法		改进遗传算法
算例编号	作业点数量	最大作业时间/s	运行时间/s	最大作业时间/s	运行时间/s	最大作业时间/s	运行时间/s	最大作业时间/s	运行时间/s
1	100	864.46	5.57	916.44	23.62	890.48	73.34	946.27	29.67
2	263	4 266.03	27.90	5 349.68	67.70	4 418.26	567.32	6 619.09	72.76
3	400	7 138.29	81.85	9 083.24	121.01	7 946.48	1 166.50	9 993.62	137.52
4	573	10 634.24	159.88	12 769.79	175.57	11 164.83	2 281.44	15 580.10	194.77
5	723	14 166.14	354.60	16 600.79	360.16	15 639.37	4 452.37	19 517.02	409.72

表4 各算法对比

Table 4 Comparison of different algorithms

算法		算例1	算例2	算例3	算例4	算例5	算例1	算例2	算例3	算例4	算例5
算法		总时长/s	CV/%	总时长/s	CV/%	总时长/s	CV/%	总时长/s	CV/%	总时长/s	CV/%
改进模拟退火LKH算法	UAV₁	855.18	3.37	4 225.79	6.61	6 655.99	3.14	10 570.19	1.36	13 985.17	0.89
	UAV₂	832.86		3 695.11		7 137.24		10 440.38		13 880.58
	UAV₃	801.01		4 263.97		7 069.25		10 313.21		14 166.14
	UAV₄	864.46		4 216.39		7 057.66		10 634.24		13 935.80
改进差分进化算法	UAV₁	915.40	0.26	5 349.68	0.70	9 055.40	0.16	12 763.99	0.52	16 581.56	0.08
	UAV₂	911.13		5 270.42		9 058.35		12 762.87		16 574.61
	UAV₃	916.44		5 342.99		9 051.01		12 632.48		16 597.31
	UAV₄	915.14		5 342.04		9 083.24		12 769.79		16 600.79
改进蚁群算法	UAV₁	890.48	9.59	3 121.16	15.12	7 946.48	4.88	8 305.70	13.06	15 639.37	15.36
	UAV₂	890.48		4 069.66		7 407.47		10 006.96		14 672.47
	UAV₃	862.40		4 377.73		7 092.47		11 043.61		12 109.53
	UAV₄	722.01		4 418.26		7 309.47		11 164.83		11 286.19
改进遗传算法	UAV₁	1 004.83	2.30	6 526.52	1.17	9 601.96	1.77	15 458.32	1.06	19 517.02	0.53
	UAV₂	1 035.91		6 619.09		9 993.62		15 196.03		19 341.29
	UAV₃	1 046.27		6 549.66		9 702.42		15 580.10		19 272.25
	UAV₄	997.93		6 433.94		9 866.22		15 471.29		19 378.94

图4 各算法收敛图（a）—算例1；（b）—算例2；（c）—算例3；（d）—算例4；（e）—算例5.

Fig. 4 Convergence diagram of different algorithms

参考文献 19

1	Zhang H J， Qi L， Wu Y L，et al.Numerical simulation of airflow field from a six‐rotor plant protection drone using lattice Boltzmann method［J］.Biosystems Engineering，2020，197：336-351.
2	Murray C C， Chu A G.The flying sidekick traveling salesman problem：optimization of drone‐assisted parcel delivery［J］.Transportation Research Part C： Emerging Technologies，2015，54：86-109.
3	Mathew N， Smith S L， Waslander S L.Planning paths for package delivery in heterogeneous multirobot teams［J］.IEEE Transactions on Automation Science and Engineering，2015，12（4）：1298-1308.
4	Poikonen S， Golden B.Multi‐visit drone routing problem［J］.Computers & Operations Research，2020，113：104802.
5	Othman M S B， Shurbevski A， Karuno Y，et al.Routing of carrier‐vehicle systems with dedicated last‐stretch delivery vehicle and fixed carrier route［J］.Journal of Information Processing，2017，25：655-666.
6	Lu L C， Yue T W.Mission‐oriented ant‐team ACO for min‐max MTSP［J］. Applied Soft Computing，2019，76：436-444.
7	Eldem H， Ulker E.A hierarchical approach based on ACO and PSO by neighborhood operators for TSPs solution［J］.International Journal of Pattern Recognition and Artificial Intelligence，2020，34（11）：2059039.1-2059039.33.
8	徐久强，邢佩龙，孔秋实，等.基于改进蚁群算法的双向物流路径优化［J］.东北大学学报（自然科学版），2012，33（9）：1240-1243，1252.
	Xu Jiu‐qiang， Xing Pei‐long， Kong Qiu‐shi，et al.Logistics routing optimization based on improved ant colony algorithm［J］.Journal of Northeastern University （Natural Science），2012，33（9）：1240-1243，1252.
9	Moshref‐Javadi M， Hemmati A， Winkenbach M. A comparative analysis of synchronized truck‑and‑drone delivery models［J］.Computers & Industrial Engineering，2021，162：107648.
10	Murray C C， Raj R.The multiple flying sidekicks traveling salesman problem：parcel delivery with multiple drones［J］.Transportation Research Part C：Emerging Technologies，2020，110：368-398.
11	Dell’Amico M， Montemanni R， Novellani S.Matheuristic algorithms for the parallel drone scheduling traveling salesman problem［J］.Annals of Operations Research，2020，289（2）：211-226.
12	Hu Q R， Lin Z W， Fu J Z.A new global toolpath linking algorithm for different subregions with travelling salesman problem solver［J］.International Journal of Computer Integrated Manufacturing，2022，35（6）：633-644.
13	Kirkpatrick S， Gelatt Jr C D， Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671-680.
14	朱才华，孙晓黎，李岩.站点分类下的城市公共自行车交通需求预测［J］.吉林大学学报（工学版），2021，51（2）：531-540.
	Zhu Cai‐hua， Sun Xiao‐li， Li Yan.Forecast of urban public bicycle traffic demand by station classification［J］.Journal of Jilin University（Engineering and Technology Edition），2021，51（2）：531-540.
15	杨毅，刘亚辰，刘明阳，等.一种基于凸壳的智能服务机器人路径规划算法［J］.北京理工大学学报，2011，31（1）：54-58.
	Yang Yi， Liu Ya‐chen， Liu Ming‐yang，et al. A path planning algorithm based on convex hull for autonomous service robot［J］.Transactions of Beijing Institute of Technology，2011，31（1）：54-58.
16	Helsgaun K.Solving the equality generalized traveling salesman problem using the Lin‐Kernighan‐Helsgaun algorithm［J］.Mathematical Programming Computation，2015，7（3）：269-287.
17	Carter A E， Ragsdale C T.A new approach to solving the multiple traveling salesperson problem using genetic algorithms［J］.European Journal of Operational Research，2006，175（1）：246-257.
18	周辉仁，唐万生，王海龙.基于差分进化算法的多旅行商问题优化［J］.系统工程理论与实践，2010，30（8）：1471-1476.
	Zhou Hui‐ren， Tang Wan‐sheng， Wang Hai‐long.Optimization of multiple traveling salesman problem based on differential evolution algorithm［J］.Systems Engineering：Theory & Practice，2010，30（8）：1471-1476.
19	Song B D， Park K， Kim J.Persistent UAV delivery logistics：MILP formulation and efficient heuristic［J］.Computers & Industrial Engineering，2018，120：418-428.