考虑观测次数的无人机交通巡视时空网络模型

王冬冬，何胜学，路 扬

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

实时、可靠、准确的交通信息是进行有效交通管理和控制的基础。目前的交通信息采集主要依赖配备在固定位置的各类固定型交通检测器，主要包括线圈检测器、红外线检测器和视频检测器（AVI）等。但由于受到建设和维修预算的限制，固定型交通检测器布设数量有限，不能在时间和空间上为道路网络提供完整的交通信息。针对上述问题，本文建立考虑单路段巡视次数和限制同一路段多次巡视的时间间隔的无人机路网巡视的路径优化模型，以此解决路网巡视的路径优化问题。

无人驾驶飞机简称无人机（unmanned aerial vehicle，UAV），最早被应用于军事领域，执行战场侦察、跟踪定位、精确制导等任务[1]。近年来无人机在民用方面的应用也逐渐扩展，包括交通检测、天气监测、灾害响应及地质调查等[2]。南京和苏州相继出现了使用无人机进行输电线路巡视和交通路网巡视的案例，效果显著。使用无人机进行交通巡视不受路面交通拥堵的影响，而且成本低、机动性强。可搭载感应装置如传感器、摄像机、照相机等，在一定的高度以俯视的角度获得连续完整的交通信息，并实时地将拍摄画面传送到指挥中心，方便对城市交通的实时监控。可以预见，在不久的将来会有越来越多的地方选择使用无人机进行交通巡视，而使用无人机进行交通巡视需要一套高效合理的飞行计划，因此，在满足一系列任务约束的前提下确定无人机的最佳飞行路径就变得非常重要和有意义。

无人机的路径规划是交通检测的重要部分，是指无人机在给定约束条件下从指定的出发点飞向指定的目的地，完成预设的观测任务且飞行距离最短[3]。无人机的路径规划研究主要包括：以总飞行时间最短和在最短时间内完成所有任务的多目标研究；带有时间窗约束的多无人机协同路径规划研究；确定最佳的无人机数量的多无人机路径规划研究等。文献[4-6]对无人机用于交通事件监测、交通信息采集方面进行了相应的研究。在无人机数量有限，不足以对所有目标进行侦察的前提下，建立了以巡航总距离最短且巡视目标尽可能多为目标的优化模型，并使用遗传算法进行求解[5]。Kim 等[7]对用于交通道路巡视的无人机自动控制算法进行研究，通过UAV 人工视觉系统（AVS）分析应急和异常交通情况，提供车辆跟踪和速度检测问题的解决方案。Huang 等[8]提出了一种多UAV 协同路径规划方法，通过蚁群优化算法获得UAV 的初始路径，并通过K-means 平滑方法获得更多的可飞行路径。Habib 等[9]对多起讫点的无人机路径优化问题进行了研究，对每架无人机巡视目标的数量进行约束，并考虑了无人机因故障导致数量减少，路径重规划的情况。Avellar 等[10]介绍了给定有限数量的无人机，确定最佳的无人机数量，以及使所有无人机的覆盖时间最短的解决方法。Karakaya[11]研究了使用有限数量的无人机进行路径优化，在考虑它们飞行范围的基础上尽可能多地覆盖目标，并通过修改后的最大最小蚂蚁算法（MMAS）进行求解。

国内外对无人机路径规划方面的研究多集中于处理特定任务点对之间无人机路径最优选择问题。在最短的时间内满足一定任务约束条件下巡视完所有目标点，或针对无人机的任务分配，确定最佳的无人机数量。上述研究均以节点为研究对象，没有考虑节点之间是否存在道路连接。而使用无人机进行路网巡视时，需要巡视具体路段。Niu 等[12]提出在总巡航时间最短的情况下应尽可能多地巡测未设置固定型交通检测器的路段。Niu 等[12]以路段作为研究对象，却没有考虑路段的巡视次数问题。根据现实需要，无人机路网巡视需要沿道路巡视，巡视区域内的所有路段应至少被巡视一次，重要路段可能需要多次巡视。同时还要考虑适当的巡视时间间隔，避免无人机之间的相互碰撞和短时间内对同一路段的重复巡视。为了减少冗余飞行，使无人机的巡视路线更加合理，可以适当增加无人机的基站数量，因此，本文研究考虑多基站的多无人机路网巡视问题。

