1
STP: An Aerial Spray Treatment Planning System
W.D. Potter; University of Georgia; Athens, GA
Ramyaa; University of Georgia; Athens, GA
J. Li; University of Georgia; Athens, GA
J. Ghent; USDA Forest Service; Asheville, NC
D. Twardus; USDA Forest Service; Morgantown, WV
H. Thistle; USDA Forest Service; Missoula, MT
Keywords: Spray treatment planning, Spray scheduling, Aerial Spray Treatment
2002 SECon-SEC122 page 1
1
ABSTRACT
The Spray Treatment Planner is an intelligent decision support system for productivity and efficiency evaluation in an aerial spray treatment project. It can be used as a tool to plan the schedule for spraying pesticides aerially. STP schedules the spraying operation of selected blocks from selected airports using single or multiple aircraft(s). The scheduling is done to maximize the spray efficiency and spray productivity while minimizing the total time and distance flown. It uses heuristics to obtain a near optimal solution. Aerial spray applicators can use STP to estimate total time required for a treatment operation. Forest managers can use STP to determine an efficient and productive treatment plan.
1.INTRODUCTION
The gypsy moth (Lymantria dispar L.) has been one of North American’s most devastating exotic forest pests since it was accidentally introduced into North Americain the late 1860s. It can cause loss of valuable oak species, degraded aesthetics, loss of wildlife habitat and detrimental effects on watersheds (Potter 2000). A principle tool for the management of gypsy moth infestations is the application of pesticides by aircraft. Since planning of aerial spray activity heavily relies on the knowledge and ability of a human scheduler, it is important to develop decision aids to support the planning of aerial spray treatment. GypsES (Gypsy Moth Expert System), which was developed by the USDA Forest Service, is a computerized decision support system for use by natural resource managers involved in federal, state and local pest management programs. GypsES uses a geographical information system (GIS) framework for creation and analysis of complex map sets and on-screen digitizing with topographic map backdrops or aerial photographs. Due to its ease of use for on screen digitizing of treatment blocks and its importing and exporting of flight data for a variety of aircraft GPS tracking and guidance programs, its primary use has been in aerial treatment projects (Ghent 1999). In 1999, the Canadian Forest Servicephonology model, BioSIM was added to GypsES to incorporate forest defoliation (Ghent 1999). Through the use of GypsES’ GIS functions and the recently added phonology model BioSIM; some important aspects of aerial treatment planning are addressed. Because there is no effective way of evaluating the production needs of an aerial spray treatment project, the application of GypsES is limited. Currently, several million dollars are spent annually on aerial spray treatment application programs throughout the US (Ghent 1999). Determining production needs for the treatment contract is mainly based on guesswork or historic information from other projects. These estimates can often lead to overestimating contract needs, which can increase treatment cost by contracting for larger than needed aircraft or more aircraft than needed. Under-estimating contract needs often leads to treatment at less than optimal timing and results in less effective control (Ghent 1999). As available treatment dollars become limited, more precise estimates of contracting needs can assist land managers in reducing contract costs. Therefore, it is important to develop decision aids that help forest managers with aerial spray treatment planning. Since treatment areas are frequently remote, large, and inaccessible by ground transportation, a successful aerial spray application requires careful preparation and planning, as well as comparing different spray application strategies (Curbishley 1993). All these demands reinforce the need to develop a decision support system in this domain.
Two quantitative measures of effectiveness of such strategies are spray productivity and efficiency. Spray productivity is represented by the ratio of the area sprayed to the total aerial spray operation time. Spray efficiency is represented by the ratio of the time spent actually applying the spray on the target area to the total aerial spray operation time. These measures were first quantified in the "Baltin-Amsden Formula" (Amsden 1959) that describes a method for estimating the cost of an aerial spray operation. In contrast to previous cost estimation methods this formula emphasizes that the cost of spraying should be based on field or spray path lengths rather than on the magnitude of the area to be sprayed. Banaugh (1984) modified this formula to account for irregularly shaped and topographically varied spray areas. In addition, he presented a systematic and orderly calculation procedure for predicting the two measures. In 1988, Curbishhley and Teske developed a PC program called CASPR (Computer Assisted Spray Productivity Routing) to implement the procedure for evaluating an individual spray block. This system was used to evaluate productivity and efficiency of a single sprayed block. Due to the fact that CASPR can only evaluate a single treatment block, it is not convenient for users to plan an aerial application project with multiple blocks serviced by a single or multiple airports. There is a need to develop software to effectively evaluate the productivity and efficiency of aerial spray treatment projects on different scales. This is the primary motivation for developing our Spray Treatment Planner (STP), an extension to the CASPR system.
Determining a spray project’s production needs varies with the size of the treatment project, the size and number of blocks, the development rates of the target species over large geographic areas, and the location of heliports or airports in relation to the treatment blocks. This requires that users must supply block and airport information to do the evaluation. CASPR uses a general map to set these parameters manually, which makes it an inefficient decision support system.
STP aims to assist managers in evaluating the productivity and efficiency of spray treatment projects that have different scales with respect to the number of blocks and airports. In STP, we use a GIS to supply the treatment area parameters. The first scale has a single block serviced by a single airport. The second has multiple blocks serviced by a single airport. The third has multiple blocks serviced by multiple airports. Because of the limitation of aircraft fuel and pesticide tank capacity, an aircraft may require multiple cycles (trips) to spray a treatment area. Different schemes of scheduling spraying will result in different flight path length and total flying time. How to schedule the cycles is critical in order to evaluate the productivity and efficiency of the project. We use different heuristic procedures to solve this problem.
In STP, we use a series of heuristic rules for the single block serviced by a single airport scenario. A heuristic called CVRPS (Capacitated Vehicle Routing Problem for Multiple Blocks Serviced by A Single Airport) was established for this problem (the single airport scenario is a special case). Another procedure called CVRPM (Capacitated Vehicle Routing Problem for Multiple Blocks Serviced by Multiple Airports) based on CVRPS is used to deal with multiple blocks serviced by multiple airports. Also, a calculation model for evaluating production need was implemented in STP.
2.THE PREFERRED FUNCTIONALITIES IN STP :
1)The system will allow users to evaluate productivity for various types of aircraft for a specific project.
2)It will also calculate the production rates needed to accomplish a specific project, for all or individual treatment blocks based on the scheduling procedures developed in STP.
3)This system will be able to provide the project manager with realistic estimates of various aircraft productivity, total program productivity needs and improve efficacy in treatment block selection.
4)By applying STP, the estimates of contract needs will be able to reduce the problems associated with insufficient or too many aircraft. More importantly, improved grouping of blocks ready for treatment should increase effectiveness of control programs and reduce the need for re-treatment.
3.OVERVIEW OF STP
The system integrates three separate computer models to arrive at the estimates of productivity and efficiency for spray treatment projects. A GIS operation model is used to determine block boundaries and the locations of airports in relationship to the established loading areas. The scheduler model of how to spray the blocks is used to determine the total treatment distances, ferry distances and travel distance. In order to predict time and cost elements of an aerial spray operation, specific data supplied from the users are required. These include: application rate, tank capacity, flying speeds, hourly costs, insecticide cost, turning times, and the number and lengths of spray paths flown. Then these data and the two former models’ outputs will be fed into the evaluation model of productivity and efficiency to get the final results. These results are output.
Figure 1. The evaluation model flowchart
Figure 1 shows the flowchart of the STP evaluation model for productivity and efficiency of spray treatment. Recall that spray productivity is represented by the ratio of the area sprayed to the total time of aerial spray operation, and spray efficiency is represented by the ratio of the time spent actually applying the spray on the target area to the total operation time of aerial spray treatment. The total operation time is the sum of the flying time and time on the ground. The flying time is the sum of the ferrying time, spraying time, travel time among blocks, turning time and touchup time. The ground time is the sum of the loading time, equipment adjustment time and aircraft repair time. In STP, the ground time only consists of the loading time.
In order to calculate these measures, users will have to supply data about spray characteristics and aircraft. The spray characteristics include the pesticide application rate and swath width. The aircraft’s data includes ferry speed, spray speed, travel speed, loading time/cycle, turning time, auxiliary ferry distance, number of auxiliary turns, touchup constants, spraying cost rate, ferry cost rate, turning cost rate, touchup cost rate, loading cost rate and travel cost rate. Users enter all these parameters using the GUI tool in STP.
The GIS module will supply data about the block and airports. These geographical data are used to schedule the block spraying by the CVRPS and CVRPM. Then, they will supply the area of the block, the total ferry distance, the total travel distance, the total number of turns and total spray distance. These measures along with spray characteristics and aircraft data are fed into the “Baltin-Amsden” Formula for calculating the productivity and efficiency.
4.HEURISTICS FOR SCHEDULING SPRAY TREATMENT
The scheduling model for spraying blocks is one of three main models in STP. It is used with the GIS operational model and evaluation model to evaluate the production performance of the spray treatment project. The objective of this model is to minimize total flying distance by the aircraft so that we can get optimized productivity and efficiency. Since the area of blocks determines the total spray distance, the only way to minimize the total distance is to minimize the flying distance (ferry distance and travel distance). In STP, we develop a heuristic procedure called CVRPS to optimize the total flying distance for multiple blocks serviced by a single airport. We also use this procedure to develop another procedure called CVRPM for multiple blocks serviced by multiple airports. In the case of a single block serviced by a single airport, we set up a series of rules to spray the block. We also implement a small module called the “Flight Advisor” to let users investigate the rules to be used by the heuristics.
We established a set of rules for how to spray a single block serviced by a single airport. The rules are from experienced schedulers. These rules are then used in CVRPS (Capacitated Vehicle Routing Problem for Multiple Blocks Serviced by a Single Airport) and CVRPM (Capacitated Vehicle Routing Problem for Multiple Blocks Serviced by Multiple Airports).
The rules to be applied depend on the shape of the block. If the block is a rectangle, the aircraft will spray along its longest side. If the block is a polygon, we will identify two cases: (1) if the polygon can be divided and approximated as rectangles, then divide it and fly the small rectangles along their long side direction respectively. (2) If not, spray the polygon along the direction of its longest side. In this way, we can guarantee the aircraft will make the least number of turns during the treatment. This is very important since it will also reduce the risk due to dangerous sharp turns.
The capacitated vehicle routing problem (CVRP) in STP can by defined as follows: Let G=(V, E) be a connected graph, where V={V1…Vn} is the block set and V1 denotes the vertex at which the airport is located; E={(Vi, Vj)} is the flight lines set. Let Lij be the length of the flight lines of (Vi, Vj) and Qi0 be the load associated with Vi. In this problem, the load is the amount of pesticide the last cycle needs to spray the block. There is a fleet of homogeneous aircraft with pesticide tank capacity Q based at the airport to be available. The CVRP in STP consists of determining aircraft spray routes starting and ending at the airport such that:
(1) The load associated with any given block at the last cycle is sprayed by exactly one aircraft.
(2) The sum of all loads in the last cycle of blocks sprayed by the aircraft does not exceed Q.
(3) A linear combination of the number of aircraft and of the total distance traveled by these aircraft is minimized.
The CVRP and related problems have been studied extensively (Laporte and Nobert 1987; Golden and Assad 1988; Basnet 1997). Basically there are two types of algorithms that can be used to solve the CVRP: exact and heuristic. Exact algorithms are ones that, in the absence of round-off errors, will yield an exact solution in a finite number of steps. Because of the computer time involved, the exact algorithm approach is limited to problems involving relatively few locations. This is generally true of all exact algorithms that solve the CVRP. Heuristic algorithms, on the other hand, are quite often faster and capable of obtaining optimal or near-optimal solutions for much larger problems in a reasonable amount of computer time (Golden 1987). Note that there is no guarantee that a heuristic approach will give an optimal result. In addition, the CVRP is a generalization of the famous Traveling Salesperson Problem. To our knowledge there are several heuristic algorithms for the CVRP (Labbe 1991; Rennie 1995; Basnet 1997). Labbe (1991) developed upper bounds and lower bounds for the problem, which were then included in a branch and bound search for the exact solution. Rennie (1995) used the upper bound to construct a heuristic for the CVRP. Basnet (1997) gave two other heuristic algorithms for the problem. His algorithm is a remarkably simple modification of the heuristic first introduced by Clarke and Wright (1964). To test the computational performance of the heuristics, he randomly generated a number of numerical instances of the problem, and applied the heuristics to them. He used the two developed heuristics in the test, and the solutions were obtained. He also solved the same problem using the upper bound and the exact algorithm of Labbe et al (1991) and the sequential greedy heuristic of Rennie (1995). His research showed that all the heuristics came relatively close to the exact solution. Therefore, heuristics in this domain are feasible and powerful. These heuristics have practical advantages, but are domain dependent. In our work, we develop a heuristic called CVRPS for the problem of spray treatment planning (similar to one of Basnet’s heuristics) in the case of a group of blocks serviced by a single airport. We follow that with a heuristic called CVRPM for the case of a group of blocks serviced by multiple airports.
The main idea of the heuristic for CVRPS in STP is that we begin to construct as many runs as there are blocks for every aircraft. Each block is alone on a unique run. We then progressively combine runs, subject to the fuel and pesticide tank capacity. This procession is in a myopic and greedy fashion, which is based on the maximum savings (in total distance traveled) by run combination. The approach is illustrated in the following figures. There are three different cases. We begin the combination process by selecting the block that is the nearest neighbor of the airport and then search from its adjacent blocks to see which one will be combined into this run based on the capacity of the aircraft. We first check the pesticide tank capacity and then check the fuel tank capacity. If both capacities are not exceeded, these blocks will be combined into one run. In case there are several candidates to be selected, the first choice is the closest one; the second choice is the combined capacity closest to the aircraft capacity. In this way, this combination process is continued until there are no more feasible run combinations to be found. The combinations of the initial runs will result in the groups of blocks to be sprayed together by a single aircraft. Then the order of the blocks within the group will be determined based on the minimum total flight distance. This heuristic can reduce total ferry distance and travel distance. Thus, the heuristic can find an optimal or near optimal solution for this problem. There are three cases for the run combination: