A Method of UAVs Route Optimization Based on the Structure of the Highway Network

Abstract

It is essential for transportation management centers to establish a network of fixed and mobile sensors to collect traffic information of highway network, especially for very important links with frequent traffic events. Emerging Unmanned Aerial Vehicles (UAVs), it is introduced as a mobile sensor to collect road traffic information and its cruise route planning problem is researched based on the highway network physical structure. First, according to existing traffic data, a method used to calculate the link importance degree index is proposed, and the index is used to evaluate the link's information. Second, a multiobjective optimization model is proposed, its aim is to minimize the total cruise time under detecting as many important links as possible and minimize the information value undetected by UAVs, and the fuzzy operator is introduced to the constraint conditions. Finally, a case study is used to demonstrate the feasibility and effectiveness of proposed model about UAVs’ route planning.

1. Introduction

Traffic information is the foundation of the traffic management and control. Traffic sensors are considered as an important way to collect traffic information. Most of commonly used traffic sensors are installed in fixed location, such as loop detector, microwave detector, video camera, and Automatic Vehicle Identification (AVI) readers. The biggest advantage of this kind of traffic sensors is that they can capture the traffic dynamic characteristics of the specific location for a long time horizon. While the disadvantage of fixed traffic sensor is also obvious, it cannot be installed on everywhere in a network because of the budget constraint. The movable traffic sensors are developed as a complementary tool for traffic information collecting. Due to the weakness of the fixed traffic sensor, more movable traffic sensors are invented for network surveillance. Unmanned Aerial Vehicle (UAV) is considered as a novelty tool, which can conduct different tasks by loading various sensors, such as high-resolution camera, radar, and infrared camera.

UAVs, well known for their wide field of view, easy operating, and outstanding flexibility, are promised to be a great aerial sensor for transportation applications. UAVs can be launched quickly and exchange data with control center in real time. According to the sensors on the UAVs, they can provide the entire image of the investigation area or a special location and also provide continuous traffic state evolution. Therefore, UAVs are considered as an effective traffic surveillance system compared with traditional fixed traffic sensors.

The maximum flight distance or flight time of UAV is limited by the fuel volume and battery volume that they can carry. If the number of monitored roads and available UAVs are determined, it is important and meaningful to investigate the optimal cruise route of UAVs in order to cruise more target roads under the UAVs’ capacity constraints or cruise all target roads with most efficient route.

In recent years, some researchers focused on the UAVs route planning problems. Ryan et al. [1] considered this problem as a multiple travel salesman problem with the objective of maximizing expected target coverage and solved it by applying a Reactive Tabu Search. In 2002, the UAVs route planning problem was studied by Hutchison. The monitored roads were divided into several subareas firstly, and all the target road in each subarea was inspected by one UAV. In his study, the UAVs route planning problem was solved by simulated annealing algorithm [2]. Yan et al. [3] also considered the UAVs routing problem as a TSP and introduced a generic algorithm to find out the nearly optimal route. This paper creatively considered the different fly routes between two target roads into their model. They verified their method by a case study of sparse network in western part of China.

Ousingsawat and Campbell [4] considered this problem as two parts. First is to find the shortest path between two points, and the possible path combinations are listed for all UAVs; then the task assignment problem was used to give the results. Tian et al. [5] introduced the time window requirement of reconnaissance mission for each target road. They presented a mathematical model for cooperative reconnaissance mission planning problem which takes the reconnaissance resolution demands and time windows of the targets into account and with the constraints of maximum travel time of each UAV.

Wang et al. [6] presented a multiobjective ant colony system algorithm for UVA route planning in military application. Two components are taken into account in their cost function which are route length and danger exposure. Liu et al. [7] proposed a multiobjective optimization model for UAVs route planning. Two objectives are listed: minimize the total distance and maximize the total number of monitored points. The available amount of UAV and maximum cruise distance are considered as constraints. Liu et al. [8] introduced time window constraint in the optimization model. One of the main weakness of their study is that they did not consider the length of road links. Liu et al. [9] introduced UAV route planning method without and with flight distance constraints. K-means clustering algorithm was used to divide the UAV cruse area into subarea and simulated annealing algorithm was applied to solve this problem. The multiobjective optimization model proposed by Liu et al. [10] aimed to minimize UAV cruise distance and minimize the number of UAVs being used. Zhang et al. [11] presented a space-time network-based modeling framework for integrated fixed and mobile sensor networks, in order to provide a rapid and systematic road traffic monitoring mechanism. A Lagrangian relaxation solution framework is developed to decompose the original complex problem into a series of computationally efficient time-dependent and least cost path finding subproblems. A recent study by Zhu et al. [12] specifically considered the mobility constraints of traffic sensors, and a measure of traffic information acquisition benefits was used to evaluate the surveillance performance. Their proposed hybrid two-stage heuristic algorithms include both particle swarm optimization and ant colony optimization components.