1 基于时空网络的问题描述

本文研究的无人机路径规划问题要求遍历所有路段，重要路段多次巡视，类似于连续域范围内的遍历式路径规划问题。解决此类问题需要先进行环境建模，最常用的方法有栅格法、模板模型法等，本文考虑使用时空网络[13-15]的方法进行建模。时空网络不仅能够较好地表达本文考虑的时间约束问题，而且能够将动态的路径规划转化为静态路径规划，实现对无人机动态时空轨迹的细致刻画。

图1 给出了简单原始路网的时空网络图。原始的实际路网在图的上方，由3 个节点组成，对应的行程时间标示在路段上方。由于无人机飞行速度固定，因此，同一路段的双向行程时间相同。在转化为时空路网前，首先需要根据所有路段的行程时间来确定时空路网中的单位时长，确保所有路段的行程时间都是单位时长的整数倍。其次根据完成任务所需的路段行程时间确定划分的时段总数n。然后根据划分的时段对原始路网中所有的节点复制 n份，并依据原始路段添加对应时空 路段，完成原始路网到时空路网的转换。

图 1 简单原始路网的时空网络图Fig.1 A space-time network diagram for simple road network

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

考虑到沿道路飞行的无人机需要针对地面双向交通的某一特定方向进行跟踪拍摄，所以，一条双向路段的无人机巡视的路线应设定为双向，这与以往的单向路径规划不同，建模和求解的复杂度都大大提高。无人机的运动规划包括路径规划和航迹规划。本文主要研究无人机的路径规划问题，因此，假设无人机飞行速度固定，同时无人机改变方向时的时间消耗以及无人机起飞和降落时的加、减速时间也已经包含在相应路段的飞行时间中。无人机路径规划模型是为了使所有的无人机从指定的基站出发完成规定巡逻任务后返回到基站，且所用时间总和最短。

2 无人机路径规划模型

2.1 参变量说明

由于时空路网在二维平面空间的基础上增加了一个时间维度，因此，对于实际的节点以及路段也需要在原本的表达方法上相应地增加一个时间坐标。原始路网中一维的节点用 n表示，而在时空路网中用二维的 ( n,t)表示。在原始路网中二维的实际路段(m,n)在时空路网中用三维的(m,t,n)表示，其中， m，n为路段起、讫节点， t为从节点 m出发的时间。同时引入了2 个整数变量 Xmp,t,n和rnp,t。Xmp,t,n表示无人机 p是否在 t时刻进行从节点 m到节点 n的巡视。当Xmp,t,n=1时，代表无人机 p在t时刻进行从m点到 n点的巡视；否则，Xmp,t,n=0。对一架无人机p而言，将路网中所有的Xmp,t,n=1的时空路段按照时间顺序取出连接，即可得到无人机 p在时空路网中的运行轨迹。 rnp,t表 示无人机 p是否在t时刻从节点 n加载进入或离开时空路网。当 rnp,t=1 时，表示无人机 p在t时刻从节点 n加载进入时空路网；当rnp,t=-1时，表示无人机 p在t时刻从节点 n离开时空路网；在其他情况时，rnp,t=0。

其他主要参变量简介如下：

N代表路网中所有节点的集合，有 n∈N ；

P代表所有无人机的集合，有p ∈P ；

T 代表时空路网中的时间集合，其中， t∈T ；

(N,T)代表时空路网中的节点集合，是一个节点以及时间组成的二维集合，集合中元素的表达方式为 ( n,t)；

tm,n代 表节点 m到节点 n之间的路段行程时间，由于无人机飞行速度固定，因此， tm,n=tn,m；

(M,T,N)代表时空路网中的路段集合，其中的时空路段(m,t,n)由2 个时空节点(m,t)和(n,t+tm,n)连接而成，表示在t 时刻从节点 m出发前往节点n；

