Research on the scheduling model of flying defense team based on simulated annealing algorithm

Li Yibai，Cao Guangqiao

(Nanjing Institute of Agricultural Mechanization，Ministry of Agriculture and Rural Affairs，Nanjing 210014，China)

Abstract: Plant protection UAVs(unmanned aerial vehicles)are usually operated in the form of flying defense teams.At present，the scheduling organization of the flying defense teams is relatively extensive，resulting in the low efficiency of the flying defense teams.Reasonable scheduling of UAVs can improve the operational efficiency of the flying defense teams.By taking the rice smut prevention and control scenarios as the research object，according to the operation specifications of“single-spray triple-prevention”against rice smut，referring to the current situation of the order modes of flying defense operation，an order management and plant protection UAVs scheduling model is proposed in this study，to ensure the operation quality and operation efficiency of plant protection UAVs.The model has two parts:(1)Order management，which is an order sorting method that comprehensively considers order work area，time window，and order urgency;(2)Scheduling model，which is a UAV scheduling model based on simulated annealing algorithm.Taking 16 plots in Nanjing area in China and rice smut control tasks of 4 flying defense teams for case study，the simulated annealing algorithm and the greedy algorithm were used to make a comparative study on the time window lengths of 3-6 days.Research results showed that，when the operation time window length is 3-5 days，the longer the time window，the shorter the scheduling distance and waiting time，the longer the total operation time，and the higher the total revenue.When the time window length is 6 days，the total operation time and operation income will not change.This research can provide a scientific basis for the deployment and decision-making analysis of the UAVs flying defense teams，and provide a reference for the development of the intelligent scheduling system for agricultural machinery.

Keywords: plant protection unmanned aerial vehicles;scheduling model;task assignment;simulated annealing algorithm

0 Introduction

Rice is an important food crop，therefore，ensuring the yield and quality of rice is an important part of food security[1-2].The requirements for the prevention and control of major rice pests and diseases in the“2022 Technical Plan for the Prevention and Control of Major Rice Pests and Diseases”issued by the Ministry of Agriculture and Rural Affairs of China pointed out that the prevention and control strategies are:prevention first，comprehensive pest control with unified prevention and high efficiency，to achieve green and safe prevention[3].Among them，the common diseases such as rice false smut，ear rot，leaf sheath disease need to be sprayed from the end of booting to the heading stage，demonstrating high timeefficiency[4].In recent years，with the maturity of plant protection UAVs plying defense and spraying technology，the use of plant protection UAVs for pesticide spraying to control crop pests and diseases has become a trend in plant protection operations[5].Reasonable planning of UAVs scheduling strategies and comprehensive consideration of timeliness and scheduling cost in UAVs operation can achieve good operation results and low scheduling cost[6].

The existing studies on the scheduling method of UAVs mainly focus on the path planning in the field.At present，the research on the field transfer path of plant protection UAVs generally directly uses the models of the logistics management[7-8]and ordinary agricultural machinery scheduling[9-10].The optimization objective is multi-objective fusion and optimization，such as the shortest general time and the minimum scheduling cost[11-12].The model constraints are generally set as follows:soft time window，and the operation time window is set to be relatively long[13].In terms of operating costs and benefits:the larger the field and the longer the operating time for ordinary machinery operation，the higher the operating benefits，and the higher infield operation costs than the field transfer costs[14-15].However，the following three conditions in the plant protection operation scenarios have not been considered by the research on the direct and indirect agricultural machinery scheduling models:(1)The length of the time window.With the characteristics of strong timeliness for plant protection，the operations need to be completed within a specific period during growth of crops.Therefore，the operation time window of the plant protection UAVs scheduling model needs to be set in a short time to achieve better operation effect，and the length of the time window has a greater impact on the UAVs scheduling.(2)Operation costs.UAVsapplied plant protection has the characteristics of high in-field operation efficiency and low field transfer efficiency.The operation scheduling costs of UAVs mainly lie in the field transfer cost and the operation waiting cost.(3)Operation priority.The operation cycle of plant protection is short，and the outbreak of farmland diseases and insect pests occurs suddenly and spread quickly.Therefore，according to the farmland conditions，applying different weights to different orders according to the actual situation can better ensure the operation quality of the plots.

