基于完善交通信息收集的UAV路径规划

王冬冬，何胜学，路 扬

（上海理工大学管理学院，上海 200093）

0 引言

实时、准确的交通信息是实施交通管理和控制的基础。目前交通信息采集主要依赖于配备在固定位置的各类固定型交通信息检测器，如固定线圈、红外和视频检测器等。受经济预算的限制，部分城市路段没有布置固定型交通信息检测器，无法获取有效的交通信息。作为新时代的产物，无人机（Unmanned Aerial Vehicle，简称UAV）已经广泛应用于交通信息收集、紧急救援、电力巡检等各领域[1-4]。针对现有交通巡检设备巡检效率低、灵活性差等问题，提出使用无人机收集完善交通信息的方法[5]。然而，因受电池容量的限制，无人机的飞行时间有限，研究无人机的最佳飞行路径就变得非常重要和有意义。

目前国内外对无人机路径规划方面的研究主要涉及算法研究，确定最佳的无人机数量以及使用有限数量的无人机巡视尽可能多的目标等。Kim等对用于交通道路巡查的无人机自动控制算法进行研究，通过UAV人工视觉系统（Artificial Vision Sys⁃tem，简称AVS）分析应急和异常交通情况，提供车辆跟踪和速度检测问题的解决方案[6]。Karakaya研究使用有限数量的无人机进行路径优化，在考虑飞行范围的基础上尽可能多地覆盖目标，并通过改进后的最大最小蚂蚁算法（MAX-MIN Ant System，简称MMAS）进行求解[7]。Huang等提出一种多UAV协同路径规划方法,通过蚁群优化算法获得UAV的初始路径，并通过K-means方法获得更多的可飞行路径[8]。Avellar等在无人机数量有限的条件下，确定最佳的无人机数量，并给出使所有无人机覆盖时间最短的方法[9]。Niu等提出使用无人机作为一种移动型交通检测器对高速公路进行巡视，在总飞行时间最短的情况下尽可能多地巡视未布设固定型交通检测器路段[10]。刘晓锋等对无人机用于交通事件监测、交通信息采集进行了研究[11-13]。刘晓锋等在无人机数量有限，不足以对所有目标进行侦察的前提下，建立了以巡航总距离最短且巡视目标尽可能多为目的的优化模型，并使用遗传算法进行求解[11]。上述研究虽然对未布设固定型交通检测器的路段进行信息收集，但没有考虑到收集信息的准确性以及利用无人机资源的合理性。

本文拟通过时空网络，建立以总飞行时间最短和最大单机飞行时间最短为目标的多目标模型，优化巡视路径，并通过添加巡视次数和巡视时间间隔使收集到的信息更加符合实际需要。

1 时空网络介绍

为细致刻画无人机在路网巡视过程中的动态飞行特征，将动态的路网巡视过程转化为静态的无人机飞行轨迹，在此引入时空网络作为研究框架[14-15]。将普通的原始路网拓展为时空路网后一般网络规模都比较大，问题的求解有一定难度。考虑到本文主要研究UAV的路径规划问题，为降低求解难度，假设无人机的飞行速度固定，且不考虑无人机转弯的时耗。图1所示为原始路网到时空路网的具体转化过程。首先，根据所有路段的行程时间确定时空路网的单位时长，确保所有路段的行程时间都是单位时长的整数倍。然后，根据完成任务所需的路段行程时间，将原始路网中所有节点复制n份。最后，进行时空路段的连接，依据原始路段添加相应的时空路段，即无人机从一个节点前往另一个节点的过程，在时空路网中用运行弧表示。

图1中，线型1表示运行弧，代表无人机所有可能飞行的路径；线型2连接位于相邻时刻的同一节点，表示无人机在一个节点等待一个分段时长，即随着时间的变化，无人机的空间位置未发生变化。有向实线（线型3）给出了一个无人机在时空路网中的运行轨迹：无人机p在t=0时刻从节点a出发开始巡逻任务，在下一时刻到达节点b，然后经过节点b在t=3时刻到达节点c，最后从节点c按照原路返回，在t=6时刻经节点b回到节点a。因本研究不考虑无人机的等待行为，故对于等待弧不予考虑。

图1 一个简单原始路网的时空网络图

2 模型构建

2.1 目标函数的建立

合理的飞行路径应要求所有无人机在满足飞行特性约束和巡视任务约束的前提下，总飞行代价最小。这里考虑的飞行代价包括无人机的总飞行时间和完成任务的时间跨度，其飞行代价分别用式（1）和式（2）表示为：

