# Optimization of Pesticide Spraying Tasks via Multi-UAVs Using Genetic Algorithm

Authors: He Luo; Yanqiu Niu; Moning Zhu; Xiaoxuan Hu; Huawei Ma
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Task allocation is the key factor in the spraying pesticides process using unmanned aerial vehicles (UAVs), and maximizing the effects of pesticide spraying is the goal of optimizing UAV pesticide spraying. In this study, we first introduce each UAV’s kinematic constraint and extend the Euclidean distance between fields to the Dubins path distance. We then analyze the two factors affecting the pesticide spraying effects, which are the type of pesticides and the temperature during the pesticide spraying. The time window of the pesticide spraying is dynamically generated according to the temperature and is introduced to the pesticide spraying efficacy function. Finally, according to the extensions, we propose a team orienteering problem with variable time windows and variable profits model. We propose the genetic algorithm to solve the above model and give the methods of encoding, crossover, and mutation in the algorithm. The experimental results show that this model and its solution method have clear advantages over the common manual allocation strategy and can provide the same results as those of the enumeration method in small-scale scenarios. In addition, the results also show that the algorithm parameter can affect the solution, and we provide the optimal parameters configuration for the algorithm.


---

## Body

## 1. Introduction

With the development of artificial intelligence and unmanned processes in agriculture, UAVs have rapidly become an important platform in agricultural aviation operations due to their high efficiency, low labor intensity, and low comprehensive cost, and they have been widely applied in precision seeding, vegetation testing, pesticide spraying, and other agricultural aviation operations [1, 2]. The current operation of UAVs to carry out agricultural aviation work is mainly through manual remote control. Therefore, the actual results of the work are closely related to the skill level of the operator. The workload of the operator increases with the increased number of UAVs and tasks. This may cause high missing and repetition rates in operations. Thus, with the minimum of human intervention, using UAVs to complete agricultural aviation operations tasks autonomously has attracted widespread attention.Pesticide spraying requires multi-UAVs to do blanket spraying on multiple farmlands. Such tasks not only need to ensure that all crops in the farmland are sprayed but also need to assign a specific task sequence and flight trajectory for each UAV in order for them to fly between multiple farmlands. For pesticide spraying assignments, without considering the UAV flight trajectory inside the farmland, each farmland can be abstracted as a task point, and the process of UAV visiting all task points can be described as the traveling salesman problem (TSP). However, due to UAV flight distance and the factors of farm size, number, and distribution, it is difficult for the UAV to traverse all the farmlands in a single flight. Therefore, we regard the assignment of pesticide spraying tasks as a team orienteering problem (TOP). With this problem, as the efficacy of pesticide spraying is mainly related to the temperature during spraying [3], the time window of spraying each farmland varies. Meanwhile, the UAV spraying strategy within a farmland can affect the UAV flight distance and change the time for the UAV to reach the next farmland, thus affecting the efficacy of the pesticide spraying for the next farmland. Therefore, the farmland cannot be abstracted as a task point in the pesticide spraying task assignment process. We need to consider not only the task allocation scheme and order of execution but also the UAV flight trajectory inside and outside of the farmland.Thus, the optimization of multi-UAV pesticide spraying assignments studied in this paper can be described as requiring that multi-UAVs must spray pesticides for multiple farmlands in the time window and that each farmland can be sprayed by only one UAV. Under a variety of factors, we selected the appropriate farmland from the candidate farmlands and assigned the UAV for pesticide spraying, the spraying order, and spraying method to maximize the efficacy of the pesticide spraying [4]. To this end, we proposed a Dubins team orienteering problem- (DTOP-) variable time windows- (VTW-) variable profits (VP) model. Compared to the regular TOP, this model facilitated research on the following three aspects of pesticide spraying.First, this model extends the TOP model to the DTOP model by taking into account the impact of the each UAV’s turning radius on UAV flight time. In the process of UAV pesticide spraying, it is necessary to adjust the flight direction at the edge of the farmland according to the minimum turning radius in order to achieve the spray coverage for the farmland. Meantime, the UAVs are subject to kinematics and dynamics in the course of flight. At this time, UAV flight distance is not described by the Euclidean distance in the regular TOP but by the length of the Dubins path [5]. Therefore, the distance between the two farmlands discussed in this paper is described in terms of Dubins path length. Because there are many changes in the points where the UAV enters and leaves the farmland, there are multiple Dubins paths between the two farmlands, which is described herein as the DTOP model.Second, in the regular team orienteering problem with time windows (TOPTW), the time window is generally divided into two categories: one is from the perspective of the points of interests (POIs) to generate multiple fixed target access time windows based on the opening hours [6]; the other is from the perspective of the customers to generate multiple fixed available time windows based on each customer’s time slots [7]. Obviously, the creation of these time windows is static or predetermined. However, the time window in which the farmland can be sprayed with pesticides is affected by the temperature, and the resulting time window would change with the temperature. These time windows are the type of time window with uncertainties which is manifested by the uncertainty of the number and length of time windows. Therefore, we determined the time window based on the dynamics of the temperature and extended the DTOP model to the DTOP-VTW model.Third, in the orienteering problem with variable profits (OPVP), the profit from visiting each node and the visiting time are related by a concave or convex function [8]. However, for the pesticide spraying process, the profit from each farmland after spraying pesticides also changes with the temperature [9]. The relation between the efficacy of the sprayed farmland and the time is not fixed on one function, and it could be another functional relationship. Therefore, we calculated the spraying efficacy based on the dynamics of temperature in this paper and extended the DTOP-VTW model further to the DTOP-VTW-VP model.In terms of the model solution, solving the TOP has been proven to be a typical NP-hard (nondeterministic polynomial-time hard) problem [10]. Although the exact algorithm can be used to obtain the optimal TOP solution, it is difficult to obtain the optimal solution within the polynomial solvable time when the scale of the problem increases. Therefore, we can only use the heuristic algorithm to obtain the solution [11]. At present, there are many heuristic algorithms used to solve the TOP. Among them, the GA has been proven to be an effective heuristic algorithm for solving the TOP [12]. It is very effective in solving standard benchmark instances and can obtain better results by adjusting the corresponding parameter configuration. In solving practical problems, the GA is also used as an efficient algorithm for solving the problem of task assignment and trajectory optimization [5]. In most cases, it exhibits better results [13] and shorter solution times [14] than other algorithms. Therefore, we used the GA to solve the DTOP-VTW-VP in this study.The rest of this paper is organized as follows. The researches related to this topic are reviewed and analyzed in Section2. In Section 3, the DTOP-VTW-VP model under the impact of temperature is proposed. The GA based on the model solution algorithm is detailed in Section 4. The numerical experiments and comparative experiments conducted are described in Section 5, and conclusions are presented in Section 6.


## 2. Related Work