Additionally, in military area, UAVs have already dominated the investigative equipment. While in the general aviation field, UAVs are facing some barriers in China, for instance, strict airspace and complicated route application. These barriers obstruct the UAVs’ application in transportation field. The China air traffic control center will open the low attitude space (lower than 1000 m) management in the following years. This is a great opportunity for the transportation department to explore the application of UAVs in road traffic network surveillance and traffic incident observation.

Based on above, this paper proposed a novel model of UAVs route planning under the assumption of UAVs’ flying space constraint where UAVs could only fly above the physical road network. Multiobjectives are considered in this model which minimize flying cost and maximize the collected information value or minimize the undetected information value.

The remainder of this paper is organized as follows. The problem statements and assumptions are first presented in the next section. In Section 3, a structure of the highway network based UAV routing planning model is developed to integrate with existing fixed traffic detectors to minimize flying time and maximize the detect information value. In Section 4 an illustrative example is given to demonstrate the effectiveness of the proposed models. The conclusion is summarized in Section 5.

2. Problem Statement and Assumptions

2.1. Problem Assumptions

At present, UAV flight facing a more practical problem in China is affected by the traffic management requirements and low-flying privileges, as well as inhabitant distribution, so the UAVs cannot be arbitrary flying in the sky. For the highway network, airspace along the road does not involve in residential and military no-fly zone and other restrictions; therefore UAVs flying along the physical road are more feasible.

In recent years, researchers proposed different kinds of UAVs route optimization methods. Someone used dual method and the links which are needed to be monitored were transformed into nodes; someone assumed UAVs fly along the road when they cruise road links. Figure 1 shows the main abstract methods of UAVs route optimization problem.

Figure 1

The main abstract methods of UAVs route optimization problem.

In [7–9], the authors abstracted the links which are needed to be detected into nodes, and it is assumed that arcs exist between both arbitrary nodes and UAVs can fly along them, but it is very difficult to carry out in reality. Reference [10] assumed UAVs fly along the road when they cruise road links which are needed to be detected, but the other path is along the straight line between two nodes. Reference [11] assumed UAVs fly along the road from beginning to end.

In this paper, stipulate UAV cruising routine based on topology network of road network. And the cruise targets are nondetector links. When the UAVs cannot cruise all nondetector links, the links with higher important degree will be selected to cruise prior to finally get maximum detection information. When the information value of links are equal, the low cost route will be selected prior.

2.2. The Link Importance Degree Calculation

We choose the links by the important degree of the links without fixed sensors as cruising targets. The information of the link will be increased with the important degree increasing. Thus, the cruising route of UAVs are determined by the important degree of links. The important degree assessment is equivalent to vulnerability analysis problem in some degree.

A number of different vulnerability assessment methods and indicators are available in the literatures, for example, [13–15], arising from different interpretations of the concept of it and the scope of analysis. According to [14], several types of attributes can have a significant effect on link importance and these can be classified into four main types, that is, network characteristics, traffic flow, threats, and neighborhood attributes. Network attributes include road types and physical configuration. The traffic attributes could cover link capacity, flow, and speed. Attributes concerning “threats” may include event types, the scope, and extent of event's impact.

In reality, it is very difficult to collect the traffic flow and speed information on the nondetector links, so there are some limitations in the above method. As Department of the National Transportation, Ministry of Transport in China, opened the traffic information management system in September 2006, the blocked road information was reported to the traffic information center and the nationwide traffic information service was started at the same time. After years of practice, a large amount of blocked road information data has been accumulated by traffic information management system. Based on GIS technology, a spatial data analysis method for blocked road information data is presented in [16], and it is easy to obtain the number of blocked events and its event rank in some time periods, such as one year and continuous three years. Here, the link importance degree is calculated by the number of blocked events and its event rank parameters. The more the blocked events on the link, the more the important degree, and the information of this link is large.

