多无人机高速公路巡逻任务规划方法

项 芮，朱默宁,3*，徐 丽

(1.合肥工业大学 管理学院，安徽 合肥 230009；2.安徽有云智能科技有限公司，安徽 合肥 230088；3.智能互联系统安徽省实验室，安徽 合肥 230009)

0 引言

近年来，全国高速公路的通车里程迅速增长，导致交通管理短缺与人力需求增长的矛盾日益凸显[1-2]。目前，交通主管部门通常采用常规人工巡逻和固定摄像头等方式获取高速公路的实时信息。然而，现有的高速公路巡逻方式存在着里程长、盲区多、效率低的缺点，比如固定摄像头无法实现全路段覆盖，常规的人工巡逻需要占用本已十分有限的道路资源，且难以快速到达事故现场并获取实时的事故信息。一旦高速公路上发生交通事故等紧急事件，易导致长时间堵车，交警难以快速到达现场进行指挥，若处置不当很容易引发二次事故[3]。无法及时到达现场进行路段指挥工作给应急管理工作带来了极大的困难。因此，如何满足当前日渐增长的高速公路交通管理需求是高速公路巡逻的一大难题。

无人机是一种环境适应性和可扩展性较强的传感平台[4]，具有远程自主飞行、道路抓拍、定点悬停和实时语音通信等功能，被广泛应用于交通巡逻领域[5]。相较于常规的人工巡逻，使用无人机巡逻高速公路具有以下的明显优势：不受交通流量影响，不会占用道路资源，且能够实时回传道路现场的视频和图像,有利于道路管理部门通盘指挥和疏导交通[6]。通过无人机实时传输视频、图像和语音等信息可以让交警快速勘察现场情况，提高巡检过程的安全性。无人机还可携带喊话器来指挥交通实现短时间内恢复通车，可以加速现场撤离，降低警力投入。综上所述，以无人机编队高速公路巡逻为导向的巡逻模式可以有效提升路况信息服务水平和快速处理高速公路突发事件。在实际应用中，当面对若干不同类型的巡逻任务时，如何规划无人机编队的巡逻路径，使得巡逻效益最大化，成为亟待解决的问题之一。

本文面向城市高速公路交通巡逻场景，研究了无人机编队的任务规划问题。城市高速公路的巡逻指挥任务主要包括事故多发点巡逻、电子眼盲区巡逻和道路堵塞疏导等，其中一部分任务可以由无人机完成。对无人机进行巡逻任务规划的过程可以描述为：先将日常巡逻任务抽象成若干个需要无人机遍历的点目标，将需要进行交通指挥的任务路段抽象成若干个线目标；然后将这些点目标和线目标分派给不同的无人机，通过优化无人机的巡逻路径，以最小的总成本遍历所有的任务目标。为了解决本文提出的无人机编队高速巡逻任务，引入旅行商问题(Travelling Salesman Problem，TSP)模型，将问题抽象为无人机编队从多个停机坪出发，完成对指定任务目标的遍历后返回出发停机坪的问题。该问题可以看作多站点TSP和固定终点旅行商问题的结合，即多站点固定终点的多旅行商问题(Multi-Depot Fixed Destination Multi Travelling Salesman Problem，MD-FD-MTSP)模型。

TSP已被证明是非确定性多项式难(Non-Deterministic Polynomial Hard，NP-Hard)问题，本文所研究的MD-FD-MTSP是TSP的变体问题，所以也是NP-Hard问题。遗传算法及其混合算法是解决TSP及其变体问题最先进的启发式算法之一，并被广泛应用于工程实践中[7]。因此，根据多无人机高速巡逻任务的特点，针对MD-FD-MTSP模型设计了改进的单亲遗传算法(Improved Partheno-Genetic Algorithm，IPGA)，得到每架无人机的可飞路径，并通过对比实验展示了算法的性能。

1 相关工作

1.1 无人机道路巡检

近些年，国内外诸多学者对无人机在交通巡逻领域上的应用进行了深入研究。一些学者[8-9]提出了基于无人机巡检的城市交通流状况的评价方法，并分析了无人机数量和城市中汽车数量的变化对于算法求解效率的影响。相关研究[10-11]利用无人机获取中国主要十字路口的监控录像，基于路网搜索路径规划算法解决无人机自主搜索任务的任务规划问题。为了更高效地利用无人机所采集的影像数据，有学者[12-13]对如何基于无人机图像自动提取高精度的道路信息进行了研究。

1.2 多旅行商问题

多旅行商问题(Multiple Traveling Salesman Problem,MTSP)是TSP的推广，在TSP的解决方案中使用了1个以上的旅行商[14]。MTSP同样属于NP-Hard问题,通常被定义为：给定m位旅行商从n个城市集合中的1个城市出发，各自访问其中一定数量的城市后回到出发城市，且每个城市只需要被访问一次[15]。目标为找到距离或时间等代价最小的任务分配方案以及访问次序。