TOP is an extension of the orienteering problem (OP). The OP is also referred to as the selective traveling salesman problem (STSP) [15]. So, when the objective function in the STSP is only a profit and there are targets that are not visited, the STSP is the TOP [16]. In the TOP, several members are given, and each member starts from the same starting point within the specified time and score to the same ending point. In this process, after the target is visited by a member for the first time, the member can obtain the appropriate score. Each member needs to visit as many targets as possible, so that the total score of all members can be maximized [17]. The TOP has two characteristics [4, 18]: the objective function is the maximum total profit and all targets are visited, at most, once. Clearly, for such problems, it is difficult to build the vehicle routing problem (VRP) model because the goal of the VRP is to use the minimum number of vehicles to serve all the vertices or to use the minimum total travel distance with a fixed number of vehicles [19, 20]. Currently, the TOP has been widely used in solving tourist trip design problems [6, 10, 21], mobile crowdsourcing problems [22–24], UAV task allocation problems [25, 26], pharmaceutical sales representative planning problems [27], and resource management allocation problem during wildfires [28].In the above-mentioned application scenarios, the path length between targets is generally considered to be fixed, such as the distance between different POIs, the distance between hospitals, and the distance between the locations on wildfire. To solve these types of problems, one only needs to select and combine the existing routes to maximize the total profits [4, 18]. However, for UAV task allocation problems, due to the constraints of the UAV’s kinematic constraints, the distance between targets visited by UAVs is no longer Euclidean distance but rather Dubins path length. The Dubins path is a feasible trajectory of the minimum length over a bounded curvature trajectory at a constant rate [29], and it has been widely used in the field of UAV trajectory planning [5, 30–32]. In addition, for multi-UAV pesticide spraying assignment problems, due to the many possible points for UAVs to enter and exit the farmland, there are multiple Dubins paths between farmlands. When all of the farmlands must be sprayed with pesticides, the problem can be regarded as a DTSP [33–35] and can be solved by using decoupling methods and transformation methods. However, in the case where UAVs cannot spray pesticides for all farmlands due to the constraints of flight distances and profits of targets, the problem is described as a Dubins traveling salesman problem (DTOP). To solve this model, we need to determine the visiting order of the targets under the condition that the trajectory length is changeable.At the same time, when the visiting of targets must be completed within a time window, the TOP is extended to the TOP with time windows [36]. According to the number of time windows, the TOP can be further divided into single time window (TOP-TW) or multiple time windows (TOP-MTW) problems, which are NP-hard problems [37]. In the TOP-TW, each vertex has a fixed time window [11, 38, 39], and the time window constraints require that the visit to the vertex must start within the specified time [40]. In the TOP-MTW, each vertex can have multiple fixed time windows. According to the different standards of classification, the time windows are divided into the following two categories. The first is to determine different time windows according to the available visiting time of each target. For example, the opening hours of different points are different, and the working hours of the same point are intermittent. Therefore, multiple fixed time windows are generated [6]. The second category is to classify the time windows according to the customers’ time slots, such as those based on the fact that different visitors have different amounts of free time during the trip to generate multiple fixed time windows [7]. As for problems with the above two cases occurring at the same time, literature [41] includes a study of tourist trip problems under the constraints of opening hours of points and tourist time. There are related studies in other models on multiple time windows, such as the VRP about multiple time windows [42, 43], and the TSP of multiple time windows [44]. However, for UAV task allocation problems, due to the fact that the time when the farmland can be sprayed with pesticides changes with the temperature, the resulting time windows have the characteristic of uncertainty.In terms of the profit of the targets, the goal of the OP and TOP is to maximize the profits of all targets after the selection of the routes. Under normal circumstances, the profit of each target is fixed [45, 46]. However, the spraying efficacy for each farmland changes with time in UAV task allocation problems. The model of this type of problem is similar to the OPVP. OPVP is a special case of the optional TSP (STSP), and it is also an NP-hard problem [8]. In the OPVP, the relationship between the profit of target and time can be a concave or convex function, such as the relationship between the profit of being able to catch the fish and time in fishing operations or the relationship between the profit of the time length of viewing a program and time [8]. These relationships can randomly change with the normal distribution function [47]. However, in the process of UAV pesticide spraying task allocation, the profit of each farmland after spraying the pesticides does not necessarily change with time and completely exhibits the above-described concave or convex functional relationship. There may be a diminishing profit relationship [48] or any other type of functional relationship.Currently, the GA [49], branch-and-cut algorithm [50], tabu search algorithm [51], simulated annealing algorithm [11, 41], ant colony algorithm [38], and so forth are usually used to solve the regular TOP or extended TOP models. Through analyzing the results of solving 24 standard TOP benchmark instances using a heuristic algorithm, Ferreira et al. believed that the GA’s results for 60% of the benchmark instances were better than those from other heuristic algorithms [12] and proved that using GA to solve the TOP within the acceptable time can produce good results. When solving the OP with time windows [52] or OP with stochastic profits [47], the GA results have advantages over those from other heuristic algorithms. Meanwhile, in practical application processes such as UAVs task allocation [53] and mission planning [54], the GA not only requires less calculating time [14] but also gives better results [13].


## 3. Problem Description and Formulation

The characteristics of the pesticide spraying task make the number and length of time windows in which the farmland can be sprayed affected by the temperature, and the efficacy of spraying pesticide (i.e., the profit in the model) is also affected by the temperature. At the same time, the UAV’s performance, size of the farmlands, trajectories of pesticide spraying, and flight trajectories of UAVs between farmlands all have impacts on the results of the allocated tasks. In this regard, this section describes in detail the TOP proposed for UAVs to carry out pesticide spraying tasks, with variable profits and variable time windows under the impact of the ambient temperature.


### 3.1. UAVs

Consider(1)U=U1,U2,…,UNUdenotes the set of NU UAVs performing the spraying tasks, and each UAV can carry only one type of pesticide. During the flight, all of the UAVs have the same minimum turning radius RU and flight speed V and carry a nozzle with a spray radius of RD.Considering the characteristics of UAVs performing pesticide spraying, we make the following assumptions:(1)
UAVs have the ability to automatically avoid obstacles. In the face of a collision, UAVs can use the control strategy of self-circumvention, and the resulting path deviation relative to the length of the total flight trajectory is very small and negligible.(2)
UAVs fly at the same cruising speed and same cruising altitude, so that the impacts of these factors on the spray effect are not considered.(3)
The impacts of the external environments on a UAV’s flight trajectory are not considered.(4)
UAVs can carry the pesticides required to carry out the task, but the amount of fuel carried is limited.


### 3.2. Farmlands

Set(2)A0,ANA+1as the starting and ending points of UAVs,(3)A1,A2,…,ANA,as the NA rectangular farmlands to be sprayed with pesticides, and Ai as a rectangle with an area of Di. The set of UAV beginning point, the farmlands, and ending point are (4)A=A0,A1,A2,…,ANA,ANA+1.When Uu overlays spraying pesticides for Ai, a UAV’s entering point to the farmland is Iniu, its exit point is Outiu, and it is assumed that the UAV can only leave after it has completely sprayed the entire farmland. At the same time, each farmland can only be sprayed, at most, once.


### 3.3. Time Window

The temperature range over which pesticide spraying can achieve a satisfactory level of efficacy is limited; therefore, only one or several time snippets can be used in a day. The time snippets are defined as the time windows in which pesticide spraying tasks can be carried out.The temperature rangeTSC,TSO in which the farmland can be sprayed with pesticides generates W time windows Oiwu,Ciwu for a UAV to carry out the tasks, where Oiwu and Ciwu represent the beginning and ending times in the time window w for the UAV to spray pesticides on the farmlands.In general, the temperature in a day usually changes from low to high and then from high to low. This pattern can be approximated as a quadratic function distribution or a normal distribution. The temperature range in which the farmland can be sprayed with pesticides can further generate three types of time windows, as shown in Figure1, when(5)Tmax<Tso.UAVs do not have any time window to do pesticide spraying; when(6)Tso<Tmax<Tsc,only one time window can be generated to carry out the tasks; when (7)Tsc<Tmax,only two time windows can be generated. Thus, for the pesticide spraying assignment problems described in this paper, the number of time windows may be 1 or 2.Figure 1
Relationship between daily temperature and time windows.
(a)
(b)
(c)


### 3.4. Flight Trajectory

When spraying pesticides, UAVs not only conduct the covered spray inside the farmland but also need to fly among different farmlands to complete the pesticide spraying tasks. Therefore, there are two types of flight trajectories: that inside the farmland and that between farmlands.


#### 3.4.1. Flight Trajectory inside the Farmland

WithinAi, UAVs fly along Dubins paths under kinematic constraints and conduct the covered pesticide spray using back-and-forth path strategy. During this process, Uu enters Ai from point Iniu in time window w. After entering the farmland, the flight trajectory is parallel to one of the farmland’s edges, and then the UAV exits the farmland from point Outiu. At this time, the time that it takes Uu to spray farmland is tiwu.The back-and-forth path strategy is one of the most optimal strategies for UAVs to conduct covered pesticide spray on rectangular farmlands. It is also the most convenient control strategy to implement and is widely applied to tasks for covered areas [55]. There are two implementations of this strategy, namely, parallel track search and creeping line search [56].For example, in Figure2(a), there are two ways to execute a covered scan of the rectangular area. One is the parallel track search [as shown in Figure 2(b)] and the other is the creeping line search [as shown in Figure 2(c)].Figure 2
Schematic of farmland spraying.
(a)
(b)
(c)At the same time, both the position of a UAV entering the rectangle and the UAV’s actual turning radius at the edge of the rectangle have impacts on the length of the UAV’s flight trajectory inside the farmland. Although the UAV can enter the farm from any point on the edge, the entering point with the shortest flight trajectory for UAVs to cover a rectangular area is the point that has a distance ofRD to the apex of the farmland, according to literature [55]. Therefore, UAV’s entry points into the rectangular area are discretized in this paper. We have chosen eight points,(8)RD1,RD2,…,RD8,on the edges of the rectangle with a distance of RD to the four vertexes of the rectangle as the entry points for the UAVs to enter the rectangular area. For a UAV to have the shortest covered flight trajectory in a rectangular region, it must enter the rectangular area from one of the eight entry points. The UAV’s exit point on the shortest trajectory of the rectangular area is also uniquely determined.


#### 3.4.2. Flight Trajectory between Farmlands

After spraying pesticides for farmlandAi in time window w, the UAV needs to spray for Aj. Thus, the UAV must fly along the Dubins path between Ai and Aj [57]. Meanwhile, the UAV does not spray pesticides when flying between farmlands. The beginning point of this trajectory is Uu’s exit point Outiu from Ai, the ending point is Uu’s entry point Inju to Aj, and the time spent on the Dubins path is tijwu.For example, Figure3 describes a UAV’s flight trajectory between farmlands under the kinematic constraints. According to the generating principle of a Dubins path [31], the UAV starts from RD6 of Ai, turns right (denoted by R), and flies along the arc path and then along a straight linear path (denoted by S), and finally turns left (denoted by L) and takes the arc flight path to arrive at RD1 of Aj. Owing to the back-and-forth path strategy used inside the farmland, the angles of the UAV entering or leaving the farmland must be perpendicular to the edge of the farmland. Therefore, in the process of optimizing the shortest Dubins path, the angles of the UAV at the beginning point and ending point are determined, and the varying factors are Uu’s exit point Outiu from Ai and the entering point of Inju to Aj.Figure 3
Dubins flight path under the RSL circumstance.
(a)
(b)Although the lengths of the flight trajectory and flight duration in Figure3(a) are greater than those in Figure 3(b), this does not mean the result of pesticide spraying by the UAV is worse. The overall optimal result is affected by flight trajectories both inside and outside of the farmland.