The optimal solution methods of the model can be divided into two categories:exact solution and heuristic algorithm[16].The exact solution algorithm is prone to problems of slow computational efficiency and huge calculation amount when faced with a large problem scale[17-18].The heuristic algorithm can find a better solution in a short time，which is more suitable for actual situation than the exact algorithm[19-20].Since the plant protection UAV has the characteristics of high operation efficiency and strong maneuverability，the simulated annealing method was taken as the model solution method in this model[21-22].Simulated annealing algorithm is a common heuristic algorithm[23-24]，compared with genetic algorithm and particle swarm algorithm，it has the advantages of faster convergence speed and is suitable for solving small-scale optimization problems.

In summary，by taking the prevention and control of rice smut as the research scenario and referring to the optimization objectives and constraints of the agricultural machinery scheduling model，and taking the actual parameters of UAVs in plant protection operation and scheduling as the constraints of the scheduling model，comprehensively considering the quality and efficiency of operations，a scheduling model for plant protection UAVs suitable for rice smut control was established，and the simulated annealing method was used as the model solution method.During the standard operation period of pesticide application，the influence of different time window lengths on the operating income of the flying defense team is discussed，which provides a reference for the development of intelligent dispatching system for agricultural machinery.

1 Task planning of multi-machine collaborative operation based on rice smut prevention and control scenarios

The requirements for the prevention and control of rice smut in the “2022 Technical Plan for the Prevention and Control of Major Rice Pests and Diseases”pointed out that the prevention and control of rice smut should be based on prevention.For the control of rice smut，the plants should be uniformly applied 7-10 days before the rupturing stage of rice.Too early or too late application will affect the control effect on the disease.In the organizational form of the actual operation，farmers who have the demand of such operation send plant protection orders to the local cooperatives，and the order mainly includes the location，size and operation time window of the operation field.The cooperatives organize flying defense teams to carry out operations according to the order demand.The flying defense teams are from different locations，and a flying defense team can have multiple plant protection UAVs.If there is a lack of efficient plant protection UAVs scheduling and multimachine collaborative operation decision-making methods in the area，the total operation time of plant protection UAVs may be very long，and the transfer or waiting cost will be increased，or even the operation cannot be carried out within the time window，thus the operation efficiency and effect cannot be guaranteed.Therefore，the operation scenario of rice smut fly prevention is a problem of scheduling of multimachine system operation.

In this study，the collaborative mission planning of multi-machine plant protection UAV is divided into two parts:order management and task allocation management.In order management，ordering rules are established considering the urgency of the order，the operation time window and the operation revenue.In terms of task allocation，comprehensively consider the current state of the UAVs and the transfer cost，and reasonably schedule the UAVs to perform tasks to minimize the overall path transfer cost and operation time.

2 Order management

Rice smut prevention and control operations have the characteristics of strong timeliness.The optimization objectives and constraints in this paper are also closely related to the operation sequence of each order.By analyzing various factors affecting the operation efficiency，a better optimization objective function value can be obtained，which is more suitable for rice smut control.

(1)Emergency of prevention and treatment.Since the incidence of rice false smut is related to weather factors such as humidity，temperature，and wind direction，which are uncertain to some extent，thus its outbreak has certain suddenness and contingency.Therefore，the order sender can choose the emergency level according to the actual situation of crops and weather:urgent operation and nonurgent operation，the priority of emergency orders is higher than the non-economic level.

(2)Field area.Plant diseases and insect pests are diffusible，and priority operations are given to orders with larger contiguous areas，which can achieve good control effects and give full play to the advantages of UAVs in efficient operation.Therefore，the larger the work area in farmer’s order，the higher the order priority.