Δt代表某一路段被多次巡视的最小时间间隔；

Nm代表与节点 m相邻的所有节点的集合，其中Nm⊂N；

Rm,n代表路段 ( m,n)的最少巡视次数；

Mo代表路网中无人机发射基站的集合，其中，mo ∈Mo；

Nd代表路网中无人机降落基站的集合，其中，nd∈Nd；

t0代表多架无人机在同一基站起降的最少时间间隔；

Tp代表无人机 p的最大巡航时间。

2.2 目标函数的建立

使用多无人机协同对目标路网进行路网巡视，应使所有无人机在满足飞行特性约束和巡视任务约束的前提下总飞行代价最小。这里考虑的飞行代价包括无人机的总飞行时间f1以及完成任务的时间跨度。其中，无人机从开始起飞到任务完成所需要的总时间代价为所有无人机的飞行时间之和，可表示为

所有的无人机进行协同路径规划，需要考虑无人机在最短的时间内完成所有的巡视任务。这里通过限制单机的最大巡航时间来实现该目标，f2为完成任务需要的最大单机时间。引入一个参数Z ，其中，， 只要令Z的值最小即可。对应的代价函数可表示为

2.3 约束条件的建立

首先考虑巡视次数约束。使用无人机进行路网巡视时，根据实际状况，一般需要对路网中的每条路段至少巡视一次，一些事故频发的重点路段需进行多次巡视，相关约束为

其次考虑同路段相邻巡视的时间间隔约束。当要求对重点路段多次巡视时，无人机可能会在短时间内对一条路段往返重复巡视，而在后面的巡视中“忽略”此路段。这种巡视无疑是不合理的，因此，添加巡视时间间隔约束，要求每条路段在一段时间内只能被巡视一次，具体形式为

接着考虑节点流量守恒。时空网络细致刻画了无人机在原始路网中的飞行轨迹，将动态的原始路网路径规划转化为静态的时空路网路径规划。为了在原始路网中得到连续的飞行路径，需要考虑时空路网中节点的流量守恒，即在任意一个时段，无人机进入某一节点的次数加（减）无人机从该节点加载进入（离开）时空路网的次数等于无人机离开该节点的次数，对应的流量守恒约束为

为了避免无人机之间的相互碰撞和保证基站的有效运作，还需要考虑在一段时间内只允许一架无人机在同一基站起飞或降落的约束为

单架无人机的飞行时间受到其最大续航能力的影响，因此，每架无人机的巡视时间应小于其最大续航时间，相关约束为

如果优化的目标是在最短时间内完成所有巡视任务，则还需考虑的约束为

以式（1）和式（2）为优化目标，式（3）～（9）为约束的多UAV 交通网络巡视模型是一个线性整数规划模型，该类问题可以使用一些经典的算法求解，如分支定界法和割平面法，也可以使用一些经典启发式算法，如遗传算法、模拟退火算法和粒子群算法等。其中，部分较成熟的算法已经在一些商业软件中得到应用，本文将使用商业软件Lingo 对模型进行求解。

3 案例分析

图2 是1 个由14 个节点和42 条路段组成的道路网络。道路均为双向车道，无人机的2 个基站分别位于节点4 和节点13（假设无人机从节点4 和节点13 起降）。根据路网的路段行程时间，以1 min 作为一个单位时长，路段行程时间均以单位时长的整数倍标示在相应的路段上。该路网中共有4 架无人机参与巡视，单机最大续航时间为40 min。在初始阶段，标号为1，3 和2，4 的无人机分别在节点4 和13 的基站，且同一基站的任意时刻至多一架无人机起飞或降落。巡视任务从第一架无人机起飞开始，直到所有无人机全部完成各自任务降落，巡视结束。

该案例中起飞基站的集合 Mo以及降落基站的集合 Nd均由节点4 和节点13 组成。4 架无人机分别从2 个基站起飞，有，。

图 2 上海虹桥临空经济区北区的道路网络Fig. 2 Road network for the north district of airport economic zone of Shanghai Hongqiao