### 3.5. Task Profit

Since the spraying equipment, spraying method, and other hardware and software conditions have been determined, a task profit in this paper is defined by the efficacy of pesticide spraying by a UAV on a farmland.When a UAV sprays pesticides on farmlands, the spraying efficacy is closely related to temperature and temperature will differ with changes in time. Therefore, the efficacy of a UAV spraying pesticides on farmlandAi within time window w can be described by the efficacy function Piw(t) over time t. While using different type of pesticides, Piw(t) may manifest as a concave function, convex function, normal distribution, or linear decreasing function.Suppose thatUu begins to spray pesticides on farmland Ai with an area of Di at siwu in time window w, and it takes tiwu for Uu to spray the entire farmland Ai in time window w. The task profit can be defined as(9)SPiwu=Di104∗∫siwusiwu+tiwuPiwtdttiwu.


### 3.6. DTOP-VTW-VP Model

For the pesticide spraying task allocation problem described in this paper, we take the DTOP-VTW-VP as the model.NU UAVs and NA farmlands are given, and each farmland Aii∈1,2,…,NA has W time windows. A0 is the starting point, and ANA+1 is the ending point. siwu is the starting time for UAV Uu to spray pesticides on farmland Ai in time window w, tiwu is the spraying time for UAV Uu to spray pesticides on farmland Ai in time window w, and tijwu is the flight time for UAV Uu flying between farmlands Ai and Aj within time window w. Note that Oiwu and Ciwu are the opening time and closing time in time window w for UAV Uu to spray pesticides on farmland Ai. Ewu is the longest flight time for UAV Uu in time window w and M is a large constant.Two decision variables are used:xiwu=1 if UAV Uu completes the pesticide spraying task for farmland Ai within time window w and 0 otherwise; yijwu=1 if UAV Uu begins to fly between Ai and Aj within time window w and 0 otherwise.The objective function of optimization is defined as the maximization of the total task profits for all the UAVs. The formulation of the DTOP-VTW-VP is the following:(10)J=max⁡∑u=1NU∑w=1W∑i=1NASPiwuxiwu,(11)∑u=1NU∑w=1W∑i=0NAyiNAwu=∑u=1NU∑w=1W∑j=1NA+1y1jwu=WNU,(12)∑i=0NAyikwu=∑j=1NA+1ykjwu=xkwu;∀k=1,…,NA;∀u=1,…,NU;∀w=1,…,W,(13)siwu+tijwu-sjwu≤M1-yijwu;∀i,j=0,…,NA+1;∀u=1,…,NU;∀w=1,…,W,(14)∑u=1NU∑w=1Wxiwu≤1;∀i=0,…,NA+1,(15)Oiwu≤siwu≤Ciwu,tiwu≤Ciwu-siwu;∃w∈1,2,…,W;∀i=1,…,NA;∀u=1,…,NU,(16)∑i=0NA+1xiwutiwu+yijwutijwu≤Ewu;∀u=1,…,NU;∀w=1,…,W,(17)xiwu∈1,0;yijwu∈1,0;∀i,j=0,…,NA+1;∀u=1,…,NU;w=1,…,W.The objective function (10) maximizes the total tasks profits for all the UAVs. Constraint (11) ensures that all routes have the same starting point and ending point, and the number of routes is the sum of UAV routes in each time window. Constraint (12) ensures the connectivity of the route. Constraint (13) shows that the spraying time is needed when visiting farmlands. Constraint (14) ensures that each farmland can be visited at most once in all of time windows. Constraint (15) ensures that the time of spraying must be within time window. Constraint (16) transforms the UAV’s fuel limitation to the limitation of the UAV’s flight time. Constraint (17) defines the decision variables.


## 3.1. UAVs

Consider(1)U=U1,U2,…,UNUdenotes the set of NU UAVs performing the spraying tasks, and each UAV can carry only one type of pesticide. During the flight, all of the UAVs have the same minimum turning radius RU and flight speed V and carry a nozzle with a spray radius of RD.Considering the characteristics of UAVs performing pesticide spraying, we make the following assumptions:(1)
UAVs have the ability to automatically avoid obstacles. In the face of a collision, UAVs can use the control strategy of self-circumvention, and the resulting path deviation relative to the length of the total flight trajectory is very small and negligible.(2)
UAVs fly at the same cruising speed and same cruising altitude, so that the impacts of these factors on the spray effect are not considered.(3)
The impacts of the external environments on a UAV’s flight trajectory are not considered.(4)
UAVs can carry the pesticides required to carry out the task, but the amount of fuel carried is limited.


## 3.2. Farmlands

Set(2)A0,ANA+1as the starting and ending points of UAVs,(3)A1,A2,…,ANA,as the NA rectangular farmlands to be sprayed with pesticides, and Ai as a rectangle with an area of Di. The set of UAV beginning point, the farmlands, and ending point are (4)A=A0,A1,A2,…,ANA,ANA+1.When Uu overlays spraying pesticides for Ai, a UAV’s entering point to the farmland is Iniu, its exit point is Outiu, and it is assumed that the UAV can only leave after it has completely sprayed the entire farmland. At the same time, each farmland can only be sprayed, at most, once.


## 3.3. Time Window

The temperature range over which pesticide spraying can achieve a satisfactory level of efficacy is limited; therefore, only one or several time snippets can be used in a day. The time snippets are defined as the time windows in which pesticide spraying tasks can be carried out.The temperature rangeTSC,TSO in which the farmland can be sprayed with pesticides generates W time windows Oiwu,Ciwu for a UAV to carry out the tasks, where Oiwu and Ciwu represent the beginning and ending times in the time window w for the UAV to spray pesticides on the farmlands.In general, the temperature in a day usually changes from low to high and then from high to low. This pattern can be approximated as a quadratic function distribution or a normal distribution. The temperature range in which the farmland can be sprayed with pesticides can further generate three types of time windows, as shown in Figure1, when(5)Tmax<Tso.UAVs do not have any time window to do pesticide spraying; when(6)Tso<Tmax<Tsc,only one time window can be generated to carry out the tasks; when (7)Tsc<Tmax,only two time windows can be generated. Thus, for the pesticide spraying assignment problems described in this paper, the number of time windows may be 1 or 2.Figure 1
Relationship between daily temperature and time windows.
(a)
(b)
(c)


## 3.4. Flight Trajectory

When spraying pesticides, UAVs not only conduct the covered spray inside the farmland but also need to fly among different farmlands to complete the pesticide spraying tasks. Therefore, there are two types of flight trajectories: that inside the farmland and that between farmlands.


### 3.4.1. Flight Trajectory inside the Farmland

WithinAi, UAVs fly along Dubins paths under kinematic constraints and conduct the covered pesticide spray using back-and-forth path strategy. During this process, Uu enters Ai from point Iniu in time window w. After entering the farmland, the flight trajectory is parallel to one of the farmland’s edges, and then the UAV exits the farmland from point Outiu. At this time, the time that it takes Uu to spray farmland is tiwu.The back-and-forth path strategy is one of the most optimal strategies for UAVs to conduct covered pesticide spray on rectangular farmlands. It is also the most convenient control strategy to implement and is widely applied to tasks for covered areas [55]. There are two implementations of this strategy, namely, parallel track search and creeping line search [56].For example, in Figure2(a), there are two ways to execute a covered scan of the rectangular area. One is the parallel track search [as shown in Figure 2(b)] and the other is the creeping line search [as shown in Figure 2(c)].Figure 2
Schematic of farmland spraying.
(a)
(b)
(c)At the same time, both the position of a UAV entering the rectangle and the UAV’s actual turning radius at the edge of the rectangle have impacts on the length of the UAV’s flight trajectory inside the farmland. Although the UAV can enter the farm from any point on the edge, the entering point with the shortest flight trajectory for UAVs to cover a rectangular area is the point that has a distance ofRD to the apex of the farmland, according to literature [55]. Therefore, UAV’s entry points into the rectangular area are discretized in this paper. We have chosen eight points,(8)RD1,RD2,…,RD8,on the edges of the rectangle with a distance of RD to the four vertexes of the rectangle as the entry points for the UAVs to enter the rectangular area. For a UAV to have the shortest covered flight trajectory in a rectangular region, it must enter the rectangular area from one of the eight entry points. The UAV’s exit point on the shortest trajectory of the rectangular area is also uniquely determined.


### 3.4.2. Flight Trajectory between Farmlands

