Abstract: In this study, three heuristics were developed to assess the quality of forest plans that can be developed and the time required to develop them. The three heuristics include threshold accepting, 1-opt tabu search and a combined heuristic which consisted of threshold accepting, 1-opt tabu search and 2-opt tabu search. The combined heuristic was developed to capitalize on the unique search properties of both threshold accepting and tabu search. Present hypothesis was that each of the three heuristics would produce forest plans of approximately equal solution quality. The three heuristics are assessed using forest plans developed from nine hypothetical landownerships containing various ownership patterns and age class distributions. The combined heuristic found the highest quality forest plans for most problems with older and normal age class distributions. In problems with younger age class distributions, the combined heuristic produced slightly inferior solutions as compared to threshold accepting. The variation in forest plan quality was lowest when using the combined heuristic or threshold accepting, thus these two processes are of value for large-scale forest plan development efforts.
INTRODUCTION
The use and evaluation of spatial harvest scheduling techniques has increased in recent years due to the need to develop forest plans that accommodate multiple and often conflicting management objectives. In addition, there has been a recognizable increased need for sustainable forest harvesting practices that not only recognize economics, but also recognize the preservation and maintenance of bio-diversity, aesthetic values and public recreation areas (Bettinger and Chung, 2004). Further, federal and state regulations and polices have resulted in increasingly complex objectives for the management of forests in the North America (Bettinger and Sessions, 2003). And, in many instances, compliance with regulatory restrictions, voluntary forest certification programs and organizational goals and policies related to landscape conditions are now as important as economic objectives in the development of forest plans. Long-term forest planning allows people to understand whether sustainable forestry is actually being practiced. Therefore, locating efficient algorithms to assist with the development of forest plans has become a very practical and import issue.
An optimization process seeks to maximize (or minimize) certain economical and ecological objectives subject to various constraints, while assigning forest management actions to timber stands over some lengthy period of time and across a landscape. There are two general classes of forest planning algorithms, one is based on traditional mathematical programming techniques and the other is based on heuristics. The first class includes exact algorithms, such as linear programming, mixed integer programming, integer programming (Bevers and Hof, 1999; Hof et al., 1994; Hof and Joyce, 1992) and dynamic programming (Snyder and ReVelle, 1997; Hoganson and Borges, 1998). The appeal of exact algorithms is that the optimal solution to a problem (if found) will be reported. However, as the size of a planning problem increases, solving it may become computationally impractical (Lockwood and Moore, 1993), particularly if integer variables are used. Although computer hardware and software technology continues to advance, the use of exact algorithms remains limited in application to small- and medium-sized forest planning problems. The second class include heuristics such as Monte Carlo simulation (Nelson and Brodie, 1990), simulated annealing (Dahlin and Sallnas, 1993; Lockwood and Moore, 1993; Murray and Church, 1995), threshold accepting (Bettinger et al., 2003), tabu search (Bettinger et al., 1997; Batten et al., 2005) and genetic algorithms (Glover et al., 1995; Falcão and Borges, 2001). Although heuristics cannot guarantee that they can locate the optimum solution to a problem, they can usually find good solutions to complex planning problems, making them attractive for large-scale spatial forest planning problems.
Bettinger et al. (2002) compared eight heuristics on three small, but increasing difficult wildlife planning problems. They found that threshold accepting, simulated annealing and tabu search with 2-opt moves worked the best in most cases. Heinonen and Pukkala (2004) performed a comparison of 1-opt and 2-opt compartment neighborhoods in the development of forest plans for medium-sized forest planning problems and confirmed the notion that 2-opt neighborhoods were important for tabu search. One question that lingers is whether differences in forest plan quality arising from the use of different search methods becomes negligible when relatively large forests are considered, given the large number of choices available and the greater amount of flexibility inherent in these problems. In this research, we will compare how three heuristics perform in the development of nine forest plans. One of the heuristics combined the unique search properties of the other two. Each plan considers a different type of land ownership situation. The goal is to determine which heuristic works best for the management problem under consideration. Knowledge gained from the previous research will inform the selection of test heuristics. For example, it has been shown that threshold accepting is a relatively fast heuristic and it can transition an inferior solution to a problem to a very good solution in a fraction of the time that tabu search requires. Tabu search, on the other hand, uses deterministic choices to refine the quality of solutions. Present hypothesis is that a combination of these, utilizing their unique search behavior, can produce higher quality forest plans for larger landscapes then when each is used alone. Thus the contribution of this study is in the testing of methods for the development of large, relatively complex, yet realistic forest plans.
MATERIALS AND METHODS
This study was conducted in 2006. The scheduling problems we use in this research involve three types of ownership patterns of parcels that are typical in the Southeastern United States (clumped, random and dispersed parcels). Three forest age class distributions are then assigned to each timber stand randomly; these represent a young forest age class structure, a normal forest and an older forest age class structure. The size of each hypothetical forest is approximately 28,300 ha. Forest plans were then developed for each of these 9 hypothetical forests. We describe next the formulation of the forest planning problem and the heuristic techniques that were tested. The planning problem described below was solved first using linear programming, although the spatial harvest placement constraints were ignored. Thus the results derived from linear programming are assumed to come from a relaxed problem. The heuristics were employed to solve the full spatial planning problem. Each were developed using the C-sharp programming language.
The forest planning problem uses a time horizon that is 20 years long; each planning period is one year long. This tactical planning problem seeks to maximize the net present value of timber harvested from the forest and the problem formulation has been used in other research endeavors (Zhu et al., 2007; Zhu and Bettinger, 2008). The objective function and constraints are formulated as:
(1) |
Subject to
(2) |
(3) |
(4) |
where, XT1it = 1, otherwise XT2it = 0
(5) |
(6) |
AGic - AGit1 >
5 ∀ i |
(7) |
AGic - AGit2 >
5 ∀ i |
(8) |
(9) |
(10) |
(11) |
(12) |
| Ai | = | Area of timber stand i |
| AGic | = | Clearcut age for timber stand i |
| AGit1 | = | Age when first thinning occurs for timber stand i |
| AGit2 | = | Age when second thinning occurs for timber stand i |
| Cit | = | Logging cost for timber stand i harvested in time period t |
| i, z | = | Timber stands |
| P | = | Stumpage price |
| MCA | = | maximum clearcut area |
| N | = | The total number of timber stands |
| Ni | = | Set of all timber stands adjacent to timber stand i |
| Si | = | The set of all timber stands adjacent to those timber stands adjacent to timber stand i |
| t, u | = | Planning periods |
| T | = | The total number of planning periods in the planning horizon |
| Vit | = | The available clearcut timber harvest volume from timber stand i during time period t |
| Vi20 | = | The unscheduled timber harvest volume from timber stand i at the end of period 20, whether or not a harvest had been applied during the period represented by the plan |
| VT1it | = | The available first thinning timber harvest volume from timber stand i during time period t |
| VT2it | = | The available second thinning timber harvest volume from timber stand i during time period t |
| Xit | = | A binary variable, which = 1 if timber stand i is clearcut harvested in time period t and 0 otherwise |
| XT1it | = | A binary variable, which = 1 if timber stand i is first-thinned in time period t and 0 otherwise |
| XT2it | = | A binary variable, which = 1 if timber stand i is second-thinned in time period t and 0 otherwise |
The objective function of this problem assesses the difference between revenue generation and the cost of management activities (prices versus logging costs) for each activity (clearcut, first thinning and second thinning) applied to each timber stand over the time horizon. Decisions are integer in nature (yes or no), therefore when an activity is applied to a stand it is applied to the entire stand. Revenues and costs are discounted from the mid-point of each planning period. The value of the ending inventory (the timber that remains standing at the end of the time horizon) is included to fully value the forest management enterprise. Equation 2 indicates that each stand can only be clearcut harvested one time during the time horizon and Eq. 3 indicates that each stand can only be first thinned once during the time horizon. Equation 4 indicates that each stand can only be second thinned once during the time horizon, given that it was previously first-thinned. Equation 5 ensures that clearcuts do not exceed the maximum clearcut size assumed and also assumes that the green-up period is 2 years. This set of constraints represent a slight modification of the original ARM model presented by Murray (1999). Here, Si is the subset of clearcut harvested stands containing all stands adjacent to neighbors of stand i and stands adjacent to the neighbors of the neighbors, etc. As Murray (1999) suggested, this constraint involves a recursive function that senses a sprawling cluster of stands clearcut harvested within the green-up period and that the cluster depends on the contiguity of stands and their direct or indirect relationship to stand i. As a result, the relationship is not easily described by a linear equation. Equation 6 represents an ending inventory constraint, where the standing volume at the end of the time horizon must be at least 90% of the standing volume at the beginning of the time horizon. Equations 7 and 8 ensure that the time period between a thinning activity and a clearcutting activity is at least six years. Equations 9 and 10 are wood-flow constraints and maintain the volume scheduled for harvest during each time period to a proportion of the standing volume at the end of the time horizon. Equations 11 and 12 are also wood-flow constraints and limit deviations in scheduled harvest volumes from one period to the next, as a form of stability. This problem formation can be considered a Model I (Johnson and Scheurman, 1977), integer programming problem.
We assumed an interest rate of 6% and derived timber stumpage prices by Mart-South (2004). The costs of reasonable forest establishment practices for the Southeastern United States were derived by Smidt et al. (2005). The maximum clearcut size we assumed was 97 ha (240 acres) and the green-up period associated with the adjacency constraints was assumed to be 2 years.
The heuristic methods we tested included threshold accepting and tabu search. Threshold accepting, initially described by Dueck and Scheuer (1990), has been successfully applied to forest planning problems (Bettinger et al., 2002; Bettinger et al., 2003) and in general, can produce solutions that are as good, if not better than, those produced by simulated annealing. The parameters required for the threshold accepting heuristic include the initial threshold, number of total iterations, the rate of change in the threshold and the number of unsuccessful iterations allowed per threshold. Threshold accepting is a stochastic local search process. In our implementation, a timber stand and a management prescription are selected at random and temporarily inserted into the current forest plan. Then the clearcut adjacency constraints are assessed. If the addition to the forest plan results in a constraint violation, then the addition is rejected. If the addition to the forest plan results in no constraint violations and improves the quality of the plan, then it is formally accepted. If the addition to the forest plan does not result in a constraint violation, but leads to a solution that is of lower quality than the best solution stored in memory, then is formally accepted only if the quality of the resulting solution is within the threshold (best solution-current threshold value). The threshold accepting search process begins with a relatively large threshold value, which decreases as the number of iterations progresses, until it is so small that the search process terminates. This search process allows large deviations in solution quality in the initial stages of the search and small deviations later in the search. Through numerous trials, we arrived at the following parameters: allow 500 iterations per threshold value, use an initial threshold level of $1,000,000 (US) and reduce the threshold value by $200 each time it is changed. If more than 500 unsuccessful attempts to change a plan pass, the threshold changes as well.
Tabu search is a deterministic search process that was initially described by Glover (1989). Tabu search has been applied extensively to forest planning problems (e.g., Bettinger et al., 1997; Bettinger et al., 2002). In its basic form, tabu search uses 1-opt moves, which change the status of an individual decision variable. In present case, this would involve changing the timing of a harvest applied to a timber stand. Once a choice has been assigned to a stand, the stand is considered tabu for a pre-defined number of iterations of the search process. During this time, no other changes can be made to the stand unless the changes result in a forest plan that is better (in solution quality) than any other forest plan developed during the search. This is frequently considered the aspiration criteria.
Within tabu search, a neighborhood of potential changes is assessed and the best choice of harvests is selected from this set. The neighborhood in present case involves assessing all of the potential changes to a forest plan, although region-limited approaches have shown value (Bettinger et al., 2007). As with threshold accepting, the constraints are assessed after selecting a choice from the neighborhood. If the choice results in a violation of one or more constraints, it is disregarded and another choice is made. Based on numerous trials, we determined that the best parameters for tabu search were to allow the process to operate for 20,000 iterations and to use a tabu state of 500 iterations. While we considered intensification and diversification techniques, such as the use of a frequency list or strategic oscillation, we decided here to utilize this standard version of tabu search as a standard basis for comparison. The number of iterations was chosen to approximate the number of decisions considered by the threshold accepting algorithm.
The search process within tabu search can be intensified using a 2-opt neighborhood, where the harvest timing of two different timber stands are switched. A 2-opt process has been shown as a valuable way to further refine the quality of a forest plan (Bettinger et al., 1997; Bettinger et al., 2002). Due to the computational burden of this process, we used a region-limited approach and only assessed a neighborhood of 100 timber stands at one time. This neighborhood moved 50 stands forward each time the 2-opt process was employed. Tabu search with 2-opt moves cannot be used by itself, since no introduction of new opportunities is possible (only the swapping of opportunities). As a result, this 2-opt process is employed in conjunction with the standard 1-opt tabu search process. The tabu state for 2-opt moves, however, is 400 iterations of the search process, a parameter we determined again through numerous trials. This combined form of tabu search represents a portion of the third heuristic we studied.
We developed a combined heuristic that utilized the strengths of threshold accepting and tabu search. In this combined heuristic, threshold accepting is enacted first, using similar parameters as described earlier, in order to quickly move the development of a forest plan to a very good area of the solution space. The parameters were adjusted slightly so that when combined with the tabu search process, the total amount of potential decisions made approximates those considered when using threshold accepting and tabu search heuristics in isolation. Within the combined heuristic, after threshold accepting is employed, a 1-opt tabu process is performed using the result (best solution) from threshold accepting. A 2-opt tabu search process is subsequently employed using result (best solution) of the 1-opt tabu search process.
To compare the results that are generated, each of the three heuristics generated 30 solutions (forest plans) for each of the nine hypothetical planning problems, resulting in 27 sets of 30 solutions each. The forest plans were developed using a Pentium III computer equipped with a 2.7 GHz processor. Each of the forest plans can be considered an independent sample from a larger population because each began with a randomly-defined forest plan, thereby inducing the development of statistically independent samples (Golden and Alt, 1979; Los and Lardinois, 1982). A series of statistics are then developed to evaluate the average, maximum, minimum, variation in each set of 30 solutions.
RESULTS AND DISCUSSION
To begin, while each of the three heuristics attempts to locate the optimal solution to the planning problem, the overall best solution generated by each can vary by as much as 8 to 12% (Table 1). The largest percentage variation is found when developing the forest plans for the younger forest, the least variation is found when developing plans for the normal forest. The combined heuristic located the best solutions for the problems involving normal and old forest age classes. In the 2 of 9 instances where it did not locate the best solution (when considering the younger forest), the best solution generated by the combined heuristic was within about 0.2% of the best solution generated by the threshold accepting heuristic. While the combined heuristic consisted of threshold accepting and tabu search processes, one could argue that these differences are minor, since randomly generated initial plans were used. Further, one could argue that the addition of tabu search provided little assistance in these cases. In general, the combined heuristic and threshold accepting produced similar solutions, although in a few cases, the combined heuristic produced forest plans that were $200,000 (US) or greater in net present value. The time required to generate a solution using the combined heuristic, however, was also about twice as long as when using the other heuristics, mainly due to the inclusion of 2-opt tabu search procedure.
The threshold accepting heuristic performed reasonably well on its own and much better than the 1-opt tabu search heuristic, when applied to these forest planning problems. Tabu search using only 1-opt moves was out-performed by both threshold accepting and the combined heuristic. Again, this is a standard 1-opt tabu search procedure and others (Richards and Gunn, 2000; Bettinger et al., 1999) have suggested ways in which the tabu search process can be enhanced to facilitate the development of higher quality forest plans. However, we used the standard tabu search process as a point of reference for current and for future work in this area and serves increasingly as a benchmark against which other heuristics are tested.
The worst-case performance for the threshold accepting and combined heuristics (Table 2) was very similar.
| Table 1: | Quality of the best solution generated by three heuristics and associated time required to generate the solution |
| Table 2: | Worst-case performance of three heuristics, when applied to nine hypothetical forest planning problems |
| Table 3: | Variation in performance of three heuristics, when applied to nine hypothetical forest planning problems |
However, the worst-case performance of 1-opt tabu search was much lower and variation in forest plan quality was much higher when using 1-opt tabu search (Table 3). This indicates that the other two heuristics were also significantly better, on average, at producing high-quality forest plans than when using 1-opt tabu search. However, the variation in forest plan quality, when using threshold accepting or the combined heuristic was generally higher when the young age class distribution was considered. And, when the normal forest was considered, variation among forest plan quality was lowest when using threshold accepting. In the case of the younger forest, the difficulty in meeting the wood-flow constraints during the first few time periods of the plans likely contributed to the difficulty in locating consistently high-quality solutions.
Another manner in which to evaluate the performance of the heuristics in generating forest plans is to compare the results to the plan that was developed using linear programming. One can use the reduction in solution quality (percentage reduction) as an estimate of the cost of implementing the adjacency and green-up policy, since these spatial constraints were not included in the linear programming problem formulation. We found that the percentage reductions when using threshold accepting or the combined heuristic were 0.3 to 4.5% below the relaxed linear programming situation. This is consistent with the results found by others who sought to determine the cost of spatial restrictions in forestry operations in the southern US (Boston and Bettinger, 2001).
One might also argue that the improvement in solutions generated by combined heuristic is simply because it required a much longer length of time to generate a single forest plan. However, because the parameters for threshold accepting and tabu search were carefully selected, the comparison among results seems valid. Roughly speaking, the amount of decisions made by threshold accepting and the combined heuristic were about the same. Therefore, even if we increased the number of iterations allowed by threshold accepting and 1-opt tabu search, we hypothesized that the results would not change significantly. The reason why the combined heuristic performs better in most cases is that it uses 2-opt tabu search process to switch the schedule for two units simultaneously.
The 2-opt tabu search intensification process works well when applied to small and medium forest planning problems (Bettinger et al., 2002; Heinonen and Pukkala, 2004) and with this study, shows promise for larger forest management problems. What remains to be determined is whether the sequence of scheduling techniques (threshold accepting, 1-opt tabu search, 2-opt tabu search) needs adjustment to further enhance the performance of a combined heuristic. Our method for developing the combined heuristic consisted of acknowledging that threshold accepting could move the search quickly to local optima of high quality and assuming that tabu search could be used to refine the search, especially 2-opt tabu search. Further assessments of the appropriate sequence (or collection) of heuristic processes, based on the behavior of the search process, seems to be a worthwhile area of exploration. In addition, while we concentrated here on the assessment of a combined heuristic that used threshold accepting and tabu search processes, other types of heuristics could provide processes to help diversify (avoid becoming stuck in local optima) or intensify the search (carefully search a good area of the solution space). Threshold accepting was selected based on previous research (Bettinger et al., 2002). The 1-opt tabu search process was also selected based on advantageous characteristics (deterministic moves made, regardless of decrease in solution value). And the 2-opt tabu search has been suggested as a worth-while addition to tabu search algorithms even though the processing time requirements may be high. Other heuristics, such as genetic algorithms, have been included in combined forest planning heuristics (Boston and Bettinger, 2001). However, the effect of the crossover routine on the maintenance of adjacency is generally so high that a number of constraint violations must be attended to (usually by unscheduled harvests) to maintain feasibility at each iteration of the search.
CONCLUSIONS
The significance of this research to the scientific community is the finding that when examining realistic forest management behavior in North America and in attempting to optimize this behavior at the forest-level, either a fast stochastic heuristic (threshold accepting) or one that uses an intensive deterministic search process (tabu search with 2-opt moves) are appropriate. Although this has been suggested in previous research, we have shown here that this assertion is robust across a broad range of landowner sizes, spatial configurations and forest age classes. Previous study was not as complete and examined a smaller range of potential landowner conditions. While heuristics such as threshold accepting can provide very good solutions to a variety of forest planning problems and can produce them relatively quickly, the addition of tabu search procedures (to form a combined heuristic) may allow one to produce higher quality solutions, on average, to many types of forest planning problems. The additional time required (0.5 to 1 h) to generate a solution that has a $50,000-200,000 increase in net present value seems moot, given that the plan will be implemented over a series of years. However, additional parameterization (for both tabu search and threshold accepting) and additional programming logic are the main disadvantages of the approach. This work has shown that the cost of typical adjacency constraints (2 year green-up and 97 ha maximum clear cut size) is consistent with current knowledge, 1-5% reduction in NPV from relaxed case. Recent advancements in spatial harvest scheduling (Bettinger and Zhu, 2006) may be useful in developing even better solutions. However, these new techniques have generally only been tested on limited sets of small problems and may provide difficult to integrate with other search processes.