The calculation formula of importance degree of link i is as follows:

$$\begin{array}{cc}& I_i={\displaystyle \sum }_{k=\mathrm{1}}^N{n}_k^i{w}_k,\end{array}$$

(1)

in which N is the event rank; usually, N is equal to 5; $n_k^i$ is the number of events on rank k, link i, and $n_k^i\ge \mathrm{0}$ ; $w_k$ is the weight of rank k.

In the next section, the link importance degree is denoted by link information value; if the UAVs cruise the link, then the information is collected.

2.3. The Optimal Object Determination

In daily inspections, the goal of administrators is to use the least cost to get much more information. According to this objective, maximizing the amount value of collected information and minimizing the flying time of UAVs are considered as two objective functions in this paper.

Due to different flying time, the corresponding fuel cost is also different. Endurance mileage and endurance time of UAV have a certain correlation, but endurance mileage cannot reflect the flight cost difference due to UAV flying time change under condition of same endurance mileage. Actually, the flying speed of UAVs can be adjusted according to management requirement; namely, UAVs keep low speed flying or hover over somewhere when flying over cruising road and keep high flying speed when flying the undetected road link between cruising roads. So, for the same flight mileage, the UAV's flight time is very different. Therefore, this paper chooses UAV endurance time as UAV flying cost, rather than flying distance (such as literature [8, 9]).

3. The UAVs Route Optimization Model

The intersections of highways, interchanges, and toll stations are abstracted as nodes and the original topology of highway network structure is extracted. Then, the adjacency matrix and incidence matrix between link and node of highway network topology can be obtained easily, denoted by M and B, respectively. Furthermore, the flight time matrix D between any two nodes of UAV by using the highway mileage data and the UAVs’ speed is nonmonitoring links.

Let S be the set of all links in highway network, let $S_{\mathrm{0}}$ be the set of links which are not installed fixed sensors, and let $S_{\mathrm{1}}$ be the set of links which are installed fixed sensors; then $S_{\mathrm{0}}\cap S_{\mathrm{1}}=\Phi$ ,   $S_{\mathrm{0}}\cup S_{\mathrm{1}}=S$ . The monitoring targets are the links which are not installed fixed sensors.

3.1. Preparation

Here, the calculation method of UAV's flying time between two detected links is introduced.

The flight time contains two parts: (I) the cruise time of target links and (II) the flight time between two adjacent target links. Part (I) is obtained by link length and the speed of UAV on the link. Part (II) is calculated by formula (2) in [6] as follows.

As in Figure 2, links m and n are needed to be detected, and the link m connects the node $a_s(m)$ and node $b_e(m)$ and the link n connects the node $a_s(n)$ and node $b_e(n)$ . When the UAV flights from link m to link n, it has four possible route options as shown in dashed arrows: $a_s(m)\to b_e(n)$ , $a_s(m)\to a_s(n)$ , $b_e(m)\to a_s(n)$ , and $b_e(m)\to b_e(n)$ . Then the flight time from link m to link n of UAV is obtained by following formula:

$$\begin{array}{cc}& L^{\prime }\left(m,n\right)=\alpha \left[\beta D_{mn}^{\mathrm{1}}+\left(\mathrm{1}-\beta \right)D_{mn}^{\mathrm{2}}\right]+\left(\mathrm{1}-\alpha \right)\left[\beta D_{mn}^{\mathrm{3}}+\left(\mathrm{1}-\beta \right)D_{mn}^{\mathrm{4}}\right],\end{array}$$

(2)

where