After spraying pesticides for farmlandAi in time window w, the UAV needs to spray for Aj. Thus, the UAV must fly along the Dubins path between Ai and Aj [57]. Meanwhile, the UAV does not spray pesticides when flying between farmlands. The beginning point of this trajectory is Uu’s exit point Outiu from Ai, the ending point is Uu’s entry point Inju to Aj, and the time spent on the Dubins path is tijwu.For example, Figure3 describes a UAV’s flight trajectory between farmlands under the kinematic constraints. According to the generating principle of a Dubins path [31], the UAV starts from RD6 of Ai, turns right (denoted by R), and flies along the arc path and then along a straight linear path (denoted by S), and finally turns left (denoted by L) and takes the arc flight path to arrive at RD1 of Aj. Owing to the back-and-forth path strategy used inside the farmland, the angles of the UAV entering or leaving the farmland must be perpendicular to the edge of the farmland. Therefore, in the process of optimizing the shortest Dubins path, the angles of the UAV at the beginning point and ending point are determined, and the varying factors are Uu’s exit point Outiu from Ai and the entering point of Inju to Aj.Figure 3
Dubins flight path under the RSL circumstance.
(a)
(b)Although the lengths of the flight trajectory and flight duration in Figure3(a) are greater than those in Figure 3(b), this does not mean the result of pesticide spraying by the UAV is worse. The overall optimal result is affected by flight trajectories both inside and outside of the farmland.


## 3.4.1. Flight Trajectory inside the Farmland

WithinAi, UAVs fly along Dubins paths under kinematic constraints and conduct the covered pesticide spray using back-and-forth path strategy. During this process, Uu enters Ai from point Iniu in time window w. After entering the farmland, the flight trajectory is parallel to one of the farmland’s edges, and then the UAV exits the farmland from point Outiu. At this time, the time that it takes Uu to spray farmland is tiwu.The back-and-forth path strategy is one of the most optimal strategies for UAVs to conduct covered pesticide spray on rectangular farmlands. It is also the most convenient control strategy to implement and is widely applied to tasks for covered areas [55]. There are two implementations of this strategy, namely, parallel track search and creeping line search [56].For example, in Figure2(a), there are two ways to execute a covered scan of the rectangular area. One is the parallel track search [as shown in Figure 2(b)] and the other is the creeping line search [as shown in Figure 2(c)].Figure 2
Schematic of farmland spraying.
(a)
(b)
(c)At the same time, both the position of a UAV entering the rectangle and the UAV’s actual turning radius at the edge of the rectangle have impacts on the length of the UAV’s flight trajectory inside the farmland. Although the UAV can enter the farm from any point on the edge, the entering point with the shortest flight trajectory for UAVs to cover a rectangular area is the point that has a distance ofRD to the apex of the farmland, according to literature [55]. Therefore, UAV’s entry points into the rectangular area are discretized in this paper. We have chosen eight points,(8)RD1,RD2,…,RD8,on the edges of the rectangle with a distance of RD to the four vertexes of the rectangle as the entry points for the UAVs to enter the rectangular area. For a UAV to have the shortest covered flight trajectory in a rectangular region, it must enter the rectangular area from one of the eight entry points. The UAV’s exit point on the shortest trajectory of the rectangular area is also uniquely determined.


## 3.4.2. Flight Trajectory between Farmlands

After spraying pesticides for farmlandAi in time window w, the UAV needs to spray for Aj. Thus, the UAV must fly along the Dubins path between Ai and Aj [57]. Meanwhile, the UAV does not spray pesticides when flying between farmlands. The beginning point of this trajectory is Uu’s exit point Outiu from Ai, the ending point is Uu’s entry point Inju to Aj, and the time spent on the Dubins path is tijwu.For example, Figure3 describes a UAV’s flight trajectory between farmlands under the kinematic constraints. According to the generating principle of a Dubins path [31], the UAV starts from RD6 of Ai, turns right (denoted by R), and flies along the arc path and then along a straight linear path (denoted by S), and finally turns left (denoted by L) and takes the arc flight path to arrive at RD1 of Aj. Owing to the back-and-forth path strategy used inside the farmland, the angles of the UAV entering or leaving the farmland must be perpendicular to the edge of the farmland. Therefore, in the process of optimizing the shortest Dubins path, the angles of the UAV at the beginning point and ending point are determined, and the varying factors are Uu’s exit point Outiu from Ai and the entering point of Inju to Aj.Figure 3
Dubins flight path under the RSL circumstance.
(a)
(b)Although the lengths of the flight trajectory and flight duration in Figure3(a) are greater than those in Figure 3(b), this does not mean the result of pesticide spraying by the UAV is worse. The overall optimal result is affected by flight trajectories both inside and outside of the farmland.


## 3.5. Task Profit

Since the spraying equipment, spraying method, and other hardware and software conditions have been determined, a task profit in this paper is defined by the efficacy of pesticide spraying by a UAV on a farmland.When a UAV sprays pesticides on farmlands, the spraying efficacy is closely related to temperature and temperature will differ with changes in time. Therefore, the efficacy of a UAV spraying pesticides on farmlandAi within time window w can be described by the efficacy function Piw(t) over time t. While using different type of pesticides, Piw(t) may manifest as a concave function, convex function, normal distribution, or linear decreasing function.Suppose thatUu begins to spray pesticides on farmland Ai with an area of Di at siwu in time window w, and it takes tiwu for Uu to spray the entire farmland Ai in time window w. The task profit can be defined as(9)SPiwu=Di104∗∫siwusiwu+tiwuPiwtdttiwu.


## 3.6. DTOP-VTW-VP Model

For the pesticide spraying task allocation problem described in this paper, we take the DTOP-VTW-VP as the model.NU UAVs and NA farmlands are given, and each farmland Aii∈1,2,…,NA has W time windows. A0 is the starting point, and ANA+1 is the ending point. siwu is the starting time for UAV Uu to spray pesticides on farmland Ai in time window w, tiwu is the spraying time for UAV Uu to spray pesticides on farmland Ai in time window w, and tijwu is the flight time for UAV Uu flying between farmlands Ai and Aj within time window w. Note that Oiwu and Ciwu are the opening time and closing time in time window w for UAV Uu to spray pesticides on farmland Ai. Ewu is the longest flight time for UAV Uu in time window w and M is a large constant.Two decision variables are used:xiwu=1 if UAV Uu completes the pesticide spraying task for farmland Ai within time window w and 0 otherwise; yijwu=1 if UAV Uu begins to fly between Ai and Aj within time window w and 0 otherwise.The objective function of optimization is defined as the maximization of the total task profits for all the UAVs. The formulation of the DTOP-VTW-VP is the following:(10)J=max⁡∑u=1NU∑w=1W∑i=1NASPiwuxiwu,(11)∑u=1NU∑w=1W∑i=0NAyiNAwu=∑u=1NU∑w=1W∑j=1NA+1y1jwu=WNU,(12)∑i=0NAyikwu=∑j=1NA+1ykjwu=xkwu;∀k=1,…,NA;∀u=1,…,NU;∀w=1,…,W,(13)siwu+tijwu-sjwu≤M1-yijwu;∀i,j=0,…,NA+1;∀u=1,…,NU;∀w=1,…,W,(14)∑u=1NU∑w=1Wxiwu≤1;∀i=0,…,NA+1,(15)Oiwu≤siwu≤Ciwu,tiwu≤Ciwu-siwu;∃w∈1,2,…,W;∀i=1,…,NA;∀u=1,…,NU,(16)∑i=0NA+1xiwutiwu+yijwutijwu≤Ewu;∀u=1,…,NU;∀w=1,…,W,(17)xiwu∈1,0;yijwu∈1,0;∀i,j=0,…,NA+1;∀u=1,…,NU;w=1,…,W.The objective function (10) maximizes the total tasks profits for all the UAVs. Constraint (11) ensures that all routes have the same starting point and ending point, and the number of routes is the sum of UAV routes in each time window. Constraint (12) ensures the connectivity of the route. Constraint (13) shows that the spraying time is needed when visiting farmlands. Constraint (14) ensures that each farmland can be visited at most once in all of time windows. Constraint (15) ensures that the time of spraying must be within time window. Constraint (16) transforms the UAV’s fuel limitation to the limitation of the UAV’s flight time. Constraint (17) defines the decision variables.


## 4. GA for DTOP-VTW-VP

The GA is used to solve the DTOP-VTW-VP in this paper. In the algorithm, the initial population is generated by amount of chromosomes which represent different solutions of this problem, and it is updated by three operators: selection, crossover, and mutation. The process continues until the satisfactory solution is obtained or the maximum iteration is reached. The specific process is shown in Figure4.Figure 4
GA flowchart for DTOP-VTW-VP.


### 4.1. Encoding