(3)Time window.Only by carrying out the“unified prevention and control”operation in the specified crop growth state and time can ensure the quality of the operation.The closer the time window start time is to the wall，the shorter the window time，and the higher the order priority.Taking the above factors into consideration，the order sorting rule is determined as shown in equation(1).

Where，Urepresents the urgency of the order，0 means non-urgent，1 represents urgency，andw1represents its weight.Arepresents the normalized farmland area，andw2represents its weight.wsrepresents the start time of normalized time window，andw3represents the weight of start time of time window，andwlrepresents the normalized time window length，and its weight isw4.The calculation equation ofwlis as in equation(2)，andwerepresents the end time of the time window.Equation(3)indicates that the sum of the weights of each influencing factor is 1.In this paper，the weights ofw1、w2、w3、w4are all the same，which is 0.25.Use equation(1)to calculate the score of each order，and arrange the orders in reverse order according to the score to obtain the sequence of operation of all orders.

3 Plant protection UAV scheduling model

The establishment and solution of the scheduling model of the plant protection UAVs is to solve the task sequence planning problem on the basis of order sorting.Task sequence planning mainly solves the problem of assigning sub-tasks to UAVs in different locations.When the number of tasks is more than the number of available plant protection UAVs，there will be cases that multiple tasks are assigned to one UAV.Therefore，it is necessary to find a reasonable allocation model，while ensuring that the UAVs complete the operation within the operation time window，reduces the transfer cost of the UAVs，improves the operation efficiency，and maximize the overall benefit.

Then the hero betook himself to the King, who was obliged now, whether he liked it or not, to keep his promise, and hand him over his daughter and half his kingdom

3.1 Model optimization goals

(1)Shortest working time

Where，mrepresents the total number of tasks of the UAVs;terepresents the end time of each task;tsrepresents the start time of each task;trei，jrepresents the start time of the UAVjduring the taski;trei-1，jindicates the end time of UAVjin the task ofi-1;xrepresents subtasks number of UAVj.

(2)Operation time window penalty

Equation(5)represents the minimization of the gap between the start time of the operation and the end time of the time window，andWE irepresents the end time of the time window of fieldi.

(3)The maximum benefit of the operation:the benefit can be expressed as equation(6).

Among them，cirepresents the operating income;ccrepresents the operating cost(including mechanical loss，battery energy and pesticide consumption cost)，andA irepresents the operating area of each field，m1represents the labor cost of operation time，(i-1，j)，(i，j)represent the path cost of the UAVjtransferring from fieldi-1 to fieldi，andm2is the unit price of waiting cost.

3.2 Constraints of plant protection UAV scheduling

The scheduling of plant protection UAVs needs to meet the following constraints.

Equation(7)indicates that all farmland needs to be operated，xis the flag bit of whether to work.Equation(8)indicates that the end time of farmland operation should be earlier than the end time of the farmland time window.

4 Simulated annealing algorithm

The simulated annealing algorithm is derived from the principle of solid annealing and is a probabilitybased search algorithm.The simulated annealing algorithm starts from a certain high initial temperature，with the continuous decrease of the temperature parameter，combined with the probabilistic abrupt jump characteristic，it randomly finds the global optimal solution of the objective function in the solution space，that is，the local optimal solution can jump out probabilistically，and tends to a global optimum.In this paper，the simulated annealing algorithm is used to optimize the scheduling problem of plant protection UAVs swarms.The specific iterative process of the algorithm is as follows.

(1)Specify the initial temperatureTand the maximum number of cyclesM.The initial temperature in this paper is set to 100，and the lower limit temperature is 0，the attenuation coefficient isβ=0.85，and the maximum number of cycles is set to 1 000 times.The task is randomly assigned to each UAV，and the function value of the initial solution is calculated.