$$\begin{array}{cc}& \alpha =\left\{\begin{array}{cc}\mathrm{1}\hfill & \text{when\hspace{0.17em}\hspace{0.17em}}{a}_s\left(m\right)⟶a_s\left(n\right)\text{\hspace{0.17em}\hspace{0.17em}or\hspace{0.17em}\hspace{0.17em}}{a}_s\left(m\right)⟶b_e\left(n\right)\hfill \\ \mathrm{0}\hfill & \text{when\hspace{0.17em}\hspace{0.17em}}{b}_e\left(m\right)⟶a_s\left(n\right)\text{\hspace{0.17em}\hspace{0.17em}or\hspace{0.17em}\hspace{0.17em}}{b}_e\left(m\right)⟶b_e\left(n\right),\hfill \end{array}\right.\\ \beta =\left\{\begin{array}{cc}\mathrm{1}\hfill & \text{when\hspace{0.17em}\hspace{0.17em}}{a}_s\left(m\right)⟶a_s\left(n\right)\text{\hspace{0.17em}\hspace{0.17em}or\hspace{0.17em}\hspace{0.17em}}{b}_e\left(m\right)⟶a_s\left(n\right)\hfill \\ \mathrm{0}\hfill & \text{when\hspace{0.17em}\hspace{0.17em}}{a}_s\left(m\right)⟶b_e\left(n\right)\text{\hspace{0.17em}\hspace{0.17em}or\hspace{0.17em}\hspace{0.17em}}{b}_e\left(m\right)⟶b_e\left(n\right).\hfill \end{array}\right.\end{array}$$

(3)

Figure 2

The possible routes between link m and link n.

$D_{mn}^{\mathrm{1}}$ represents the UAV's flight time from node $a_s(m)$ to node $a_s(n)$ , and $D_{mn}^{\mathrm{1}}=d(a_s(m),a_s(n))$ ; $D_{mn}^{\mathrm{2}}$ represents the UAV's flight time from node $a_s(m)$ to node $b_e(n)$ , and $D_{mn}^{\mathrm{2}}=d(a_s(m),b_e(n))$ ; $D_{mn}^{\mathrm{3}}$ represents the UAV's flight time from node $b_e(m)$ to node $a_s(n)$ , and $D_{mn}^{\mathrm{3}}=d(b_e(m),a_s(n))$ ; $D_{mn}^{\mathrm{4}}$ represents the UAV's flight time from node $b_e(m)$ to node $b_e(n)$ , and $D_{mn}^{\mathrm{4}}=d(b_e(m),b_e(n))$ . Here, $D_{mn}^{\mathrm{1}}$ , $D_{mn}^{\mathrm{2}}$ , $D_{mn}^{\mathrm{3}}$ , and $D_{mn}^{\mathrm{4}}$ can be obtained from matrix D.

If link n is the UAVs bases, that is, link n becomes a node, then $D_{mn}^{\mathrm{1}}=D_{mn}^{\mathrm{2}}$ and $D_{mn}^{\mathrm{3}}=D_{mn}^{\mathrm{4}}$ ; formula (2) transforms into following formula:

$$\begin{array}{cc}& L^{\prime }\left(m,n\right)=\alpha D_{mn}^{\mathrm{1}}+\left(\mathrm{1}-\alpha \right)D_{mn}^{\mathrm{3}}.\end{array}$$

(4)

Let

$$\begin{array}{cc}& L\left(m,n\right)=L^{\prime }\left(m,n\right)+h\left(m,n\right),\end{array}$$

(5)

where $h(m,n)$ is the flight time on the monitored link and

$$\begin{array}{cc}& h\left(m,n\right)=\left\{\begin{array}{cc}l\left(m\right)\hfill & \text{when\hspace{0.17em}\hspace{0.17em}the\hspace{0.17em}\hspace{0.17em}first\hspace{0.17em}\hspace{0.17em}link\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}cruise\hspace{0.17em}\hspace{0.17em}route\hspace{0.17em}\hspace{0.17em}belongs\hspace{0.17em}\hspace{0.17em}to\hspace{0.17em}\hspace{0.17em}}{S}_{\mathrm{0}},\hfill \\ l\left(n\right)\hfill & \text{when\hspace{0.17em}\hspace{0.17em}the\hspace{0.17em}\hspace{0.17em}first\hspace{0.17em}\hspace{0.17em}link\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}cruise\hspace{0.17em}\hspace{0.17em}route\hspace{0.17em}\hspace{0.17em}belongs\hspace{0.17em}\hspace{0.17em}to\hspace{0.17em}\hspace{0.17em}}{S}_{\mathrm{1}}.\hfill \end{array}\right.\end{array}$$

(6)

$l(m)$ ,   $l(n)$ represent the flight time on links m and n, respectively. $L(m,n)$ is the sum of flight time monitored link and the flight time from link m to link n.

For UAV k, the total flight time of one patrolling mission $L_k^s$ is calculated by the equation as bellow

$$\begin{array}{cc}& L_k^s={\displaystyle \sum }_{m,n\in S_{\mathrm{0}},m\ne n}{L}_k\left(m,n\right)W_{m,n,k},\end{array}$$

(7)

in which $L_k(m,n)$ is the sum of flight time monitored link and the flight time from link m to link n for UAV k. $W_{m,n,k}$ is a binary variable; if UAV k flies from link m to link n, then $W_{m,n,k}=\mathrm{1}$ ; otherwise, it equals 0.

3.2. Model Established

In this paper, the optimization objectives are to minimize sum of uncollected information and minimize the total UAVs flight time. The optimization model is listed as follows.

The objective functions:

$$\begin{array}{cc}& \underset{}{\min }{\displaystyle \sum }_{m\in S_{\mathrm{0}}}{C}^F\left(m\right)x^F\left(m\right)\end{array}$$

(8)

$$\begin{array}{cc}& \min {\displaystyle \sum }_{k\in N_u}\hspace{0.17em}{\displaystyle \sum }_{m,n\in S_{\mathrm{0}},m\ne n}{L}_k\left(m,n\right)W_{m,n,k}.\end{array}$$

(9)

The constraints:

$$\begin{array}{cc}& \underset{k\in N_u}{{\displaystyle \bigvee }}{x}_{mk}\le {\displaystyle \sum }_{k\in N_u}\hspace{0.17em}{\displaystyle \sum }_{n\in S_{\mathrm{0}}}{W}_{m,n,k},\hspace{1em}\forall m\in S_{\mathrm{0}},\end{array}$$

(10)

$$\begin{array}{cc}& \underset{k\in N_u}{{\displaystyle \bigvee }}{x}_{mk}+x^F\left(m\right)=\mathrm{1},\hspace{1em}\forall m\in S_{\mathrm{0}},\end{array}$$

(11)

$$\begin{array}{cc}& {\displaystyle \sum }_{n\in S_{\mathrm{0}},n\ne m}{W}_{m,n,k}-{\displaystyle \sum }_{n\in S_{\mathrm{0}},n\ne m}{W}_{n,m,k}=\left\{\begin{array}{cc}\mathrm{1}\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}m\hspace{0.17em}\hspace{0.17em}\mathrm{i}\mathrm{s}\hspace{0.17em}\hspace{0.17em}\mathrm{t}\mathrm{h}\mathrm{e}\hspace{0.17em}\hspace{0.17em}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}\hspace{0.17em}\hspace{0.17em}\mathrm{p}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}\hspace{0.17em}\hspace{0.17em}\mathrm{o}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\mathrm{U}\mathrm{A}\mathrm{V}\hspace{0.17em}\hspace{0.17em}k,\hfill \\ -\mathrm{1}\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}m\hspace{0.17em}\hspace{0.17em}\mathrm{i}\mathrm{s}\hspace{0.17em}\hspace{0.17em}\mathrm{t}\mathrm{h}\mathrm{e}\hspace{0.17em}\hspace{0.17em}\mathrm{e}\mathrm{n}\mathrm{d}\hspace{0.17em}\hspace{0.17em}\mathrm{p}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}\hspace{0.17em}\hspace{0.17em}\mathrm{o}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\mathrm{U}\mathrm{A}\mathrm{V}\hspace{0.17em}\hspace{0.17em}k,\hfill \\ \mathrm{0}\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},\hfill \end{array}\right.\end{array}$$

