﻿ 考虑观测次数的无人机交通巡视时空网络模型
 上海理工大学学报  2019, Vol. 41 Issue (5): 441-447 PDF

Unmanned Aerial Vehicle Traffic Patrol Space-Time Network Model Considering the Number of Observations
WANG Dongdong, HE Shengxue, LU Yang
Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Based on the problem that the traditional road information detection method cannot obtain real-time continuous road information, a method of using the unmanned aerial vehicle (UAV) to conduct road network inspection was proposed. The optimization model for multi-machine flight path was established to solve the path optimization problem of the UAV through the space-time road network. The optimization objective for the new model was to minimize the total flight time of all aircraft or the maximum flight time of each aircraft under the condition of the completion of all mission. The new model not only transformed the dynamic path plan into a static path plan by using time-space network technology to meticulously depict the flight path of the UAV during the patrol process, but also added multiple patrols of key road sections and time interval constraints for multiple patrols. Based on the analysis of a case in the text, results show that, in comparison with the path planning without considering the number of patrols, the total and single flight time of the UAV increases by 15.87% and 15.15% respectively. The mission goal of patrolling two important road sections for three times can be completed. The analysis of the example shows that the optimized patrol path is more realistic to practical needs.
Key words: urban traffic     path planning     space-time network     unmanned aerial vehicle     road network inspection

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

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

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

${N_{{m}}}$代表与节点$m$相邻的所有节点的集合，其中${N_{{m}}} \subset N$

${{{R}}_{{{m,n}}}}$代表路段$(m,n)$的最少巡视次数；

${M^{\rm{o}}}$代表路网中无人机发射基站的集合，其中，${m^{\rm{o}}} \in {M^{\rm{o}}}$

${{N}^{\rm{d}}}$代表路网中无人机降落基站的集合，其中，${n^{\rm{d}}} \in {N^{\rm{d}}}$

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

${{{T}}^p}$代表无人机$p$的最大巡航时间。

2.2 目标函数的建立

 ${f_1} = \displaystyle\sum\limits_m {\displaystyle\sum\limits_{n \in {{N}_{{m}}}} {\displaystyle\sum\limits_t {\displaystyle\sum\limits_{p \in {P}} {\mathop x\nolimits_{m,t,n}^p {t_{m,n}}} } } }$ (1)

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

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

 [1] 吕信明. 军用无人机的发展及对策[J]. 国防科技, 2013, 34(1): 5-8. DOI:10.3969/j.issn.1671-4547.2013.01.002 [2] ZHANG J S, JIA L M, NIU S Y, et al. A time-space network-based modeling framework for dynamic unmanned aerial vehicle routing in traffic incident monitoring applications[J]. Sensors, 2015, 15(6): 13874-13898. DOI:10.3390/s150613874 [3] 符小卫, 高晓光. 一种无人机路径规划算法研究[J]. 系统仿真学报, 2004, 16(1): 20-21. DOI:10.3969/j.issn.1004-731X.2004.01.007 [4] LIU X F, PENG Z R, CHANG Y T, et al. Multi-objective evolutionary approach for UAV cruise route planning to collect traffic information[J]. Journal of Central South University, 2012, 19(12): 3614-3621. DOI:10.1007/s11771-012-1449-8 [5] 刘晓锋, 彭仲仁, 张立业, 等. 面向交通信息采集的无人飞机路径规划[J]. 交通运输系统工程与信息, 2012, 12(1): 91-97. DOI:10.3969/j.issn.1009-6744.2012.01.014 [6] 刘晓锋, 常云涛, 王珣. 稀疏路网条件下的无人飞机交通监控部署方法[J]. 公路交通科技, 2012, 29(3): 128-134. [7] KIM N V, CHERVONENKIS M A. Situation control of unmanned aerial vehicles for road traffic monitoring[J]. Modern Applied Science, 2015, 9(5): 1-13. [8] HUANG L W, QU H, JI P, et al. A novel coordinated path planning method using k-degree smoothing for multi-UAVs[J]. Applied Soft Computing, 2016, 48: 182-192. DOI:10.1016/j.asoc.2016.06.046 [9] HABIB D, JAMAL H, SHOAB A. Employing multiple unmanned aerial vehicles for co-operative path planning[J]. International Journal of Advanced Robotic Systems, 2013, 10(3): 1-9. [10] AVELLAR G S C, PEREIRA G A S, PIMENTA L C A, et al. Multi-UAV routing for area coverage and remote sensing with minimum time[J]. Sensors, 2015, 15(11): 27783-27803. DOI:10.3390/s151127783 [11] KARAKAYA M. UAV route planning for maximum target coverage[J]. Computer Science & Engineering, 2014, 4(1): 27-34. [12] NIU S Y, ZHANG J S, ZHANG F, et al. A method of UAVs route optimization based on the structure of the highway network[J]. International Journal of Distributed Sensor Networks, 2015, 2015(1): 1667-1670. [13] 何胜学, 陈经纬. 考虑上客点选择的公交紧急疏散时空路网模型[J]. 计算机应用研究, 2017, 34(7): 2001-2005. DOI:10.3969/j.issn.1001-3695.2017.07.018 [14] 何胜学. 无预警紧急疏散中公交车辆路径的确定方法[J]. 运筹学学报, 2014, 18(3): 47-59. DOI:10.3969/j.issn.1007-6093.2014.03.004 [15] 陈经纬, 何胜学, 程龙. 基于时空网络的无人车运行计划制定[J]. 计算机应用研究, 2017, 34(12): 3642-3646. DOI:10.3969/j.issn.1001-3695.2017.12.027