无人机在边境勘测中的路径优化问题研究

A Study of the Path Optimisation Problem of Unmanned Aerial Vehicles in Border Survey

摘要: 使用复合翼无人机实施边境勘测，已经成为部分边防部队边境勘测的重要手段。采用无人机进行边境勘测，极大提高了作业效率，实现高山、河流、雪地等恶劣艰苦环境的巡逻，尤其对担负新疆、西藏边防线上的巡逻任务来说，无人机代替分队巡逻、勘测具有重要意义。针对无人机对边防线上多个边境目标实施勘测时的路径优化问题，本文通过建立数学模型，在人工蜂群算法(Artificial Bee Colony Algorithm, ABC)、模拟退火算法(Simulated Annealing, SA)、遗传算法(Generation Algorithm, GA)、蚁群算法(Ant Colony Algorithm, ACA)等智能算法基础上进行优化，尝试采用头脑风暴优化算法(Brain Storm Optimization Algorithm, BSO)进行路径优化，并仿真实验求解，通过对求解结果、收敛度进行综合分析，得出BOS算法较其他算法收敛度较好，路径更优化，极大节省了巡逻时间、提高作业效率、为当前部分队采用无人机进行边境勘测的路径优化问题提供新方法。

Abstract: The use of composite-winged drones to carry out border surveys has become an important means of border surveys for some border defence forces. The use of UAVs to carry out border surveys greatly improves operational efficiency and achieves the patrolling of harsh and difficult environments such as high mountains, rivers, snow, etc. Especially for patrolling tasks on the borderline of Xinjiang and Tibet, UAVs are of great significance, unlike detachment patrolling and surveying. This paper addresses the path optimization problem for unmanned aerial vehicles (UAVs) conducting surveys on multiple border targets along the border defense line. By establishing a mathematical model, we optimize the problem based on various intelligent algorithms, including the Artificial Bee Colony Algorithm (ABC), Simulated Annealing (SA), Genetic Algorithm (GA), and Ant Colony Algorithm (ACA). Additionally, we explore path optimization using the Brain Storm Optimization Algorithm (BSO) and conduct simulation experiments for problem-solving. Through a comprehensive analysis of the results and convergence performance, we find that the BSO algorithm demonstrates better convergence and more optimized paths compared to the other algorithms, significantly reducing patrol time and enhancing operational efficiency. This provides a new approach to the path optimization issue for UAVs used in border surveying in some current units.

1. 概述

在近期发生的纳卡冲突、俄乌战争和巴以冲突等军事对抗中，多种类型无人机(Unmanned Aerial Vehicles, VAVs)出现在战场中，执行多种任务。比如俄乌冲突中，俄军调配“海鹰”-10、“海鹰”-30、“前哨”、“石榴”等无人机，用于侦察、火力校射等任务，开辟了大规模、高强度的无人战场；巴以冲突中，哈马斯武装组织利用无人机对以色列的“梅卡瓦4M”主战坦克发动攻击，出现了世界上第一个装备有主动防御系统的先进主战坦克被无人机击毁的案例。无人机在战争中发挥着越来越重要的作用，其应用范围涵盖了侦察与监视、通信中继、打击目标、电子战等多个方面。随着技术的不断进步，无人机在军事领域的应用更加广泛和深入，在日常分队执勤、边境勘测中也将发挥重要意义。

对于边海防分队，常年驻守在高山海岛等艰苦恶劣地形条件下，不利于分队执行边境勘测任务，无人机可搭载高清摄像头和激光雷达等设备，快速获取边境地区的高精度地形数据，这些数据对于边境管理、军事防御和自然资源管理等方面都具有重要意义；对边境区域可进行实时监控，并通过高空悬停和长航时能力，可持续监测边境线的动态，及时发现非法越境、走私和偷渡等违法活动。与传统的人力步行勘测、骑马探测等方式相比，无人机勘测具有成本较低、覆盖区域较广、灵活性较强、采集数据较准确、效率较高等优点。当前，在遂行多目标边境勘测任务中，通常使用复合翼侦察无人机实施现地勘测，对于多目标勘测，如何实施勘测路径优化问题需要进一步进行关注和研究，以进一步提高勘测效率、缩短侦察时间，达到抢占先机的目的。

2. 建立数学模型

2.1. 基本模型的建立

无人机在边境勘测的路径优化问题，可参考旅行商问题(Traveling Salesman Problem，简称TSP)加以分析。

2.1.1. TSP问题