(12)

$$\begin{array}{cc}& {\displaystyle \sum }_{k\in N_u}\hspace{0.17em}{\displaystyle \sum }_{n\in S_{\mathrm{0}}}{W}_{m,n,k}\le N_u,\end{array}$$

(13)

$$\begin{array}{cc}& {\displaystyle \sum }_{m,n\in S_{\mathrm{0}},m\ne n}{L}_k\left(m,n\right)W_{m,n,k}\le L_k,\end{array}$$

(14)

in which ⋁ is the fuzzy operator and represents taking the maximum value among all the elements; $C^F(m)$ represents the cost if link m cannot be detected by all UAVs, $m\in S_{\mathrm{0}}$ ; here the cost is uncollected information value; $x_{mk}$ is a binary variable; if link m is detected by UAV k, then $x_{mk}=\mathrm{1}$ ; otherwise, it is equal to 0; $x^F(m)$ is a binary variable; if ${\bigvee }_{k\in N_u}^{}{x}_{mk}=\mathrm{0}$ , then $x^F(m)=\mathrm{1}$ ; otherwise, it is equal to 0; namely, if link m cannot be detected by all UAVs, then $x_m^F=\mathrm{1}$ ; if link m can be detected by someone's UAV, then $x_m^F=\mathrm{0}$ ; $N_u$ is the number of UAVs; k is the subscript of UAV; $L_k$ is the longest flight time of UAV k.