Chromosome encoding represents a selected solution to the problem. A feasible solution for the DTOP-VTW-VP can be formed by determining the entry point of the UAV visiting the farmland, the starting time, and the visiting order. Therefore, the chromosome corresponds to the serial number of the farmland, UAV and entry point of the farmland, and the starting time of the UAV visiting the first farmland in each route. Among them, the serial number of the farmland belongs to the set(18)1,2,…,NA,the UAV’s serial numbers belong to the set(19)0,1,…,NU,and the serial number of the entry point of the farmland belongs to the set(20)1,2,…,8.The starting time of visiting the first farmland in each route must be within the time window.The chromosome shown in Table1 describes a potential solution for U1 and U2 to spray pesticides on seven farmlands in two time windows. In the first time window [9:00:00, 12:00:00], U1 first enters A5 from RD5 at 9:55:34 and then enters A2 from RD6 and finally returns to the starting point; U2 first enters A3 from RD7 at 9:04:16 and then enters A4 from RD8 and finally returns to the starting point. Similarly, in the second time window [14:00:00, 17:00:00], U1 enters A6 from RD3 at 15:31:48 and returns to the starting point after completing the tasks; U2 enters A7 from RD4 at 15:34:12 and returns to the starting point after completing the tasks. In this scenario, A1 is not sprayed with pesticides.Table 1
Chromosome encoding and examples.
Farmland
3
1
5
4
2
7
6
UAV
2
0
1
2
1
2
1
Entering point
7
1
5
8
6
4
3
Starting time
9.071
9.878
9.926
9.071
9.926
15.57
15.53


### 4.2. Fitness Function and Selection

In the algorithm, the objective function in formulation (10) is defined as the fitness function. The chromosome selection operation among population is carried out through the roulette wheel method. Therefore, the fitter the chromosome becomes, the higher probability it has to be selected to be included into the parental population.


### 4.3. Crossover

Through the crossover operator, the offspring can inherit the relatively good genes from the parent. Single-point crossover and multipoint crossover are some common approaches of crossover. Those crossover approaches are all integral operations of part gene in parent chromosomes. That is, for the selected part of parent chromosomes, the gene bits are either entirely replaced with new chromosome structures or are not replaced. According to the chromosome encoding, the same UAV must have the identical starting time in the chromosome. However, in these common approaches, the offspring chromosomes can hardly satisfy this constraint.A new crossover operator has been proposed. That is, the crossover site is randomly decided and the genes are replaced in the two parent chromosomes. The fourth row of the gene represents the starting time of the UAV visiting the first farmland via the same route. Therefore, in the crossed offspring chromosomes, it is also necessary to replace the fourth row of the other genes involved in the same route with the new time.The crossover example is illustrated in Figure5. For offspring A, the second column of parent B is copied to the fifth column of parent A, and since the starting time of U1 visiting the first farmland is adjusted to 8.574 in the first time window, the third and fourth columns of offspring A have also to be set as 8.574. Similarly, another offspring chromosome, B, can be obtained.Figure 5
Schematic of chromosome crossover.


### 4.4. Mutation

Mutation operator is done to prevent the GA from falling into the local optimum. In our study, the chromosome mutations include four ways, which are the mutation of the first row of farmland order and the single-point mutations of the second, third, and fourth rows of the chromosomes, that is, the mutation of the visiting UAV, entry point, and entry time. According to the mutation probability, these four kinds of mutation may not occur, or one or more than one kinds may occur.The mutation example is illustrated in Figure6; the second and third rows of chromosome A mutated. The second row and second column of chromosome A mutated from 0 to 2. This mutation represents the fact that U2 will visit A1, which would not be visited originally. The third row and third column mutated from 5 to 7. This mutation represents the fact that the entry point RD5 of U1 visiting farmland A5 was replaced by RD7. To ensure the consistency of the starting time of U2 visiting the first farmland in the first time window, on the basis of the above mutation, the second column and fourth row of chromosome B were updated to 9.071.Figure 6
Schematic of chromosome mutation.


## 4.1. Encoding

Chromosome encoding represents a selected solution to the problem. A feasible solution for the DTOP-VTW-VP can be formed by determining the entry point of the UAV visiting the farmland, the starting time, and the visiting order. Therefore, the chromosome corresponds to the serial number of the farmland, UAV and entry point of the farmland, and the starting time of the UAV visiting the first farmland in each route. Among them, the serial number of the farmland belongs to the set(18)1,2,…,NA,the UAV’s serial numbers belong to the set(19)0,1,…,NU,and the serial number of the entry point of the farmland belongs to the set(20)1,2,…,8.The starting time of visiting the first farmland in each route must be within the time window.The chromosome shown in Table1 describes a potential solution for U1 and U2 to spray pesticides on seven farmlands in two time windows. In the first time window [9:00:00, 12:00:00], U1 first enters A5 from RD5 at 9:55:34 and then enters A2 from RD6 and finally returns to the starting point; U2 first enters A3 from RD7 at 9:04:16 and then enters A4 from RD8 and finally returns to the starting point. Similarly, in the second time window [14:00:00, 17:00:00], U1 enters A6 from RD3 at 15:31:48 and returns to the starting point after completing the tasks; U2 enters A7 from RD4 at 15:34:12 and returns to the starting point after completing the tasks. In this scenario, A1 is not sprayed with pesticides.Table 1
Chromosome encoding and examples.
Farmland
3
1
5
4
2
7
6
UAV
2
0
1
2
1
2
1
Entering point
7
1
5
8
6
4
3
Starting time
9.071
9.878
9.926
9.071
9.926
15.57
15.53


## 4.2. Fitness Function and Selection

In the algorithm, the objective function in formulation (10) is defined as the fitness function. The chromosome selection operation among population is carried out through the roulette wheel method. Therefore, the fitter the chromosome becomes, the higher probability it has to be selected to be included into the parental population.


## 4.3. Crossover

Through the crossover operator, the offspring can inherit the relatively good genes from the parent. Single-point crossover and multipoint crossover are some common approaches of crossover. Those crossover approaches are all integral operations of part gene in parent chromosomes. That is, for the selected part of parent chromosomes, the gene bits are either entirely replaced with new chromosome structures or are not replaced. According to the chromosome encoding, the same UAV must have the identical starting time in the chromosome. However, in these common approaches, the offspring chromosomes can hardly satisfy this constraint.A new crossover operator has been proposed. That is, the crossover site is randomly decided and the genes are replaced in the two parent chromosomes. The fourth row of the gene represents the starting time of the UAV visiting the first farmland via the same route. Therefore, in the crossed offspring chromosomes, it is also necessary to replace the fourth row of the other genes involved in the same route with the new time.The crossover example is illustrated in Figure5. For offspring A, the second column of parent B is copied to the fifth column of parent A, and since the starting time of U1 visiting the first farmland is adjusted to 8.574 in the first time window, the third and fourth columns of offspring A have also to be set as 8.574. Similarly, another offspring chromosome, B, can be obtained.Figure 5
Schematic of chromosome crossover.


## 4.4. Mutation

Mutation operator is done to prevent the GA from falling into the local optimum. In our study, the chromosome mutations include four ways, which are the mutation of the first row of farmland order and the single-point mutations of the second, third, and fourth rows of the chromosomes, that is, the mutation of the visiting UAV, entry point, and entry time. According to the mutation probability, these four kinds of mutation may not occur, or one or more than one kinds may occur.The mutation example is illustrated in Figure6; the second and third rows of chromosome A mutated. The second row and second column of chromosome A mutated from 0 to 2. This mutation represents the fact that U2 will visit A1, which would not be visited originally. The third row and third column mutated from 5 to 7. This mutation represents the fact that the entry point RD5 of U1 visiting farmland A5 was replaced by RD7. To ensure the consistency of the starting time of U2 visiting the first farmland in the first time window, on the basis of the above mutation, the second column and fourth row of chromosome B were updated to 9.071.Figure 6
Schematic of chromosome mutation.


## 5. Experiment Analysis

### 5.1. Experimental Settings

The experiment of solving the DTOP-VTW-VP is performed on CPUs with 3.1 GHz processors and 4 GB of memory in the MATLAB Version: 8.1.0.604 (R2013a) environment. All of the results are the average results of the same experiment that was run ten times. The relevant parameters in the experiment are defined as follows.


#### 5.1.1. UAV Parameter Configuration

In the experiment, we used two UAVs,UAVa and UAVb, with different maximum flight time. The heading angle of taking-off (φ0) and heading angle of returning (φe) are all 0. The detailed UAV configurations are shown in Table 2.Table 2
UAVs’ parameters.
Type
A
0
\
A
N
A
+
1
V
R
U
R
D
E
U
A
V
a
(
0,0
)
4 m/s
3 m
5 m
2600 s
U
A
V
b
(
0,0
)
4 m/s
3 m
5 m
3600 s


#### 5.1.2. Farmland Parameter Configuration

The targets described in regular TOP and related TOP extended models are all point targets, and thereby the corresponding benchmark instances [4, 16] are also generated for the point targets. At present, there are no benchmark instances for the problem studied and reported in this paper. Therefore, we randomly generated four instances according to the number of farmlands, labeled Fa, Fb, Fc, and Fd. All of the farmlands in the instances are rectangles, as shown by the shaded areas in Figure 7.Figure 7
Distribution of farmlands to be sprayed with pesticides in four instances.


#### 5.1.3. Parameter Configuration for the Profit of Pesticide Spraying and Time Windows