旅行商问题(又称货郎担问题)，可描述为：有一人员去各地配送货物，从城市M₁出发，要遍访城市$M_2,M_3,M_4,\cdots ,M_n$ 各一次，最后返回到城市M₁，其中M_i到M_j的旅费为V_ij，按照怎样的次序访问这些城市，才能使总旅费最少。

定义变量X_ij表示人员是否从城市M_i卖货后去城市M_j，

$x_{ij}=\{\begin{array}{ll}1\hfill & 人��城市M_i��后去城市M_j\hfill \\ 0\hfill & 人��城市M_i��后不去城市M_j\hfill \end{array}$

定义总费用为Z：

$\min z={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{v}_{ij}{x}_{ij}}}$

人员在遍访城市售货时，为防止出现子回路，需要附加约束：

$w_i-w_j+n{x}_{ij}\le n-1$ , $i=1,\cdots ,n$ , $j=2,\cdots ,n$

$w_1=0$ , $1\le w_i\le n-1$ , $i=2,3,\cdots ,n$

建立数学模型：

$\begin{array}{l}\min z={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{v}_{ij}{x}_{ij}}}\\ \text{s}\text{.t}.\{\begin{array}{l}{\displaystyle \sum _{j=1}^n{x}_{ij}}=1,j=1,2,\cdots ,n\\ {\displaystyle \sum _{i=1}^n{x}_{ij}}=1,i=1,2,\cdots ,n\\ w_i-w_j+n{x}_{ij}\le n-1,i=1,2,\cdots ,n;j=2,3,\cdots ,n\\ w_1=0,1\le w_i\le n-1,i=2,3,\cdots ,n\\ x_{ij}=0或\text{1}，\end{array}\end{array}$

2.1.2. TSP问题目前研究现状

TSP问题作为一个经典的组合优化问题，在规模较小，计算量较少的情况下可采用精确、近似算法，例如可采用线性规划、分支定界算法，但此方法不适用规模较大、计算量大的情况。后期发展采用混合人工蜂群算法(Artificial Bee Colony Algorithm, ABC)、模拟退火算法(Simulated Annealing, SA)、遗传算法(Generation Algorithm, GA)、蚁群算法(Ant Colony Algorithm, ACA)等智能算法进行优化，王港华对物流配送类小规模TSP问题的遗传算法求解进行了研究，王珺研究了基于模拟退火算法的民航运输路径优化技术，孙鉴等人提出了基于Spark的并行模拟退火算法求解TSP的方法[1]。本文对无人机的多目标边境勘测任务的路径优化问题，尝试采用头脑风暴优化算法(BSO)求解，并进行收敛度分析，得出无人机对边境目标实施勘测的路径优化问题的最优解。

2.2. 头脑风暴优化算法(BSO)

头脑风暴优化算法的灵感来自于人类社会性活动(头脑风暴)，遵循延迟评判、自由畅想、以量求质和综合改善原则的智能优化算法[2] [3]。以求解问题过程为原型，抽象成优化算法。其被广泛应用于解决多方面问题，如机器人协作问题[4]、数值优化问题[5]、缓存优化问题[6]等，算法流程图见图1。

Figure 1. Flowchart of brainstorming optimisation (BSO) algorithm [7]

图1. 头脑风暴优化(BSO)算法流程图[7]

3. 算例与结果分析

3.1. 问题描述

某边防分队根据上级任务部署，对C国与H国某段边境线之间的22个重点勘测目标(以距离分队战立点最近的点O为坐标原点，其余坐标为其相对距离，见表1、图2)进行勘测，形成边境勘测报告，为指挥员判断边境情况提供有利实际情报支撑。该边防分队携带复合翼侦察无人机已抵达原点O (0, 0)，该复合翼侦察无人机电池完好、电量充足，可持续工作4小时，假设无论采取何种路线勘测，均能在4小时之内完成任务并回到原点；该无人机可飞行高度大于勘测地的山脉高度，且均能按上级要求完成对重点目标的勘测。无人机分队应如何选择勘测路径，使得无人机勘测路径最短，较快完成边境勘测任务。

Table 1. Information on the coordinates of points to be surveyed along a borderline

表1. 某边境线需勘测点坐标信息表

序号	1	2	3	4	5	6	7	8	9
X坐标	0	1000	725	1127	1105	655	1203	1235	1686
Y坐标	0	525	1108	1758	2900	3125	3750	4803	5608
序号	10	11	12	13	14	15	16	17	18
X坐标	2203	2255	2304	3525	3728	4568	4672	6234	6783
Y坐标	5650	5050	5955	6050	5734	5487	6375	6735	5102
序号	19	20	21	22	23
X坐标	7593	7421	6893	7458	5374
Y坐标	3795	2232	1537	328	423

Figure 2. Distribution of points to be surveyed along a borderline

图2. 某边境线需勘测点分布图

3.2. 根据TSP问题模型建立数学模型

边防分队需利用复合翼无人机对重点目标完成勘测任务，假设对n个目标实施边境勘测，每两个目标点之间距离为d_ij ($i,j=1,2,\cdots ,n$ ；且$i\ne j$ )，求从点O (0, 0) (以出发点为原点，正东方向为x轴，正北为y轴)出发，遍历所有目标点有且仅有1次后回到出发点O (0, 0)的最短距离。

建立数学模型如下：

$\begin{array}{l}\min f={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{d}_{ij}{x}_{ij}}}\text{ (1)}\\ \text{s}\text{.t}.\{\begin{array}{ll}{d}_{ij}=\sqrt{{\left(x_j-x_i\right)}^2+{\left(y_j-y_i\right)}^2},i\ne j,i\in V,j\in V\hfill & \text{ (2)}\hfill \\ {\displaystyle \sum _{j=1}^n{x}_{ij}}=1,i\in V\hfill & \text{ (3)}\hfill \\ {\displaystyle \sum _{i=1}^n{x}_{ij}}=1,j\in V\hfill & \text{ (4)}\hfill \\ {\displaystyle {\sum }_{j=s}{\displaystyle {\sum }_{j\in s}{x}_{ij}}}\le \left|s\right|-1,\forall s\subset V,2\le \left|s\right|\le n-1\hfill & \text{ (5)}\hfill \\ x_{ij}\in \left\{0,1\right\}\hfill & \text{ (6)}\hfill \end{array}\end{array}$

(1) 是目标函数，即从第一个点O (0, 0)出发，遍历n个点后回到点O (0, 0)的最短距离；(2) d_ij为第i点到第j点的欧氏距离；(3)、(4)为无人机经过每一个点有且仅有一次；(5) 无人机不能重复经过任何一个点(出发点除外)；(6)无人机经过某一点该点状态改为1，否则为0。V为所有点的序号集合；s为第2个点到n − 1点。

3.3. 利用BSO算法求解

采用最大迭代次数为100，种群为50，聚类数目为5，随机替换一个聚类中心的概率为0.1，选择1个聚类的概率0.5，选择两个聚类的概率0.5，选择1个聚类中心的概率0.3，选择两个聚类中心的概率0.2。Matlab核心代码见图3~6。

Figure 3. Core code 1

图3. 核心代码1

Figure 4. Core code 2

图4. 核心代码2

Figure 5. Core code 3

图5. 核心代码3

Figure 6. Core code 4

图6. 核心代码4

仿真实验结果如下：

第1代最优个体的总距离为62877.7623米；第2代最优个体的总距离为52868.493米；第3代最优个体的总距离为47296.452米；第4代最优个体的总距离为37711.8539米；第5代最优个体的总距离为36353.5003米；第6代最优个体的总距离为33812.3365米；第7代最优个体的总距离为30332.3101米；第8代最优个体的总距离为30332.3101米；第9代最优个体的总距离为29102.3541米；第10代最优个体的总距离为29102.3541米；第11代最优个体的总距离为29102.3541米；第12代最优个体的总距离为29007.5297米；第13代最优个体的总距离为28331.8461米；第14代最优个体的总距离为28331.8461米；第15代至第100代最优个体的总距离均为27995.9277米，BSO的收敛度图、路由图见图7、图8。

Figure 7. Convergence plot of the brainstorming optimisation algorithm BSO

图7. 头脑风暴优化算法BSO的收敛度图

Figure 8. Routing diagram of brainstorming optimisation algorithm BSO

图8. 头脑风暴优化算法BSO的路由图

根据仿真实验结果，无人机最优勘测路径为从原点O (0, 0)出发，沿着勘测点3 → 4 → 5 → 6 → 7 → 8 → 9 → 11 → 10 → 12 → 13 → 14 → 15 → 16 → 17 → 18 → 19 → 20 → 21 → 22 → 23 → 2 → 1，使得无人机勘测路径最短，为27995.9277米，能够较快完成边境勘测任务。从BOS收敛度图可以看出其收敛度较好，迭代到15代就能算出结果。利用BOS算法能较快解决当前部队使用无人机对边境多目标勘测时的路径优化问题，尤其在高山海岛、不良天候等恶劣环境不便于人工勘测时，极大地提高了边境勘测效率；节省大量资源。