(2)Randomly generate a group of allocation strategiesw，and calculate the cost function scoref(w)under this strategy.

(3)Randomly generate a group of disturbance allocation strategiesw′，and calculate the cost function scoref(w′)under this strategy.

(4)CalculationΔE=f(w′)-f(w).

(5)IfΔE＜0，accept the perturbation strategyw′，otherwise calculate the probability of accepting the perturbation strategy with equation(9)，whereTis the current temperature.Namely，randomly generate a numberδbetween 0 and 1，ifδ＜p.Then accept the perturbation strategyw=w′，otherwise accept the original strategyw=w′.Number of cyclesi=i+1.

(6)If strategywmeets the optimization requirements，ori＞M，the loop will be skipped.Otherwise，T=T-t，tis the temperature drop value under each cycle，and go to step(3).

5 Example experiment and analysis discussion

5.1 Example description

This paper takes the experimental scenario of“single-spray triple-prevention”operation on rice in Qixia District，Nanjing City，Jiangsu Province as an example.In this operation scenario，4 flying defense teams operate on 16 farmlands in Qixia，Jiangning and other areas need to be dispatched to provide plant protection and integrated defense for rice in 4 surrounding grassroots villages.The daily operation time limit of the flying defense team is 12 h.Farmers upload the flying defense orders to the information platform of the provincial plant protection UAVs dispatching center，and each flying defense team can obtain the farmer’s order information from this platform.The order information includes:the size，location，operation time window and operation urgency of the operation field.The operation urgency information is simulated data.The farmland area in the order is about 150-350 hm2.The information of the flying defense teams and the operating locations is shown in Table 1 and Table 2，respectively.

Table 1 Location information of the flying defense teams

Table 2 Plant protection operation order form

According to the actual survey results，it is determined that the operation cost is 10 yuan/hm2，the UAV transshipment cost is 2 yuan/km，the labor cost of each UAV operation is 8 yuan/h，and the waiting time of each UAV is 2 yuan/km.The cost is 40 yuan/h.The field operation efficiency of the UAV is 5 hm2/h，and the transfer speed is 30 km/h.

5.2 Results analysis

The operating environment of this paper is Intel Core i7 processor，Windows 10 operating system，and the simulation software is Matlab 2014b.The experimental case of this paper takes the time window of 3-6 days as examples.The results of example running are shown in Table 3.

Table 3 Operation benefits of different time window lengths

It can be seen from the scheduling results that the simulated annealing method can meet the time window operation requirements compared with the greedy algorithm.The simulated annealing method has better operation benefits than the greedy algorithm，and the operation benefits mainly come from less scheduling distance and less waiting time.From the results，when the time window length is 4，5，and 6 days，the simulated annealing algorithm can meet the time window requirements.However，the simulated annealing algorithm cannot achieve the operation time window schedule when the time window length is 3 days.The simulated annealing algorithm has better operation returns in various time window models，mainly because the total waiting time and scheduling distance of both methods are better than those of the greedy algorithm.It can be seen from the results that the scheduling distance of the 3 days time window greedy algorithm is 38.01 km longer than that of the simulated annealing algorithm，the waiting time of the plant protection UAV is reduced by 84.54 h，and the operation income is increased by 1 944.3 yuan.Compared with the greedy algorithm，the simulated annealing algorithm with a 4 days time window has 18.88 km more scheduling distance，17.22 h less waiting time，and 4 546.47 yuan more operation revenue.Compared with the greedy algorithm，the simulated annealing algorithm with a 5 days time window has 17.22 km more scheduling distance，52.27 h less waiting time，and 5 050.59 yuan more job revenue.Compared with the greedy algorithm，the simulated annealing algorithm with a 6 days time window has 17.22 km more scheduling distance，52.27 h less total waiting time，and 5 050.59 yuan more operation revenue.

From the point of view of the time window，when the length of the time window is 3-5 days，with the increase of the length of the time window，the benefits of the Simulated annealing gradually increase，and the total operation time also increases continuously.