文献[16]将MTSP分为以下2种类型：开放路径旅行商问题和封闭路径旅行商问题。本文研究的问题属于封闭路径旅行商问题的一种变体：m架无人机从m个不同停机坪出发，访问一定数量的任务目标，使得每个任务目标必须被1架无人机访问且只能访问1次，最后返回出发的停机坪。

1.3 启发式求解算法

目前应用于解决MTSP的相关算法主要有精确算法和启发式算法。尽管精确算法有着严格的数学理论支持，但随着算例规模的扩大，精确算法难以高效地求解MTSP。因此学者们逐渐倾向于采用启发式算法或元启发算法求解MTSP[17]，如粒子群算法[18]、蚁群算法[19]和遗传算法[20]。Laporte[21]提出了遗传算法，一些学者[22-24]利用遗传算法求解了多机协同侦察问题，并将其建模为MTSP。遗传算法因其良好的全局搜索能力而被广泛用于解决工程中的优化问题。一般的遗传算法主要通过交叉算子获得新的个体。然而，2个相同的个体不能通过交叉获得新的个体导致算法陷入局部最优[25]。因此，一般的遗传算法需要足够的初始种群多样性，否则算法会陷入局部最优，无法在找到全局最优方案之前产生新个体。而大量的初始种群必然会降低算法的计算效率。单亲遗传算法(Partheno-Genetic Algorithm,PGA)是一种没有交叉操作的特殊遗传算法[26]。有学者[22]提出了2种PGA，以解决多起点、封闭路径的MTSP，并将PGA与粒子群优化算法和入侵杂草优化算法进行了比较，证明了PGA的计算效率更高，且不会破坏父代染色体的基因组合。

2 问题描述

本文所研究的多无人机高速巡逻任务规划问题以高速公路为应用背景。无人机的巡逻任务分为2类：一类将任务抽象成点目标，无人机只要飞过任务点上方即视为完成了巡逻任务；另一类将任务抽象为线目标，无人机需携带喊话器对高速公路的某一路段进行指挥。假设停机坪的数量不少于无人机的数量，每架无人机选择1个停机坪出发，访问若干任务点或任务路段后返回各自出发的停机坪。每个任务点或任务路段只需要访问1次，要求所有无人机的巡逻路径总长度最短。将多无人机高速巡逻任务规划问题建模为MD-FD-MTSP模型，即K架无人机从不同的停机坪出发，共同完成由Z个点目标和W个线目标组成的任务集合，最后返回各自停机坪。

2.1 无人机

2.2 异构巡逻任务描述

在无人机执行高速巡逻任务过程中，由于无人机的续航能力有限，执行完异构巡逻任务的无人机需降落在原停机坪补充电量。考虑到操作的安全性和便捷性，本文规定每个停机坪至多只能安排1架无人机起飞和降落。

2.3 高速道路路网描述

由于点目标与线目标分布在城市高速公路路网中，且无人机编队需沿着路网执行任务。用连通图G=(V,E)来表示高速公路路网，其中，点集合V={V0,V1,…,VN}表示道路之间的交叉点，交叉点的数量为N。无人机在飞行过程中需要不断做出决策，将每次决策的出发点记作VS={V0,V1,…,VV-1}，将每次决策的目标节点记作VE={V1,V2,…,VV}，其中V0等价于VV。无人机巡检的任务路段即为连通图G的边集合E={eij=(Vi,Vj)}的子集，每条边的长度为dij，路网中共有M条边。

表1列出了本文所用到的相关集合、参数和变量。

2.4 数学模型

针对MD-FD-MTSP，以所有无人机巡逻路径的总长度最小作为优化目标，建立如下数学模型：

(1)

约束条件为：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(1)的目标函数表示多无人机执行巡逻任务的总路程长度最小化；式(2)保证路网中所有节点的流量守恒，即入度等于出度；式(3)和式(4)保证1个停机坪有且仅有1架无人机进行起降；式(5)为无人机的续航能力约束；式(6)保证每个线目标被且仅被1架无人机访问1次；式(7)保证每个点目标被且仅被1架无人机访问1次；式(8)是所有决策变量的取值。

3 改进的单亲遗传算法

IPGA的主要思想是：将待求解问题的解决方案转换为编码的形式，首先随机生成种群规模大小的个体作为父代，基于适应度函数评估每一个个体的适应度；选择出适应度较高的一些个体执行单亲遗传操作,生成和父代种群数量相同的子代种群；对子代种群进行新一轮的迭代，周而复始,达到预先设定的迭代次数为止[22]。图1给出了IPGA流程。