We have chosen four pesticides with different potencies in this study. Table3 shows the temperature range required for the different pesticides to be effective and the spraying time windows generated according to the temperature curve (shown in Figure 8) on the day the pesticides were sprayed.Table 3
Parameters of spraying pesticides.
Type ofpesticide
Effective temperature range
Temperature curve in a day
The time window
Efficacy function
M
a
[30,35]
D
a
[08:30:00, 11:30:00]
P
i
1
(
t
)
=
-
0.1
t
2
+
2
t
-
9.05
.
M
b
[30,35]
D
b
[11:00:00, 13:00:00]
P
i
1
(
t
)
=
0.2
t
2
-
4.8
t
+
29.55
.
M
c
[20,30]
D
c
[07:17:42, 16:40:20]
P
i
1
(
t
)
=
-
0.01
t
2
+
0.24
t
-
0.44
.
M
d
[20,30]
D
d
[07:42:09, 10:53:18], [15:25:11, 18:36:20]
P
i
1
(
t
)
=
0.08
t
+
0.1, Pi2(t)=-0.094+2.45.Figure 8
Temperature curve corresponding to pesticide spraying date.


### 5.2. Experiment  1

When spraying pesticides by UAVs in real life, the UAVs are operated mainly by operators who assign spraying tasks manually. This experiment compares the proposed DTOP-VTW-VP and the method of solving it with manual allocation strategies. In this experiment, we used two UAVs of the typeUAVa to carry out pesticide spraying task Ma on the six farmlands in area Fa, the thirty farmlands in area Fc, and the fifty farmlands in area Fd under the environmentDa, respectively. The UAVs needed to return to A0 after completing the tasks. In this experiment, the crossover probability is 0.9, the mutation probability is 0.5, and the number of iterations is 100. The population size is 200 for Fa and 600 for Fc and Fd.Currently, there are two typical manual assignments. The first is to spray in the order of the serial number of the farmlands (FCFS) and the second is to divide the environmental areas based on the number of UAVs (AA) and route each UAV to spray the multiple farmlands in its assigned area in an orderly manner. According to the different approaches used to partition the area, this AA strategy can be further subdivided into horizontal partitioning (HAA) and vertical partitioning strategy (VAA).TakingFa as an example, when using the FCFS strategy, due to the constraint of the UAVs’ maximum flight time, U1 can only spray farmlands 1, 2, and 3 one after the other; U2 can only spray farmlands 4 and 5 by turns; and no UAV sprays pesticides for farmland 6. When using the HAA strategy, farmlands 1 and 6 are divided into two parts, namely, farmlands 1-U and 1-D and 6-U and 6-D. At this time, U1 can only spray farmlands 1-D, 2, and 3; U2 can only spray farmlands 1-U, 4, and 5; and no UAV sprays farmlands 6-U and 6-D, shown in Figure 9(a); when using the VAA strategy, farmland 4 is divided into two parts, namely, farmlands 4-L and 4-R. At this time, U1 can only spray farmlands 1, 2, and 3; U2 can only spray farmlands 4-L and 6; and there is no UAV to spray farmlands 4-R and 5, shown in Figure 9(b). Similarly, when using HAA or VAA strategy, the areas Fc and Fd can also have corresponding divisions, shown in Figures 9(c)–9(f).Figure 9
Strategies to divide two environments.
(a)
(b)
(c)
(d)
(e)
(f)Furthermore, on the basis of the HAA and VAA partitioning strategies, it is not necessary to use the simple sequential spraying method to spray pesticides after the partitioning. We used the proposed GA to solve the problem, and the results are recorded as HAA-GA and VAA-GA. The experimental results for the six strategies are listed in Table4.Table 4
Total profits of different strategies.
Strategy
FCFS
HAA
VAA
HAA-GA
VAA-GA
GA
Profit (Fa)
Best
11.375929
11.377640
12.321728
13.163538
13.262648
14.207891
Average
11.375927
11.377570
12.321727
13.163482
13.262647
14.207630
Worst
11.375924
11.376944
12.321725
13.163280
13.262644
14.207054
Profit (Fc)
Best
13.598946
16.114927
14.177219
19.798079
19.755321
20.841820
Average
13.598857
16.113556
14.176789
19.566585
19.485146
20.803396
Worst
13.598820
16.109182
14.173178
19.254607
19.233586
20.563810
Profit (Fd)
Best
15.240267
17.025706
15.542191
19.750809
19.575570
21.164493
Average
15.238925
17.023981
15.540840
19.452674
19.253614
21.141369
Worst
15.237859
17.021032
15.538872
19.095573
18.672814
20.933253In actual operations, the FCFS strategy is very simple and convenient but ignores the many factors that influence the efficacy of pesticide spraying, causing low spraying efficiency or even the need to respray pesticides on farmlands. When making a simple partition of areaFa according to the number of UAVs, the efficacy of pesticide spraying exhibits a certain degree of improvement from the FCFS strategy, although after the partitioning the FCFS strategy is still used for pesticide spraying. For example, the profit of VAA strategies is 8.31% higher than that of FCFS strategy. However, if we use the GA to solve for the assignment after partitioning, the spraying efficacy can be further improved. For example, the profit of HAA-GA strategy is 15.70% higher than that of HAA strategy. When we use the GA to solve the DTOP-VTW-VP, we can achieve the best results in the pesticide spraying process. The average profit of 14.2076302 obtained from the experiment has improved by 24.89%, 24.87%, and 15.30% compared to the FCFS, HAA, and VAA strategies, respectively. In the ten experiments, the deviation from the lowest profit of 14.207054 to the highest profit of 14.207891 is only 0.589‰. The stability of the solution, therefore, is reasonable. Similarly, for areas Fc and Fd with larger number of farmlands, the solutions of the GA are also better than other strategies.


### 5.3. Experiment  2

This experiment is to analyze the quality of the solution of the problem obtained by the GA. However, due to the new characteristics of DTOP-VTW-VP, there is no specific exact algorithm for solving it so far. In small-scale scenario, enumeration method is a suitable method to obtain optimal solution of this problem. So, we choose enumeration method to obtain the optimal solution first, and then the solution obtained by the GA at the same scale is compared to it. In both methods, the time was discretized to 0.001-hour slices.Firstly, we considered the case of two UAVs of typeUAVa spraying pesticides Mb on two farmlands of Fb area in the Db environment. The two UAVs returned to A0 after completing the tasks. Furthermore, we considered spraying six farmlands of Fa area under the same conditions. In the experiment, the crossover probability is 0.9, the mutation probability is 0.5, and the number of iterations is 100. The population size is 300 for Fa and 200 for Fb. As shown in Table 5, the results obtained by the GA are the same as the enumeration results.Table 5
Total profits of different algorithms.
Algorithm
Enumeration method
GA (best)
GA (average)
GA (worst)
F
a
12.87509416
12.87509416
12.87509416
12.87509416
F
b
3.68693186
3.68693186
3.68693186
3.68693186


### 5.4. Experiment  3

In this study, we further analyzed the solution result of the DTOP-VTW-VP in the GA with different crossover and mutation probabilities so as to find the best GA parameter settings. Firstly, we considered the case of two UAVs ofUAVb type spraying pesticide Mc on 30 farmlands in Fc area under the Dc environment. The two UAVs needed to return to A0 after completing the tasks. In this experiment, the population size is 600, the number of iterations is 100, and the different combinations of crossover and mutation probabilities are tested. The results of the experiment are shown in Table 6.Table 6
Profits by using the GA with different crossover probability and mutation probability to solve the problem inFc area.
Crossover probability
Mutation probability
Profit
Best
Average
Worst
0.6
0.1
18.746294
18.2830218
17.848443
0.2
19.396301
18.8087832
18.306828
0.3
19.096581
18.6825238
18.136924
0.4
19.546193
18.9225651
18.476077
0.5
19.854999
19.3839069
18.277796
0.7
0.1
18.985041
18.3877006
17.797626
0.2
19.057171
18.5054134
17.845470
0.3
19.289189
18.8459193
18.295809
0.4
19.744276
19.1485988
18.276355
0.5
20.005192
19.3001108
18.737504
0.8
0.1
19.653727
18.94321789
18.257300
0.2
19.206603
18.7216859
18.197193
0.3
19.495514
18.9371575
18.436387
0.4
19.594068
19.2097174
18.845762
0.5
19.896023
19.5798137
19.246180
0.9
0.1
19.034872
18.4822167
18.026126
0.2
19.216349
18.7607619
18.265439
0.3
19.834902
18.9186706
18.338060
0.4
19.834990
19.1950335
18.797545
0.5
20.206175
19.6581126
19.286954Furthermore, we considered the case of two UAVs of typeUAVb spraying pesticide Md on 50 farmlands in Fd area under environment Dd. The two UAVs needed to return to A0 after completing the tasks. In this experiment, the population size is 600, the number of iterations is 150, and different combinations of crossover and mutation probabilities are tested. The experimental results are shown in Table 7.Table 7
Profits by using the GA with different crossover probability and mutation probability to solve the problem inFd area.
Crossover probability
Mutation probability
Profit
Best
Average
Worst
0.6
0.1
32.146313
31.063109
30.158819
0.2
31.657627
31.1924874
30.237465
0.3
32.546799
31.3829089
30.616506
0.4
31.947100
31.4342386
30.811790
0.5
33.207930
31.8172000
31.169049
0.7
0.1
32.195687
31.0616860
30.468131
0.2
32.668609
31.2538480
30.485102
0.3
32.617468
31.5489710
31.085788
0.4
32.928398
31.7442040
31.113465
0.5
32.643838
31.7436435
30.533254
0.8
0.1
31.820305
31.6226008
31.063741
0.2
32.704727
31.2754686
30.503450
0.3
32.350841
31.8024295
31.381897
0.4
32.741668
31.9405945
31.547788
0.5
32.353212
32.0858842
31.575301
0.9
0.1
32.117330
31.4044922
30.561087
0.2
32.068228
31.4085898
30.666836
0.3
32.507261
31.7834013
31.050291
0.4
32.577798
31.8160464
31.287455
0.5
33.675813
32.7698301
32.135570As can be seen from the above results, in the case of different numbers of farmlands, different temperature curves, different time windows, and different pesticide efficacy profit functions, using the GA to solve the DTOP-VTW-VP is more stable in general. However, the demonstrated effects with different crossover and mutation probabilities are moderately different (Figure10).Figure 10
Profits under different crossover and mutation probability.
(a)
(b)When the crossover probability is fixed, the profit of the experiment increases in general with the increase of mutation probability. The profit reaches the maximum when the crossover probability is 0.9 and the mutation probability is 0.5. When the mutation probability is fixed, the profit of the experiment also shows an upward trend as a whole with the increase of crossover probability. Therefore, in the process of solving the DTOP-VTW-VP, the crossover probability can be set at 0.9 and the mutation probability as 0.5.