The shorter the time window，the more subtasks.When the time window length is 3 days，the number of subtasks is 23，when the time window length is 4 days，the number of subtasks is 18，and when the time window length is 5 days，the number of subtasks is 16，when the time window length is 6 days，the number of subtasks is also 16.When the time window length is increased from 3 to 5 days，the number of sub-tasks decreases continuously.When the number of subtasks is huge，the UA V needs to be frequently scheduled，and the ground scheduling and waiting costs would also increase.Therefore，the operation benefits at this stage also increase with the length of the time window.When the time window interval is increased from 5 to 6 days，the number of subtasks is still 16.The UAV swarm scheduling Gantt under different time window lengths is shown in Figure 1，and the convergence diagram of the simulated annealing algorithm is shown in Figure 2.

The Gantt charts of 3-5 days job time window scheduling based on simulated annealing algorithm are shown in Figure 1.As can be seen from the figure，when the time window length is 3-5 days，all UAVs have almost no time interval between each sub-task，which ensures the operation and transfer efficiency of UAVs.In terms of horizontal comparison，for time window of 3-5 days，the shorter the time window，the more compact the task arrangement of each UAV.The shorter the time window，the more likely each plot is divided into multiple sub-tasks，which are completed by multiple plant protection UAVs.

Figure 1 Scheduling Gantt charts based on simulated annealing algorithm

Figure 2 Convergence graph based on simulated annealing algorithm

On the contrary，the longer the time window，the more likely that each plot will be directly completed by the same UAV，which reduces the cost of transfer and waiting，and the total revenue of the operation is also increased.In terms of the benefits of plant protection operations，when the time window interval is 3-5 days，the operation time of UAVs continues to increase，and the operating benefits also continue to increase.Among them，when the time window length is 4 days，the increase is the largest compared with the time window length of 3 days.When the time window length is 5 days，the increase is slightly higher than that when the time window length is 4 days.When the working time window length is 6 days，the operating income is no longer increasing compared with the operation time window length of 5 days.

According to the above conclusions，the flight defense team can choose an appropriate scheduling plan according to its own actual situation:when there are no other flight defense tasks or the time interval between subsequent flight defense tasks is long，the operation plan with a time window of 5 days can be selected to ensure a single maximize revenue from order jobs.When the flight defense team has received the follow-up order and the operation is urgent，the time window of 4 days can be selected，so that the operation income is most cost-effective.

6 Conclusions and shortcomings

According to the operation specification of“singlespray triple-prevention”against rice smut and referring to the current situation of the existing flying defense operation order models，the order management and order allocation methods are proposed.

(1)An order sequencing method that comprehensively considers the order operation area，time window，and order urgency.

(2)UAVs scheduling model based on Simulated annealing algorithm.The results show that the Simulated annealing algorithm has more advantages in operation benefits，scheduling distance and waiting time.

The operating income，scheduling distance and waiting time consumption of the flying defense team were analyzed under the condition of time window of 3-6 days.The results show that when the time window length is 3-5 days，the longer the time window length，the shorter the scheduling distance and waiting time，the longer the total operation time，and the higher the income.When the time window length is above 5 days，the scheduling distance，waiting time，total operation time and revenue will not change.

The research in this paper is mainly about the scheduling of plant protection UAVs from a static perspective，and does not consider the increase in subsequent orders.At the same time，the model assumes that each UAV has the same authority to obtain plant protection orders.In actual situations，plant protection UAV orders may be directly issued to each cooperative，and each cooperative has limited arrangements for its own UAV operations.When the standards for operation capacity are not met，the UAVs are dispatched from other locations to perform operations，which may involve the links of order delivery and price game.Therefore，for model establishment in the future，it is necessary to focus on taking the cooperative as a unit，and consider the increase of subsequent orders，so as to maximize the operating benefits of each cooperative.