图1 IPGA流程Fig.1 Flow chart of IPGA

IPGA的伪代码如下：

改进的单亲遗传算法(IPGA)输入:待求解的MD-FD-MTSP输出:OptPath,算法求得的任务规划方案开始种群初始化(详见3.3)适应度评价(详见3.2)While 不满足算法结束条件 单亲遗传操作(详见3.4) 种群更新(详见3.5)EndwhileIPGA所求得的最佳任务分配方案

3.1 染色体编码方式

本文采用基于巡逻任务序号的整数编码加设置断点的方式对染色体进行编码，即用2个向量表示1条染色体，其中，向量1是所有目标编号的1个随机排列，向量2是随机设置的断点位置。1条染色体代表MTSP的1个可行路径规划方案。现有3架无人机和5个任务点，3条任务路段编码方式如图2所示。

图2 IPGA染色体编码示意Fig.2 Schematic diagram of IPGA chromosome coding

图2所示的染色体表示的无人机编队巡逻路径方案可描述为：第1架无人机从停机坪出发，依次巡逻编号为8的点任务和端点为3,4的线任务后返回其出发的停机坪；第2架无人机从停机坪出发，依次巡逻编号为1，2的点任务后返回其出发的停机坪；第3架无人机从停机坪出发，依次巡逻端点为9,10的线任务,编号为10的点任务，端点为5,6的线任务和编号为7的点任务后返回其出发的停机坪。图2所示的染色体编码的巡逻方案示意图如图3所示。

图3 巡逻方案示意Fig.3 Schematic diagram of patrol scheme

3.2 适应度评价

多无人机高速巡逻任务分配方案的优劣可以由适应度值来衡量，方案越优则其适应度值越大。所以选择MD-FD-MTSP的目标函数作为IPGA的适应度函数，所有无人机的路径长度之和越小，则其适应度值越大。

3.3 种群初始化

种群初始化步骤如下：

① 将异构巡逻任务集合中的编号随机排列得到一个序列H，其中线任务用线段两端的端点表示；

② 根据无人机数量K随机设置K-1个中断点，从而将序列H分成K段，确定每个无人机应该执行的巡逻任务；

③ 根据预设的种群规模分别重复步骤①～②并存入矩阵，得到初始种群。

3.4 单亲遗传操作

交换算子：随机选取3个基因位s，t和p，将s和t基因位上的编号进行交换，然后将交换后的s和t之间的基因片段插入到基因位p的前面。具体过程如图4所示。

图4 交换算子示意Fig.4 Schematic diagram of SwapInsert operator

反转算子：随机选取3个基因位s，t和p，将s和t基因位之间的目标编号进行反转，然后将反转后的s和t之间的基因片段插入到基因位p的前面。具体过程如图5所示。

图5 反转算子示意Fig.5 Schematic diagram of FlipInsert operator

左旋算子：随机选取3个基因位s，t和p，将s和t基因位之间的目标编号全部向左移动1位，最前面一位的目标编号移动到最后面一位，然后将左旋后的s和t之间的基因片段插入到基因位p的前面。具体过程如图6所示。

图6 左旋算子示意Fig.6 Schematic diagram of LslideInsert operator

右旋算子：随机选取3个基因位s，t和p，将s和t基因位之间的目标编号全部向右移动1位，最后面一位的目标编号移动到最前面一位，然后将右旋后的s和t之间的基因片段插入到基因位p的前面。具体过程如图7所示。

3.5 更新操作

为了避免在迭代后期陷入局部最优，需要将子代种群中一定比例的个体替换为父代种群中的精英个体。所需替代的染色体数量Nr由种群规模Np和预设的代沟Gap共同决定，计算公式为：Nr=Np*(1-Gap)，比如Gap取值为0.8。具体操作如下：将父代种群中的个体按照适应度值大小排序，选择排名前20%的父代染色体替换子代种群适应度值排名后20%的染色体，得到的新种群将作为下一轮迭代的父代种群。

4 实验与分析

算法编码采用Python语言，实验均在Inter(R)Core(TM)i5-7200U CPU@2.50 GHz 2.71 GHz、内存8 GB的x64 Windows10台式计算机上进行。为了展示IPGA的性能，本文设计了2组数值实验。在第1组数值实验中，使用IPGA对文献[27]的TSP基准实例进行求解并对比，以验证算法的正确性。在第2组数值实验中，通过改造文献[27]中的基准实例生成了12组测试实例，然后使用IPGA算法进行求解，得到每架无人机的路径规划方案并进行了相关分析。

4.1 数值实验1

4.1.1 实验数据