## 5.1. Experimental Settings

The experiment of solving the DTOP-VTW-VP is performed on CPUs with 3.1 GHz processors and 4 GB of memory in the MATLAB Version: 8.1.0.604 (R2013a) environment. All of the results are the average results of the same experiment that was run ten times. The relevant parameters in the experiment are defined as follows.


### 5.1.1. UAV Parameter Configuration

In the experiment, we used two UAVs,UAVa and UAVb, with different maximum flight time. The heading angle of taking-off (φ0) and heading angle of returning (φe) are all 0. The detailed UAV configurations are shown in Table 2.Table 2
UAVs’ parameters.
Type
A
0
\
A
N
A
+
1
V
R
U
R
D
E
U
A
V
a
(
0,0
)
4 m/s
3 m
5 m
2600 s
U
A
V
b
(
0,0
)
4 m/s
3 m
5 m
3600 s


### 5.1.2. Farmland Parameter Configuration

The targets described in regular TOP and related TOP extended models are all point targets, and thereby the corresponding benchmark instances [4, 16] are also generated for the point targets. At present, there are no benchmark instances for the problem studied and reported in this paper. Therefore, we randomly generated four instances according to the number of farmlands, labeled Fa, Fb, Fc, and Fd. All of the farmlands in the instances are rectangles, as shown by the shaded areas in Figure 7.Figure 7
Distribution of farmlands to be sprayed with pesticides in four instances.


### 5.1.3. Parameter Configuration for the Profit of Pesticide Spraying and Time Windows

We have chosen four pesticides with different potencies in this study. Table3 shows the temperature range required for the different pesticides to be effective and the spraying time windows generated according to the temperature curve (shown in Figure 8) on the day the pesticides were sprayed.Table 3
Parameters of spraying pesticides.
Type ofpesticide
Effective temperature range
Temperature curve in a day
The time window
Efficacy function
M
a
[30,35]
D
a
[08:30:00, 11:30:00]
P
i
1
(
t
)
=
-
0.1
t
2
+
2
t
-
9.05
.
M
b
[30,35]
D
b
[11:00:00, 13:00:00]
P
i
1
(
t
)
=
0.2
t
2
-
4.8
t
+
29.55
.
M
c
[20,30]
D
c
[07:17:42, 16:40:20]
P
i
1
(
t
)
=
-
0.01
t
2
+
0.24
t
-
0.44
.
M
d
[20,30]
D
d
[07:42:09, 10:53:18], [15:25:11, 18:36:20]
P
i
1
(
t
)
=
0.08
t
+
0.1, Pi2(t)=-0.094+2.45.Figure 8
Temperature curve corresponding to pesticide spraying date.


## 5.1.1. UAV Parameter Configuration

In the experiment, we used two UAVs,UAVa and UAVb, with different maximum flight time. The heading angle of taking-off (φ0) and heading angle of returning (φe) are all 0. The detailed UAV configurations are shown in Table 2.Table 2
UAVs’ parameters.
Type
A
0
\
A
N
A
+
1
V
R
U
R
D
E
U
A
V
a
(
0,0
)
4 m/s
3 m
5 m
2600 s
U
A
V
b
(
0,0
)
4 m/s
3 m
5 m
3600 s


## 5.1.2. Farmland Parameter Configuration

The targets described in regular TOP and related TOP extended models are all point targets, and thereby the corresponding benchmark instances [4, 16] are also generated for the point targets. At present, there are no benchmark instances for the problem studied and reported in this paper. Therefore, we randomly generated four instances according to the number of farmlands, labeled Fa, Fb, Fc, and Fd. All of the farmlands in the instances are rectangles, as shown by the shaded areas in Figure 7.Figure 7
Distribution of farmlands to be sprayed with pesticides in four instances.


## 5.1.3. Parameter Configuration for the Profit of Pesticide Spraying and Time Windows

We have chosen four pesticides with different potencies in this study. Table3 shows the temperature range required for the different pesticides to be effective and the spraying time windows generated according to the temperature curve (shown in Figure 8) on the day the pesticides were sprayed.Table 3
Parameters of spraying pesticides.
Type ofpesticide
Effective temperature range
Temperature curve in a day
The time window
Efficacy function
M
a
[30,35]
D
a
[08:30:00, 11:30:00]
P
i
1
(
t
)
=
-
0.1
t
2
+
2
t
-
9.05
.
M
b
[30,35]
D
b
[11:00:00, 13:00:00]
P
i
1
(
t
)
=
0.2
t
2
-
4.8
t
+
29.55
.
M
c
[20,30]
D
c
[07:17:42, 16:40:20]
P
i
1
(
t
)
=
-
0.01
t
2
+
0.24
t
-
0.44
.
M
d
[20,30]
D
d
[07:42:09, 10:53:18], [15:25:11, 18:36:20]
P
i
1
(
t
)
=
0.08
t
+
0.1, Pi2(t)=-0.094+2.45.Figure 8
Temperature curve corresponding to pesticide spraying date.


## 5.2. Experiment  1