Formula (10) is the UAVs detected constraint and ${\bigvee }_{k\in N_u}^{}{x}_{mk}$ is a variable to represent whether the link m is detected by an UAV. If ${\bigvee }_{k\in N_u}^{}{x}_{mk}=\mathrm{1}$ , then the link m is detected by an UAV; that is, it exists in k such that $W_{m,n,k}=\mathrm{1}$ . Otherwise, ${\bigvee }_{k\in N_u}^{}{x}_{mk}=\mathrm{0}$ indicates $W_{m,n,k}=\mathrm{0}$ , for all k. Formula (11) represents that link m must be detected or virtually detected exactly once. Formula (12) is a set of flow balance constraints, and each UAV departs and arrives airbase only once, when the depot of UAVs is located in link m; then for arbitrary $k\in N_u$ , formula (12) holds. Formula (13) is the constraint of maximum number of available UAVs. Formula (14) is the UAVs duration time constraint.

The traditional method of solving multiobjective optimization problem is to give different weights to different objective functions, and then multiobjective problem was converted into single-objective problem by linear combination. This approach is more intuitive and easier to operate for traffic managers, in order to obtain the satisfied program by which they can adjust the weights according to their needs directly. Thus, the proposed model is solved by introducing average weighting factors, and two objectives are normalized before the algorithm by using the following formulas:

$$\begin{array}{cc}& s_{\mathrm{1}}=\frac{p_{\mathrm{1}}}{{\sum }_{m\in S_{\mathrm{0}}}^{}{C}^F\left(m\right)}\times \mathrm{100}\%,\\ s_{\mathrm{2}}=\frac{p_{\mathrm{2}}}{{\sum }_{k=\mathrm{1}}^{N_u}{L}_k}\times \mathrm{100}\%,\end{array}$$

(15)

where $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ are the normalized values for objective 1 (formula (8)) and objective 2 (formula (9)), respectively. $p_{\mathrm{1}}$ and $p_{\mathrm{2}}$ are the values for objective 1 and objective 2, respectively.

The values of the final objective function P are calculated as follows:

$$\begin{array}{cc}& P={\omega }_{\mathrm{1}}{s}_{\mathrm{1}}+{\omega }_{\mathrm{2}}{s}_{\mathrm{2}},\end{array}$$

(16)

where ${\omega }_{\mathrm{1}}$ and ${\omega }_{\mathrm{2}}$ are the weight and ${\omega }_{\mathrm{1}}+{\omega }_{\mathrm{2}}=\mathrm{1}$ . P is smaller, and the solution is better.

4. Verification

The validity of proposed model is proofed through following small network. Here the beam search algorithm is used to solve the proposed model and realized by GAMS.

For simplicity, assume that the speed of UAVs is a constant; that is, the flight speed is the same value for all links.

In Figure 3, the network includes 6 nodes and 9 links. The flying time and information value of each link are listed in Table 1. Cruising complete network requires at least 247 minutes.

Table 1

The flying time and information value of links.

Link number	①	②	③	④	⑤	⑥	⑦	⑧	⑨
Flying time (min)	20	26	18	22	49	15	33	40	24
Information value	20	25	35	32	25	20	40	20	30

Figure 3

Topology of the example network.

Top four information value links had been installed fixed detectors, which are link ⑦, link ③, link ④, and link ⑨. Other links do not have fixed sensors which are shown by red line in Figure 4. These links should be detected by UAVs and the total information of undetected links is 110.

Figure 4

The current sensors on the network.