在MD-FD-TSP中，若假设无人机数量为1，且不考虑无人机续航能力约束时，可以转换为TSP。“Sioux Falls”路网包含24个节点、38条双向路段，如图8所示，每个圆圈中的序号为路网交叉点的编号，每条边上的数值为边的长度。

图8 Sioux Falls路网示意Fig.8 Schematic diagram of Sioux Falls network

本文基于文献[27]的TSP基准实例进行数值实验，其中点任务和线任务的具体编号如表2所示。

表2 TSP基准实例Tab.2 Benchmark example of TSP

4.1.2 数值实验结果与分析

为了验证本文所提出模型和算法的正确性，基于表2中的9组TSP基准实例，使用IPGA进行求解，每个实例在同一实验条件下运行5次，并将5次中的最优方案记录在表3中，其中，第1列是实例的编号，第2列记录了文献[27]所求得的最优解路径长度，使用IPGA求得的路径方案及其对应的无人机巡检路径和路径长度记录在第3列。为了更直观地展示实验结果，将T22-1实例的最优路径用图9进行展示。

表3 基于TSP标准实例数据集的对比实验结果Tab.3 Comparative experimental results of TSP benchmark data set

图9 T22-1实例的任务规划方案示意Fig.9 Path planning result of T22-1

图9所展示路径规划方案可以描述为：无人机从蓝色圆圈标注的0号节点处出发，沿着绿色箭头方向依次经过路网节点2和3，接着开始执行端点标号为(3，4)的线任务；继而经过路网节点8，9和14，开始依次执行以红色圆圈标注的点任务21和20。完成对点任务20的巡逻后，无人机开始沿着箭头方向返回，到达9号节点后，无人机将会向右飞行以执行端点标号为(15，7)的线任务。至此，无人机已完成对所有任务的巡逻，并沿着箭头方向返回蓝色圆圈标注的停机坪。

从表3可以看出，IPGA求解方案的总路径长与文献[27]所求解的最佳方案的总路径长度一致，说明IPGA可以正确地求解基于点任务和线任务混合的TSP。

4.2 数值实验2

4.2.1 实验数据

由于本文所提出的多无人机高速巡逻路径规划问题的特征与文献[27]中的基准实例有一定的差异，即多无人机以总飞行路程最短为目标，从固定位置出发且每架停机坪限停1架无人机，故本文根据高速公路巡逻任务路段问题的特征构造了以下数据集。假设同1架无人机2个方向的旅行路程相等。表4给出了12组异构巡逻任务设置情况的数据集，每组数据集有不同数量以及位置的线任务和点任务。通过计算，对于这12组异构巡逻任务，表5记录了IPGA求解不同实例数据集的任务规划方案。

表4 异构巡逻任务测试集Tab.4 Test set of heterogeneous patrol task

4.2.2 数值实验结果与分析

使用IPGA对表4中12组实例进行求解，每个实例在同一实验条件下运行5次，将5次中求得的最优方案及其对应的路径长度记录在表5中。为了更直观地展示实验结果，将T1-1实例的最优路径用图10进行展示。

表5 12组数据集求解结果Tab.5 Solution results of 12 groups of data set

图10 T1-1实例的任务规划方案示意Fig.10 Path planning result of T1-1

图10所示的T1-1实例的路径规划方案可以描述为：第1架无人机从标号为0的停机坪出发，沿着绿色箭头方向依次执行编号为2和3的点任务。完成对端点为(10，11)的线任务的巡逻后，沿着绿色箭头方向返回编号为0的停机坪。在第1架无人机执行任务的同时，第2架无人机从编号为1的停机坪出发，首先执行编号为5的点任务，经过路网节点7后，依次执行编号为15和17的点任务。完成对端点为(6，7)的线任务巡逻后沿着紫色箭头方向返回编号为1的停机坪。

这12组实例分别改变了无人机的位置、数量和点线任务的位置和数量。IPGA在实验过程中的求解速度较快。结合表5和图10所给出的路径规划结果可知，求解多无人机任务规划方案是合理的，而且当巡逻任务不均匀地聚集在路网中时，为保证总路径长度最短，更容易出现无人机工作强度不均衡的问题，如T1-3和T2-3。因此，在实际应用中可以适当拉开停机坪之间的距离，从而使得停机坪尽量均匀地分布在任务比较聚集的地方，以便提升任务完成效率。

5 结束语

本文研究了多无人机执行高速公路巡逻任务的规划方法，构建了一种基于多旅行商问题的数学模型，并设计了一种IPGA。通过基于Sioux Falls路网的TSP实例，验证了IPGA的求解能力。在后续研究中可以将无人机的异构性引入模型中，比如续航能力和飞行速度不同的无人机协同执行异构巡逻任务，并进一步分析不同类型无人机适合的场景。