式（1）中：f1表示无人机的总飞行时间（min）；m,n表示节点号；Nm表示所有与节点m直接相连的节点的集合；P表示无人机的集合，p表示其中一架无人机；tm,n表示节点m到节点n所在道路的路段行程时间（min），有tm,n=tn,m，其中某一时刻用t表示；xpm,t,n是一个0-1变量，表示无人机p是否在t时刻进行从节点m到节点n的巡视。当xpm,t,n=1时，代表无人机p在t时刻进行从m点到n点的巡视；xpm,t,n=0则表明不进行。

式（2）中：f2表示最大单机飞行时间（min）；Z为新引入的参数，表示任意单架无人机的飞行时间上限（min），有

传统求解多目标问题的方法主要通过对多个目标赋予不同的权重系数，然后通过线性组合将多目标问题转化为单目标问题。这种方法便于通过调整权重系数得到想要的结果，也有利于问题的分析。在使用这种平均加权因子的方法计算模型之前，需要先用公式（3）和公式（4）对两个目标进行归一化处理：

最终的目标函数值计算如下：

式（3）～式（5）中：Tpperfect表示遍历整个路网所需要的单机飞行时间（min）；表示遍历整个路网所需要的总飞行时间（min）；g1,g2分别表示目标f1和目标f2归一化后的值；w1,w2是无人机飞行代价的权重系数，分别表示无人机的总飞行时间最少和最大单机飞行时间最少的重要程度，且满足w1+w2=1，w1,w2∈[0,1]；g表示多目标归一化后考虑权重系数的和，g值越小越好。

2.2 约束条件的建立

为保证所收集交通信息的准确性和巡视路径的合理性，模型需要考虑单路段的巡视次数、巡视时间间隔、节点流量守恒以及单架无人机的最大飞行时间约束。

首先，考虑单路段的巡视次数，要求每条路段(m,n)至少巡视Rm,n次，即：

式（6）中：M,N表示路网中所有路段起点和终点的集合；(M,N)表示所有路段的集合，且(m,n)∈(M,N)；Rm,n表示路段(m,n)的最少巡视次数（次）。

接着，考虑单路段的巡视时间间隔约束，要求单路段在最小巡视时间间隔内至多被巡视一次，即：

式（7）中：Δt表示单路段的最小巡视时间间隔（min）；T表示时空路网中所有时间的集合（min），有t∈T；(M,T,N)表示时空路网中所有时空路段的集合，即任意时刻所有路段的集合，有

随后，考虑节点的流量守恒。在任意时刻，无人机进入某一结点的次数加（减）无人机从该结点加载进入（离开）时空路网的次数等于无人机离开该结点的次数。对应的流量守恒约束如下：

式（8）中：引入整数变量rp n,t，表示无人机p是否

在t时刻从节点n加载进入或离开时空路网。当时，表示无人机p在t时刻从节点n加载进入时空路网；当时，表示无人机p在t时刻从节点n离开时空路网；表示其他情况；(N,T)表示所有节点在时空路网中的集合，即任意时刻所有节点的集合，有

最后，每架无人机的巡视时间都应小于等于其最大续航时间，即：

式（9）中：Tp表示无人机p的最大飞行时间（min）。

若要求无人机在最短时间内完成全部的交通信息收集任务，还需添加如下约束：

以式（5）为目标、式（6）～式（10）为约束的多UAV交通信息收集路径规划模型是一个大规模线性整数规划模型。求解这类问题的经典方法主要有分支定界法[16]和割平面法，也可以使用经典的启发式方法，如遗传算法[17]、模拟退火算法[18]和粒子群算法等求解模型。其中部分较成熟的算法已经在一些商业软件当中得到应用，并且有着较好的求解效率。本文将使用商用软件Lingo对模型进行求解。

3 算例分析和验证

3.1 算例分析

图2所示交通网络由10个节点和36条路段组成。节点间的路段行程时间标注在路段上方，选择1min作为一个单位时长。使用2架无人机对该网络进行信息收集。无人机在起飞前分别位于节点3和节点8的基站位置，完成巡视任务后分别回到起飞的基站位置。图中（1,3），（2,5），（4,7），（6,7）所在路段不能收集到有效的交通信息，需要使用无人机对以上各路段至少巡视两次，且巡视时间间隔应大于上述路段最大行程时间的2倍。

图2 路网示意图