In the example, the UAVs airbase is located at node 3 which means the UAVs should start their tasks at node 3 and return to node 3, finally; $C^F(\mathrm{1})=\mathrm{20}$ , $C^F(\mathrm{2})=\mathrm{25}$ , $C^F(\mathrm{5})=\mathrm{25}$ , $C^F(\mathrm{6})=\mathrm{20}$ , and $C^F(\mathrm{8})=\mathrm{20}$ .

When the maximum duration time of UAVs $L_k$ is very large and $N_u=1$ , then one of the optimal cruising route is link ② → link ① → link ⑤ → link ⑧ → link ⑦ → link ⑥. The minimum flying time is 189 minutes and minimum undetected information value is 0.

The following let the maximum duration time of UAVs $L_k$ be 150 minutes for all k; then the proposed model is verified by two scenarios: $N_u=1$ and $N_u=2$ .

(1) $N_u=1$ . As can be found from above results, cruising all undetected routine, one UAV at least needs to fly 189 min; under constraint condition of UAV maximum endurance flight time is 150 min; cruising all undetected links needs at least two UAVs. Therefore, when only one UAV is available, through solving biobjective optimal model of minimum information amount of nondetect road and minimum flying time in this paper, obtain UAV optimize cruising route, as in Figure 5.

Figure 5

The optimal route for an UAV.

Route 1 is link ⑥ → link ③ → link ①→ link ②, the total flying time is 79 minutes, and the uncollected information is 45.

Route 2 is link ② → link ① → link ⑤ → link ④; the total flight time is 117 minutes; and the nondetect information is 40.

Here let ${\omega }_{\mathrm{1}}={\omega }_{\mathrm{2}}=0.5$ and according to formulae (14)-(15), then the values of the final objective function $P_{\mathrm{1}}$ of route 1 and $P_{\mathrm{2}}$ of route 2 are calculated as follows, respectively:

$$\begin{array}{cc}& P_{\mathrm{1}}=\mathrm{0.5}\times \frac{\mathrm{45}}{\mathrm{110}}+\mathrm{0.5}\times \frac{\mathrm{79}}{\mathrm{1}\times \mathrm{150}}=\mathrm{0.47},\\ P_{\mathrm{2}}=\mathrm{0.5}\times \frac{\mathrm{40}}{\mathrm{110}}+\mathrm{0.5}\times \frac{\mathrm{117}}{\mathrm{1}\times \mathrm{150}}=\mathrm{0.57}.\end{array}$$

(17)

Obviously, the route 1 is the optimal cruising path.

(2) $N_u=2$ . When two UAVs are available, the same as the above, $L_k=150\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}$ for $k=\mathrm{1,2}$ , we can obtain the following optimal cruising route, as in Figure 6.

Figure 6

Two UAVs’ optimal cruising route.

UAV 1 is link ② → link ① → link ⑤ → link ④ and the total flying time is 117 min.

UAV 2 is link ⑥ → link ⑦ → link ⑧ → link ④ and the total flying time is 110 min.

The cruising time of each two UAVs in above is less than 150, which is met the constraint (14). The total flying time of two is 227 min and nondetected information value is 0. Namely, two UAVs can detect all nonsensor links, and the minimum flying time is 227 min.

As above, ${\omega }_{\mathrm{1}}={\omega }_{\mathrm{2}}=0.5$ , then the values of the final objective function P is calculated as follows:

$$\begin{array}{cc}& P=\mathrm{0.5}\times \frac{\mathrm{0}}{\mathrm{110}}+\mathrm{0.5}\times \frac{\mathrm{227}}{\mathrm{150}+\mathrm{150}}=\mathrm{0.38}.\end{array}$$

(18)

The above numerical examples show that the UAVs route optimization method is feasibility and effectiveness.

5. Conclusions

The fixed sensor-oriented traffic sensor network design problem has been widely studied. With UAVs as a special type of mobile sensors, this paper aims to propose a practically useful and computationally efficient UAVs routing model for daily traffic information collected. In this paper, cruise route planning problem of UAVs is developed based on the highway network physical structure. A multiobjective optimization model is proposed to minimize the total cruise time and minimize the information value nondetected by UAVs. Finally, a case study is used to demonstrate the results of proposed model in UAVs’ route planning.