首先不区分重点路段与非重点路段，即不考虑多次巡视任务的路径规划。此时不考虑单路段的巡视时间间隔约束问题，对任意路段(m,n)而言，Rm,n=1。得到无人机的飞行路径如表1 所示，1，2，3，4 号无人机分别在0，0，1，1 时刻起飞，在26，27，28，27 时刻降落，总飞行时间为106 min，在28 min 内完成所有巡视任务。

表 1 不考虑巡视次数的时空路线Tab.1 Space-time routes without considering the number of visits

如果选择路段（5,9）和（7,8）为重点路段，要求重点路段至少巡视3 次。为避免无人机在连续时间内对该类路段进行往返重复巡视，规定巡视时间间隔至少应为6 min。此时模型中的系数R5,9，R9,5，R7,8，R8,7均等于3，其他任意路段(m,n)，Rm,n=1；巡视时间间隔为6 s。得到无人机的飞行路径如表2 所示。1，2，3，4 号无人机分别在0，0，1，1 时 刻起 飞，在33，32，30，33 时 刻降落，无人机的总飞行时间为126 min，并且所有的无人机在33 min 内完成任务。

表 2 考虑巡视次数和时间间隔的时空路线Tab.2 Space-time routes considering the number of visits and time intervals

由表1 和表2 数据可知，由于受到同一时间内至多有一架无人机在基站起降的限制，3 号和4 号无人机选择在 t=1 时刻起飞。其中，两种情景下完成巡视任务所需的时间分别为28 min 和33 min。对该案例的两种情景进行比较，与不考虑巡视次数的路径规划相比，无人机的总飞行时间和单机飞行时间分别增加15.87%和15.15%。案例第二种情景下每架无人机只需多飞5 min，即可完成对重要路段巡视3 次的任务。就所有无人机的总飞行时间而言，无人机完成任务的效率达到了100%。案例分析表明，该模型是有效可行的。使用Lingo 软件对该问题进行求解，计算时间少于2 min。

Lingo 软件的运算时间与时空网络的规模相关。Lingo 求解问题采用的是一种精确搜索方法，运算时间会随着求解问题规模的扩大呈指数增长，因此，Lingo 只能够解决一般路网规模的路径规划问题。受到电池容量的限制，无人机的单机飞行时间有限，能够巡视的路网规模也有限，因此，使用Lingo 能够解决无人机的路网巡视问题。

第二种情景下无人机的巡航距离受到约束时，为了完成特定的飞行任务，同时满足总巡航距离最短的目标，单架无人机的飞行路径趋于区域化，即无人机在各自固定的几条路段来回飞行。从图3 无人机的飞行路径中可以看到，1 号和2 号无人机分别从节点4 和节点13 起飞，在飞行路径上有着近似性的互补关系，3 号和4 号无人机也有类似的关系，说明多无人机路网巡视能够使各架无人机的巡视路径更加区域化，同时也使总体的飞行路径更加合理，避免冗余飞行。

图 3 无人机飞行路径Fig.3 Flight path of unmanned aerial vehicle

4 结 论

针对传统交通信息收集方式不能有效获取路网全面实时性交通信息的问题，提出使用无人机进行路网巡视的方法。无人机沿路网巡视不受道路交通状况的影响，而且能够在一定的高度上获得完整的道路交通信息，有利于实现地空协调，更加高效地解决交通问题。根据路网中道路的拥堵程度、事故发生频率等因素将路段分为重点路段和普通路段，要求无人机在路网巡视时普通路段至少巡视一次，重点路段多次巡视，合理分配无人机资源。为了使飞行路径更加合理，添加了巡视时间间隔约束，避免无人机在一个连续的时段内对同一重点路段重复巡视。本文还限制了无人机在基站同时起降的数量，减少基站的人员配备。本文研究可促进无人机在交通路网巡视方面的应用，为使用无人机解决相关交通问题提供理论基础。

本研究的后续拓展方向包括：a. 无人机基站的选址优化；b. 无人机机型对路径规划的影响分析；c. 考虑在道路交叉口利用无人机进行交通控制。