首先根据图2在Lingo中建立原始路网，并根据图1所示的方法在原始路网的基础上增加一个时间维度，完成原始路网到时空路网的转化。然后根据上文提到的目标和任务约束建立目标函数和约束条件，要求两架无人机分别从节点3和节点8起飞，巡视结束后回到起飞位置。运算程序，得到所有xpm,t,n=1的量。对同一架无人机p而言，将所有的xpm,t,n=1按照时间顺序排列，即可得到无人机p在时空网络中的运行轨迹。最后，将无人机在时空网络中所经过的时空节点按顺序对应到原始节点，得到的原始节点顺序就是无人机的实际飞行路径。

下面对算例进行运算。首先给予双目标相等的权重，令w1=w2=0.5，得到无人机在时空路网中的具体运行轨迹，如表1所示。

表1 时空路网运行轨迹

由表1可知，2架无人机分别在t=0时刻从节点3和节点8起飞，并分别在14min和23min回到基站。无人机的总飞行时间为37min，最大单机飞行时间为23min。两架无人机的单机飞行时间差距悬殊，没有做到合理分配续航时间。因此需要进一步增大w2，要求整个交通信息收集任务在最短的时间内完成。依次改变w1和w2的值，得到2架无人机的飞行时间以及目标函数值的大小，如表2所示。其中UAV-1和UAV-2分别表示两架无人机的飞行时间，g表示双目标归一化后考虑权重系数的和。

表2 情景分析

分析表2中的结果，当w1≤0.4时，2架无人机的总飞行时间变为41min，最大单机飞行时间为21min，即整个飞行任务最短在21min内完成。对比表1，无人机的总飞行时间增加了9.76%，最大单机飞行时间减少了8.70%。随着权重w1的增加，第一目标所占的比重增大，无人机的总飞行时间逐渐缩短，最大单机飞行时间逐渐延长。当w1所占比重足够大时，系统仅使用1架无人机进行巡视，对应的总飞行时间最短，单架无人机的飞行时间为34min。如果仅考虑总目标函数最小，使用1架无人机的巡视效果最优，对应的飞行路径为3-1-2-5-4-6-7-4-6-7-4-5-2-1-3。通过Lingo软件，该算例的运算时间小于10s。

3.2 算例验证

为进一步验证本模型和方法的有效性，这里选择Sioux-Fall城市路网进行验证，如图3所示。Sioux-Fall城市路网被广泛应用于交通领域，该路网由24个节点和76条路段组成，基站位于节点4和节点19。有2架无人机分别从基站起飞，巡视结束后回到起飞位置，其中（4,5），（7,8），（9,14），（10,11），（11,16），（19,20）需要巡视2次，且巡视时间间隔不低于6 min。

给予双目标相等的权重，重复上述方法，在Lingo中建立时空路网，得到无人机的飞行路径（UAV-1：4-5-7-8-9-14-13-15-18-17-20-19-16-11-10-3-4；UAV-2：19-16-11-10-3-4-5-7-8-9-14-13-12-17-20-19）。2架无人机在t=0时刻分别从节点4和节点19起飞，在t=28时刻同时回到起飞位置，整个任务在28min内完成。通过Lin⁃go软件，该算例的运算时间不超过30min。

图3 Sioux-Fall城市路网

Lingo软件的运算时间直接与时空网络的规模相关，它求解线性规划问题采用的是一种精确搜索方法，因此计算时间会随着时空网络规模的增大而呈指数增加。对于由24个节点、76条路段组成的Sioux-Fall城市路网，依然能够在30min内得到最优解，因此本文提出的模型和方法可以解决无人机在大规模路网的路径规划问题。

4 结语

针对部分路段由于固定型交通信息检测器布设不足或因后期损毁导致无法获取有效交通信息的问题，提出使用无人机对该路段进行巡视以完善交通信息的方法。为保证收集信息的准确性，要求无人机多次巡视该路段，并且一段时间内至多巡视一次。由于时空网络的时间拓扑特性能够较好地表达巡视次数和时间间隔约束问题，本文以时空网络作为研究框架，建立了以总飞行时间最短和最大单机飞行时间最短为目标的多目标模型。算例分析表明，本文所建模型能够求出最佳的无人机数量和相应的巡视路径，证实了模型的有效性。不过，本文假设无人机飞行速度固定，没有考虑无人机转弯时的加速度变化和时间消耗，接下来将进一步研究考虑航迹的UAV路径规划问题。