When spraying pesticides by UAVs in real life, the UAVs are operated mainly by operators who assign spraying tasks manually. This experiment compares the proposed DTOP-VTW-VP and the method of solving it with manual allocation strategies. In this experiment, we used two UAVs of the typeUAVa to carry out pesticide spraying task Ma on the six farmlands in area Fa, the thirty farmlands in area Fc, and the fifty farmlands in area Fd under the environmentDa, respectively. The UAVs needed to return to A0 after completing the tasks. In this experiment, the crossover probability is 0.9, the mutation probability is 0.5, and the number of iterations is 100. The population size is 200 for Fa and 600 for Fc and Fd.Currently, there are two typical manual assignments. The first is to spray in the order of the serial number of the farmlands (FCFS) and the second is to divide the environmental areas based on the number of UAVs (AA) and route each UAV to spray the multiple farmlands in its assigned area in an orderly manner. According to the different approaches used to partition the area, this AA strategy can be further subdivided into horizontal partitioning (HAA) and vertical partitioning strategy (VAA).TakingFa as an example, when using the FCFS strategy, due to the constraint of the UAVs’ maximum flight time, U1 can only spray farmlands 1, 2, and 3 one after the other; U2 can only spray farmlands 4 and 5 by turns; and no UAV sprays pesticides for farmland 6. When using the HAA strategy, farmlands 1 and 6 are divided into two parts, namely, farmlands 1-U and 1-D and 6-U and 6-D. At this time, U1 can only spray farmlands 1-D, 2, and 3; U2 can only spray farmlands 1-U, 4, and 5; and no UAV sprays farmlands 6-U and 6-D, shown in Figure 9(a); when using the VAA strategy, farmland 4 is divided into two parts, namely, farmlands 4-L and 4-R. At this time, U1 can only spray farmlands 1, 2, and 3; U2 can only spray farmlands 4-L and 6; and there is no UAV to spray farmlands 4-R and 5, shown in Figure 9(b). Similarly, when using HAA or VAA strategy, the areas Fc and Fd can also have corresponding divisions, shown in Figures 9(c)–9(f).Figure 9
Strategies to divide two environments.
(a)
(b)
(c)
(d)
(e)
(f)Furthermore, on the basis of the HAA and VAA partitioning strategies, it is not necessary to use the simple sequential spraying method to spray pesticides after the partitioning. We used the proposed GA to solve the problem, and the results are recorded as HAA-GA and VAA-GA. The experimental results for the six strategies are listed in Table4.Table 4
Total profits of different strategies.
Strategy
FCFS
HAA
VAA
HAA-GA
VAA-GA
GA
Profit (Fa)
Best
11.375929
11.377640
12.321728
13.163538
13.262648
14.207891
Average
11.375927
11.377570
12.321727
13.163482
13.262647
14.207630
Worst
11.375924
11.376944
12.321725
13.163280
13.262644
14.207054
Profit (Fc)
Best
13.598946
16.114927
14.177219
19.798079
19.755321
20.841820
Average
13.598857
16.113556
14.176789
19.566585
19.485146
20.803396
Worst
13.598820
16.109182
14.173178
19.254607
19.233586
20.563810
Profit (Fd)
Best
15.240267
17.025706
15.542191
19.750809
19.575570
21.164493
Average
15.238925
17.023981
15.540840
19.452674
19.253614
21.141369
Worst
15.237859
17.021032
15.538872
19.095573
18.672814
20.933253In actual operations, the FCFS strategy is very simple and convenient but ignores the many factors that influence the efficacy of pesticide spraying, causing low spraying efficiency or even the need to respray pesticides on farmlands. When making a simple partition of areaFa according to the number of UAVs, the efficacy of pesticide spraying exhibits a certain degree of improvement from the FCFS strategy, although after the partitioning the FCFS strategy is still used for pesticide spraying. For example, the profit of VAA strategies is 8.31% higher than that of FCFS strategy. However, if we use the GA to solve for the assignment after partitioning, the spraying efficacy can be further improved. For example, the profit of HAA-GA strategy is 15.70% higher than that of HAA strategy. When we use the GA to solve the DTOP-VTW-VP, we can achieve the best results in the pesticide spraying process. The average profit of 14.2076302 obtained from the experiment has improved by 24.89%, 24.87%, and 15.30% compared to the FCFS, HAA, and VAA strategies, respectively. In the ten experiments, the deviation from the lowest profit of 14.207054 to the highest profit of 14.207891 is only 0.589‰. The stability of the solution, therefore, is reasonable. Similarly, for areas Fc and Fd with larger number of farmlands, the solutions of the GA are also better than other strategies.


## 5.3. Experiment  2

This experiment is to analyze the quality of the solution of the problem obtained by the GA. However, due to the new characteristics of DTOP-VTW-VP, there is no specific exact algorithm for solving it so far. In small-scale scenario, enumeration method is a suitable method to obtain optimal solution of this problem. So, we choose enumeration method to obtain the optimal solution first, and then the solution obtained by the GA at the same scale is compared to it. In both methods, the time was discretized to 0.001-hour slices.Firstly, we considered the case of two UAVs of typeUAVa spraying pesticides Mb on two farmlands of Fb area in the Db environment. The two UAVs returned to A0 after completing the tasks. Furthermore, we considered spraying six farmlands of Fa area under the same conditions. In the experiment, the crossover probability is 0.9, the mutation probability is 0.5, and the number of iterations is 100. The population size is 300 for Fa and 200 for Fb. As shown in Table 5, the results obtained by the GA are the same as the enumeration results.Table 5
Total profits of different algorithms.
Algorithm
Enumeration method
GA (best)
GA (average)
GA (worst)
F
a
12.87509416
12.87509416
12.87509416
12.87509416
F
b
3.68693186
3.68693186
3.68693186
3.68693186


## 5.4. Experiment  3

In this study, we further analyzed the solution result of the DTOP-VTW-VP in the GA with different crossover and mutation probabilities so as to find the best GA parameter settings. Firstly, we considered the case of two UAVs ofUAVb type spraying pesticide Mc on 30 farmlands in Fc area under the Dc environment. The two UAVs needed to return to A0 after completing the tasks. In this experiment, the population size is 600, the number of iterations is 100, and the different combinations of crossover and mutation probabilities are tested. The results of the experiment are shown in Table 6.Table 6
Profits by using the GA with different crossover probability and mutation probability to solve the problem inFc area.
Crossover probability
Mutation probability
Profit
Best
Average
Worst
0.6
0.1
18.746294
18.2830218
17.848443
0.2
19.396301
18.8087832
18.306828
0.3
19.096581
18.6825238
18.136924
0.4
19.546193
18.9225651
18.476077
0.5
19.854999
19.3839069
18.277796
0.7
0.1
18.985041
18.3877006
17.797626
0.2
19.057171
18.5054134
17.845470
0.3
19.289189
18.8459193
18.295809
0.4
19.744276
19.1485988
18.276355
0.5
20.005192
19.3001108
18.737504
0.8
0.1
19.653727
18.94321789
18.257300
0.2
19.206603
18.7216859
18.197193
0.3
19.495514
18.9371575
18.436387
0.4
19.594068
19.2097174
18.845762
0.5
19.896023
19.5798137
19.246180
0.9
0.1
19.034872
18.4822167
18.026126
0.2
19.216349
18.7607619
18.265439
0.3
19.834902
18.9186706
18.338060
0.4
19.834990
19.1950335
18.797545
0.5
20.206175
19.6581126
19.286954Furthermore, we considered the case of two UAVs of typeUAVb spraying pesticide Md on 50 farmlands in Fd area under environment Dd. The two UAVs needed to return to A0 after completing the tasks. In this experiment, the population size is 600, the number of iterations is 150, and different combinations of crossover and mutation probabilities are tested. The experimental results are shown in Table 7.Table 7
Profits by using the GA with different crossover probability and mutation probability to solve the problem inFd area.
Crossover probability
Mutation probability
Profit
Best
Average
Worst
0.6
0.1
32.146313
31.063109
30.158819
0.2
31.657627
31.1924874
30.237465
0.3
32.546799
31.3829089
30.616506
0.4
31.947100
31.4342386
30.811790
0.5
33.207930
31.8172000
31.169049
0.7
0.1
32.195687
31.0616860
30.468131
0.2
32.668609
31.2538480
30.485102
0.3
32.617468
31.5489710
31.085788
0.4
32.928398
31.7442040
31.113465
0.5
32.643838
31.7436435
30.533254
0.8
0.1
31.820305
31.6226008
31.063741
0.2
32.704727
31.2754686
30.503450
0.3
32.350841
31.8024295
31.381897
0.4
32.741668
31.9405945
31.547788
0.5
32.353212
32.0858842
31.575301
0.9
0.1
32.117330
31.4044922
30.561087
0.2
32.068228
31.4085898
30.666836
0.3
32.507261
31.7834013
31.050291
0.4
32.577798
31.8160464
31.287455
0.5
33.675813
32.7698301
32.135570As can be seen from the above results, in the case of different numbers of farmlands, different temperature curves, different time windows, and different pesticide efficacy profit functions, using the GA to solve the DTOP-VTW-VP is more stable in general. However, the demonstrated effects with different crossover and mutation probabilities are moderately different (Figure10).Figure 10
Profits under different crossover and mutation probability.
(a)
(b)When the crossover probability is fixed, the profit of the experiment increases in general with the increase of mutation probability. The profit reaches the maximum when the crossover probability is 0.9 and the mutation probability is 0.5. When the mutation probability is fixed, the profit of the experiment also shows an upward trend as a whole with the increase of crossover probability. Therefore, in the process of solving the DTOP-VTW-VP, the crossover probability can be set at 0.9 and the mutation probability as 0.5.


## 6. Conclusion

The process of allocating pesticide spraying tasks by multiple UAVs is closely related to the UAVs’ flight trajectory planning. In the face of the constraints of the time factor, pesticide effect, and UAVs’ own kinematic factors during pesticide spraying, the DTOP-VTW-VP model proposed in this paper was able to produce a satisfactory allocation scenario for pesticide spraying and provide the flight route for each UAV. The model extends the distance between two points in the regular TOP to the Dubins path distance and dynamically determines time windows of pesticide spraying according to the temperature conditions at the time the UAVs perform the tasks. Based on these factors, maximizing the profit of pesticide spraying was set as the optimization target of the model, thus avoiding the problem that in the practical application process the pesticide spraying result is not satisfied after the pesticide spraying task is completed. However, the DTOP-VTW-VP is also an extension problem of TOP, and we used the GA to solve it. We gave the methods of the GA encoding, crossover, and mutation to obtain the satisfactory solution. During the experiment, we not only validated the advantages of this model and the solving method over the manual operations but also verified the consistency of the results of the GA and the enumeration method in small-scale scenarios. Meanwhile, in the scenario of pesticide spraying task assignment for large-scale farmlands, we used the parameter sensitivity analysis method to further analyze the performance of solving the DTOP-VTW-VP by using the GA and provided the optimal algorithm parameter configuration. In future research work, we plan to extend the rectangular farmland in this problem to any irregularly shaped farmland, propose an optimization model, and solve the problem by optimizing the flight trajectory inside the farmlands.



---

*Source: 7139157-2017-11-12.xml*