An Indirect Search Algorithm for Solving the Spatial Harvest-Scheduling Problem by Kevin Andrew Crowe A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Forestry in The Faculty of Graduate Studies Department of Forest Resources Management We accept this thesis, as conforming/(o the required standard The University of British Columbia August 2000 © Kevin Andrew Crowe, 2000 In presenting this in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study . I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or his or her representatives . It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Forest Resources Management Faculty of Forestry The University of British Columbia Vancouver, Canada Date: Abstract The objective of this research was to develop, evaluate, and understand a new heuristic algorithm for solving the spatial harvest-scheduling problem. The new algorithm, indirect search, is a combination of a greedy heuristic and a neighborhood search. It was developed with the intention of quickly computing near-optimal solutions to large harvest-scheduling problems where harvest activities are treated as 0-1 variables. For this study, the algorithm solved two harvest-scheduling problems constrained by even-flow and two-period adjacency constraints: 1) a set of small tactical problems comprising 625 harvest-units scheduled over ten one-year periods; and 2) a strategic planning problem comprising 3,857 harvest-units scheduled over twenty ten-year periods. Excellent solutions to the tactical problem took 2 minutes and 42 seconds to compute and were superior to those calculated by implementations of a tabu search and a simulated annealing algorithm. The solution to the strategic problem was computed in 63 minutes and scheduled 86.9% of a linear programming model's total volume. The nature of the efficiency of this algorithm is discussed in some detail and it is also shown that the general strategy of indirect search can be applied to other combinatorial optimization problems. The indirect search algorithm performed well on the models tested thus far. These results warrant further research on: 1) applying indirect search to harvest-scheduling problems with more complex forms of spatial constraints; and 2) evaluating the efficiency of the indirect search strategy in its application to other combinatorial optimization problems. Key words: forest planning, harvest-scheduling, heuristic techniques Table of Contents Acknowledgements .V. VI Abstract ii Table of Contents iii List of Tables iv List of Figures v Chapter 1: Introduction 1 Chapter 2: Literature Review 10 Chapter 3: Methods and Procedures 34 Chapter 4: Results 50 Chapter 5: Discussion 55 Chapter 5: Conclusions 63 Literature Cited 66 i i i List of Tables 2.1 MCIP results by O'Hara et al. (1989) 15 2.2 Hi l l Climbing results for 45 harvest-units by Murray and Church (1993) 18 2.3 Hi l l Climbing results for 431 harvest-units by Murray and Church (1993) 19 2.4 Hi l l Climbing results by Liu (1995) 19 2.5 Simulated annealing results by Dahlin and Salnas (1993) 22 2.6 Tabu search results by Brumelle et al. (1998) 24 2.7 Tabu search results by Boston and Bettinger (1999) 25 2.8 Genetic algorithm's results by Liu (1995) 28 2.9 Simulated annealing versus greedy search results by Liu (1995) 32 3.1 Calculations for ending inventory for L U 26 48 4.1 Results for tactical problems 50 4.2 Results for strategic problems 52 5.1 Greedy tours for 4-city travelling salesman problem 61 iv Lis t of Figures 2.1 Example of cross-over operation 26 3.1 Flowchart of greedy search algorithm for harvest-scheduling 35 3.2 Viewer used to verify adjacency constraints in solutions 39 3.3 Age class distribution of L U 26 43 3.4 Map of L U 26 43 4.1 Progress of indirect search over 100,000 iterations 51 4.2 Timber flow for strategic problem 53 5.1 Travelling salesman problem with 4 cities 60 5.2 Indirect search applied to 4-city travelling salesman problem 63 v Acknowledgements I would like to thank my advisor, Dr. John Nelson, for generously providing me with the opportunity to pursue this subject. Without his patient, sound guidance, this great experience would not have been possible. I would also like to thank my committee members, Dr. Shelby Brumelle and Dr. Emina Krcmar-Nozic, for their review of my work. It resulted in subtle and valuable fine-tuning of my thoughts on this subject. I would also like to thank Tim Shannon for the spirited encouragement and useful direction he gave me in solving my programming problems. Finally, I would like to thank Dr. Kevin Boston for graciously sharing his data sets with me and carefully clarifying certain problem parameters. Chapter 1: Introduction 1.1 Introduction to Problem 1.1.1 Context of Problem Forest management has expanded to include the conservation of multiple forest values, and one consequence of this has been the addition of adjacency constraints to harvest-scheduling. Adjacency constraints ensure that a harvest-unit not be cut until units adjacent to it have reached a level of maturity known as the green-up age. This age depends on climate, soil, and species, and typically ranges from 2 to 20 years. The formulation of adjacency constraints for two harvesting periods is expressed in equation 1. njXit + E xit + E Xi(t-i) ^ " / for all U ; [1] i eN, i e M where Nj - set of harvest units adjacent to unit i rii = number of units adjacent to unit i Xjt = 1 if harvest-unit i harvested in period t, 0 otherwise Adjacency constraints complicate the harvest-scheduling problem because each harvest-unit must be treated as a discrete decision variable. Hence, the harvest-scheduling problem has become a combinatorial optimization problem. The inherent difficulty of 1 such problems is that their solution spaces greatly increase with the addition of more decision-variables. As a result, timber supply analysts have been discouraged from thoroughly exploring alternative harvest scenarios to large problems because the time required to compute solutions is impracticably long. There is, therefore, a need to improve the efficiency of algorithms used to solve the combinatorial harvest-scheduling problem. 1.1.2 Recent Research Research into the spatial harvest-scheduling problem has been in three areas, each with distinct shortcomings. First, there were attempts to increase the spatial resolution of solutions produced by linear programming (LP) through innovative formulations (Thompson et al. 1973; Mealey et al. 1982; Meneghin et al. 1988; and Weintraub et al. 1988). Such formulations have thus far failed to meet the demands of decision-makers who desire a clear allocation of multiple values. LP's greatest challenge in solving the harvest-scheduling problem has been that its decision-variables are continuous. Second, there has been work done on integer programming models with the goal of formulating adjacency constraints such that solutions may be calculated more quickly (Meneghin et al. 1988; Torres-Rojo and Brodie 1990; Jones etal. 1991; Yoshimoto and Brodie 1994, Murray and Church 1996). Improvements have been realized in this regard, but not enough to render this method practical for solving large problems. Finally, there has been research into heuristic methods such as and Monte Carlo integer programming (O'Hara 1989; Nelson et al. 1990), simulated annealing (Lockwood and Moore 1992; Murray and Church 1993), and tabu search (Murray and Church 1993; Brumelle et al. 2 1998; Boston and Bettinger 1999). This has been a promising area of research because heuristic algorithms have been able to calculate good solutions to large problems far more quickly than integer programming models. Its shortcoming has been a high trade-off between computing-time invested in a solution and the quality of the solution. 1.2 Problem Statement 1.2.1 Specific Problem Addressed The problem addressed in this thesis is that of designing, testing, and evaluating a new heuristic algorithm, indirect search, for efficiently solving the spatial harvest-scheduling problem. Efficiency, in this context, is understood to be a function of 1) the objective function value of the solution computed by the algorithm, and 2) the computing time required to calculate this solution. Specifically, this study will seek to answer four questions: 1) Are the objective function values of solutions calculated by the indirect search algorithm comparable to those of solutions calculated by other heuristic algorithms, such as simulated annealing and tabu search? 2) Is the computing time needed by indirect search impracticably long1 for use on large problems? 3) What are the causes of the relative efficiency of indirect search? 1 The practical value o f this algorithm w i l l be judged in the context o f its use as a tool by timber supply analysts working on large problems. This w i l l be discussed more fully below. 3 4) Is the general strategy of indirect search limited to the harvest-scheduling problem, or might it be applicable to other combinatorial optimization problems? 1.2.2 Importance of Problem The study is important for two reasons. First, there is a practical need for an algorithm that allows for faster computation of good solutions. This is because a faster algorithm can facilitate a more thorough sensitivity analysis of a given scheduling problem. In multiple-use forest planning today, a thorough—and sometimes playful— exploration of various combinations of constraints and parameters will aid analysts not so much in finding the answer to a given problem, but in gaining an insight into its nature. Such insights are necessary to help determine the sustainable level and allocation of cut. Second, any research into algorithmic efficiency should have theoretical rewards, and this is particularly true of research into heuristic methods for solving combinatorial problems. Until recently, many researchers have shunned using a heuristic for such problems, regarding it as an admission of defeat (Reeves 1993). Only in the last decade has there been an explosion of interest into heuristic methods. Hence, the heuristic field of research remains very much a lightly explored frontier for many problems. It is rich with possible improvements in computationally efficiency, especially in the discovery of 'hybrid heuristics' (Reeves, 1993). 2 Reeves (1993) credits this to two things: 1) advances in our knowledge of computational complexity, and 2) improvements in heuristic methods. Michalewicz and Fogel (2000) argue—provocatively—that most real-world problems do not yield to the traditional methods: "If they could be solved by classic procedures, they wouldn't be problems anymore." They argue that growth of interest into heuristic methods stems from a growing recognition of the benefit of matching the correct method to the structure inherent in a particular problem. In other words, mathematical programming methods have not become obsolete, but their appropriate limitations are increasingly understood. 4 1.3 Purpose and Objectives 1.3.1 Relation between Purpose and Objectives in this Study The purpose of this study has been to develop, evaluate, and understand a new heuristic algorithm, indirect search, for solving the spatial harvest-scheduling problems. A n evaluation of the algorithm will be based on its observed efficiency. In particular, the efficiency of this algorithm will be evaluated by comparing its solutions to those calculated by other algorithms. The comparisons are designed as follows: 1) Small tactical planning problems, with even-flow and strict adjacency constraints. Solutions will be evaluated by comparison to solutions calculated by simulated annealing and tabu search methods. 2) Large, strategic planning problems, with even-flow and strict adjacency constraints. Solutions will be evaluated by comparison to a linear programming model. 1.3.2 Delimitations of this Study There are two important limits to the conclusions that can be drawn concerning the relative efficiency of the indirect search algorithm. First, the comparisons to be made between the solutions calculated by the indirect search algorithm and those calculated by the simulated annealing and tabu search algorithms cannot be used to indicate indirect search's merit relative to tabu search or simulated annealing per se. This is because the particular sets of parameters used by simulated annealing and tabu search have a great influence on their efficiency (Reeves 1993, Michalewicz and Fogel 2000). For simulated 5 annealing, the cooling rate chosen affects the efficiency of the search; and for tabu search the parameter chosen for the short-term memory tenure is of cardinal importance. In addition to these parameters, the particular method of permuting the solution has an important influence on the efficiency of the search. Consequently, it would be inappropriate to draw any broad conclusions about the efficiency of indirect search when comparing its results to those of a particular implementation of tabu search or simulated annealing in solving the spatial harvest-scheduling problem. Second, it is difficult to draw any general conclusions on the efficiency of indirect search in solving the spatial harvest-scheduling problem per se. This is because only one element of this problem is incorporated into the problems tested, viz., adjacency constraints. Other constraints, such as patch-size limits, and serai patch-distributions, are not applied in these problems. Although the problems tested in this study are discrete optimization problems, it is impossible to evaluate the merit of indirect search in solving problems with other constraints until it is empirically tested. 1.3.3 Limitations of this Study Although much attention in this study will be directed to evaluating and understanding the efficiency of indirect, it is worth recalling that all models are simplifications of the real world. Solutions, therefore, are only solutions in terms of the model. Hence, we can only have confidence that solutions will be meaningful to the extent of the model's degree of fidelity to the real-world problem. In other words, i f the model rests upon too many unrealistic assumptions and rough approximations, then the solution may not only be meaningless, but misleading. It is therefore necessary to 6 acknowledge those elements in the harvest-scheduling problem that must qualify our interpretation of optimal solutions. First, the input data used in this model is imperfect. Our knowledge of the present forest inventory is imperfect and depends upon the resolution of the land classification system used and the methods of classifying stands found on the ground. In addition to this, the yield curves for each stand-class are estimates of variable accuracy. In many cases, there are no adequate, documented empirical models available to estimate yield, and the method of making such estimates should inform the analyst's interpretation of the solutions. In short, i f the data used in these models are "dirty" and biased (Garbage In), then the solutions may be of no value (Garbage Out). The acronym GIGO (garbage-in-garbage-out) represents a problem which analysts must consider when evaluating solutions to the harvest-scheduling problem. Second, the system modeled changes stochastically, over time, but the model used in this study is deterministic. Deterministic models assume that values for all uncontrollable variables are known with certainty and are fixed. The most important violations of this assumption in this study are natural disturbances caused by insects, fire, and pathogens; and patterns of human disturbance which change over time in response to unforeseeable policy changes. Hence, given these violations of the deterministic assumption, some justification is needed for applying a deterministic model to this problem. The first justification for using a deterministic model is that, since the harvest-scheduling problem rests upon so many complex processes, it may not be feasible to model the problem probabilistically. Although there are many spatially explicit 7 stochastic disturbance models for forest ecosystems, none has been seamlessly merged with a harvest-scheduling model. Instead, stochastic and deterministic models have been used to complement one another as decision-support tools for quantifying and allocating annual harvest levels.3 Second, the practical value of the deterministic model depends upon the degree of stability of the forest system modeled. Hence, although the model violates the deterministic assumption, the degree to which the system remains stable is such that the solutions are not entirely meaningless to decision-makers.4 Finally, a deterministic model does allow the introduction of uncertainties through sensitivity analysis. The robustness of a solution from a deterministic model solution can be tested by determining the amounts by which parameter estimates can be in error before significant changes in the objective function value occur. These limitations of the harvest-scheduling model allow us to regard it as a decision-support tool where input data should be updated continually. Limitations also shed light on the direction in which research into a more efficient search algorithm for this problem should take; viz., that a greater emphasis should be placed upon increasing the speed of the algorithm rather than minor advances of the solution toward optimality.5 Speed facilitates sensitivity analysis, which in turn lowers uncertainty; whereas minor improvements in the solution value alone are regarded by decision-makers as something akin to increases in a 'virtual harvest'. 3 This is not to say that it is impossible to design a feasible, stochastic model of the harvest-scheduling problem; rather, I am only stating that I am unaware of any or of how it might occur. 4 In other words, decision-makers will evaluate a deterministic model not simply by answering whether the deterministic assumption has been violated, but also, to what degree. 5 This emphasis is not the same for all problems. For problems involving more stable systems, the opposite emphasis might be more appropriate. 8 1.4 Study Overview The second chapter of this thesis contains a review and analysis of the supporting literature and concepts relevant to this topic. The methods and procedures are presented in Chapter 3 and the results are presented in Chapter 4. The discussion is presented in Chapter 5. The final chapter contains the conclusions and suggestions for further research. 9 Chapter 2 : Literature Review This literature review is divided into three categories, based upon the three general methods used to solve the spatial harvest-scheduling problem: 1) Exact Methods; 2) Heuristic Methods; and 3) Deterministic Simulation. 2.1 Exact Methods There have been three exact methods applied to the harvest-scheduling problem: 1) linear programming; 2) integer programming; and 3) dynamic programming. Each method will be reviewed separately. 2.1.1 Linear Programming The most widely used technique for harvest-scheduling in North America was once linear programming. Linear programming (LP) is a method for determining optimum values of a linear function subject to constraints expressed as linear equations or inequalities. One of the earliest LP-models used for harvest-scheduling was Timber R A M (Navon, 1971). Another popular LP-model was M A X M I L L I O N (Ware and Clutter 1971). Neither of these models included explicit spatial constraints. They were designed to calculate optimal sustainable harvest levels for even-aged, industrial forests. In 1979, the USDA developed an LP-model, M U S Y C , which was designed to deal more effectively with site-specific, environmental questions (Johnson and Jones 10 1979). Its failure to do so resulted in the wholesale revision of M U S Y C into F O R P L A N , and subsequently into F O R P L A N version II (Stuart and Johnson 1985). The standard F O R P L A N did attempt spatial allocation, implicitly, in its scheduled harvests; but this allocation was represented by a stratum-based solution in which homogenous forest units are aggregated. This aggregation resulted in a loss of both spatial resolution and site-specific data. Hence, forest managers were unable to allocate this schedule, in a meaningful way, to the reality of heterogeneous areas found on public forestland. Spatial constraints have been explicitly incorporated into LP harvest-scheduling models by Thompson et al. (1973), Mealey et al. (1982), Meneghin et al. (1988), and Weintraub et al. (1988). Notwithstanding these efforts, the insurmountable obstacle encountered by all LP approaches to solving the spatial harvest-scheduling problem is that the solutions found are not integral. Since the decision-variables in linear programming are continuous, adjacency constraints cannot be applied and harvest-units are often split. Splitting a unit can result in very small percentages of it being left for future periods - an undesirable situation because of the additional fixed cost of returning to the unit.1 From an operational and multiple-use perspective, field implementation of the solution is not practical unless the decision variables assume 0-1 values. 2.1.2 Integer Programming Integer programming is a special case of linear programming where all (or some) variables are restricted to non-negative integer values. The spatial harvest-scheduling 1 Similarly, road-links, when used within the harvest-scheduling problem, must also be integers. This is for the equally pragmatic reason that operational roads cannot be partially constructed. 11 problem requires that the solution define what harvest units should be cut entirely during each period. That is, decision variables must assume the values of zero or one. There are few spatially constrained integer programming models for harvest-scheduling. The most commonly cited model is that of Kirby et al. (1986). Their Integrated Resource Planning Model, is capable of solving modest-sized problems with spatial constraints. This is because problems incorporating opening-size and adjacency constraints are combinatorial in nature, and therefore as the number of decision-variables increase linearly, the solution space increases by disproportionately greater size. Hence, as Jones et al. (1986) demonstrated, the excessive computing cost of spatial planning makes integer programming a tool of limited usefulness. Integer programming, though, is a flexible method, and computing efficiency has improved through innovative formulations of the problem. Some gain in problem size capability has been realized by new formulations of adjacency constraints (Meneghin et al. 1988; Torres-Rojo and Brodie 1990; Jones etal. 1991; Yoshimoto and Brodie 1994, Murray and Church 1996); however, integer programming remains a useful method only for smaller problems. 2.1.3 D y n a m i c P r o g r a m m i n g Dynamic programming is a recursive approach to optimization problems. Unlike integer and linear programming algorithms, which are iterative (i.e., where each step represents a complete solution which is non-optimal), dynamic programming optimizes on a step-by-step basis, using information from preceding steps. A single step is not 12 itself a solution to the problem, but does represent information identifying a segment of the optimal solution. Given this feature of dynamic programming, it is often applied to problems requiring a sequence of interrelated decisions, and it is therefore suitable to the harvest-scheduling problem. Dynamic programming was applied to the spatial harvest-scheduling problem by Borges et al. (1998). They tested it on a small, gridded data set and concluded that the computational constraints of large problems preclude the possibility of finding an optimal solution using dynamic programming alone. The great shortcoming of dynamic programming is that computation time increases almost geometrically as the number of decision variables (a.k.a., dimensions of the state variable) increases linearly. 2.2 Heuristic Methods Heuristics have been explored as alternatives to integer programming for finding solutions to problems that are combinatorial in nature. The term heuristic is derived from the Greek word, heuriskein, which means, "to find". It is used in contrast to exact methods that guarantee finding a globally optimum solution. A heuristic is a technique that seeks good solutions at reasonable computational cost without being able to guarantee optimality, or even, in many cases, to state how close to optimality a particular feasible solution is (Reeves 1993). Despite these shortcomings, heuristic search is a useful method, and there are three main reasons for this. First, with the exponential growth in computing time required to solve combinatorial optimization problems, exact methods cannot compute 13 solutions to large problems in a reasonable period of time. Hence, a heuristic is used as the only way to solve large combinatorial optimization problems. Second, heuristic search is more flexible in coping with non-linear objective functions and constraints than linear or integer programming. Hence, heuristic models of real-world problems can be more relevant than mathematical programming models. Reeves and Beasely (1993), expressed this advantage, asking rhetorically: "Should we prefer an exact solution to an approximate model, or an approximate solution of an exact model?" Third, heuristic solution approaches can easily generate a host of good, feasible solutions. This is valuable in any decision-making environment where there may be obstacles to stakeholders accepting only one optimal solution. Four classes of heuristic search have been applied to the spatial harvest-scheduling problem: 1) Monte Carlo integer programming; 2) neighbourhood search; 3) genetic programming; and 4) hybrid heuristics. Each method will be reviewed separately.2 2.2.1 Monte Carlo Integer Programming Monte Carlo integer programming (MCIP) refers to the method of generating random samples of feasible solutions to combinatorial optimization problems and selecting the best solution (maximum or minimum) from these random samples (Conley, 1980). Arcus (1966) demonstrated that very good solutions are possible through this 2 This review of heuristic methods will be rather detailed at times because it is intended to fill in the conceptual foundations underlying the description of indirect search, presented in Chapter 3. 14 method if the number of solutions randomly generated is large. With regard to its suitability to the spatial harvest-scheduling problem, Nelson et a/.(1990) and O'Hara et al. (1989) observed that this search algorithm ought to yield, with respectable efficiency, good solutions because there appears to be, in the problem itself, a reasonable number of solutions that are relatively close to the optimum solution. O'Hara et al. (1989) used MCIP to schedule 242 units over 5 planning periods of 10 years subject to even-flow and adjacency constraints. Although this was a tactical plan, they excluded roads. They estimated the proximity of the heuristic solution to the true optimum in two ways: 1) by comparing it to the problem's LP optimum, and 2) through calculating a confidence interval on the true optimum based on the number of solutions randomly arrived at in the search procedure. This method is based on work by Golden and Alt (1979).3 Their results, which also compare the different solutions calculated for three-period versus one-period adjacency restrictions, are presented in Table 2.1. T a b l e 2.1: Results using MCIP, by O'Hara et al. (1989). Duration ol' Adjacenc> Constraints MCIP % below LP optimum MCIP % below confidence interval's upper bound 1 period 3.25 1.66 3 periods 5.35 3.46 3 Boston and Bettinger (1999) argue that extreme value estimates may produce an unreliable estimate of the optimal solution in the harvest-scheduling problem. This is because the estimate assumes that the samples have a Weibull distribution and they found, in their work on the harvest-scheduling problem, that this hypothesis was rejected in 10 out of 12 situations. 15 Nelson et a/.(1990) used MCIP to schedule 45 harvest-units and 52 road units over three planning periods of ten years, subject to even-flow and adjacency constraints. They evaluated the best solution by comparing it to that computed by an integer-programming model: it was within 97% of the optimum. Although near-optimal solutions are possible through MCIP, the number of solutions randomly generated must be large. The direction which subsequent research took, following the groundwork laid by MCIP, was to improve the heuristic search by endowing it with a capacity to navigate the solution space with greater efficiency than pure randomness. 2. 2 Neighbourhood Search In a neighbourhood search, direction is given by ensuring that a subset of the feasible solutions is explored, in an orderly manner, by repeatedly moving from the current solution to a neighbouring solution. Each solution, x, has an associated set of neighbours called the neighbourhood of x. Neighbouring solutions are reached directly from x by performing a permutation operation upon x. This permutation operation may involve swapping two elements in the solution, or relocating only one element within the solution. There are many possible ways to define the permutation operation.4 Some creativity and experimentation are needed to find an effective operation.5 A neighbourhood, therefore, is defined as the set of solutions obtained by performing a 4 Interestingly, research in genetic programming has devoted more attention to this subject than research in neighbourhood search (Michalewicz and Fogel, 2000). 5 In the spatial harvest-scheduling problem, an efficient permutation operation for multiple rotation problems may differ from that used in single rotation problems. 16 permutation operation on the current solution. There are three general strategies used to explore the neighbourhood of the current solution and of deciding when to accept a neighbouring solution as the current solution. These are: 1) hill climbing; 2) simulated annealing; and 3) tabu search. Each strategy will be reviewed separately. 2.2.1 H i l l Climbing Hi l l climbing is the simplest form of a neighbourhood search: all neighbouring solutions are evaluated, and the best solution in the neighbourhood becomes the current solution. Inferior neighbouring solutions never become the current solution. The search ends when no improved neighbouring solution can be found or a fixed number of iterations has passed. The obvious consequence of this is that convergence upon a local, rather than a global optimum, is more likely than not in most problems. The importance of where the hill-climbing search begins, i.e., its initial solution is paramount in this strategy; for the search is deterministic after this initial solution has been formed. A common approach to overcome this limitation is to re-start the search from a different initial solution. Another approach is to accept the first neighbouring solution that is superior to the current solution as the new current solution. This latter strategy is sometimes referred to as hill climbing by random ascent (Cawsey 1998). A hill-climbing search was first applied to the spatial harvest-scheduling problem by Murray and Church (1993). They used the same data set as Nelson et al. (1990) with 45 harvest-units and 52 road-links scheduled over 3 periods. In addition to hill climbing, they tested a simulated annealing and a tabu search algorithm on the same problem and 17 compared their results to the Nelson et al. (1990) best MCIP solution and to the integer programming optimum (presented in Table 2.2). Table 2.2: Murray and Church's (1993) comparison of the results of different search methods applied to Nelson's (1990) 45 harvest-units and 52 road-links. Search Method Optimum (in ) Time (using 386/33 PC ) Monte Carlo random search 5,774.9 8 hours Hi l l Climbing 5,883.7 3 hours Simulated Annealing 5,897.1 11 hours Tabu Search 5,932.6 30 hours Integer Programming 5,953.0 60 hours For this problem, the results indicate that the more controlled methods of neighbourhood search are superior to MCIP's random search; and that, among the neighbourhood search methods, there is a correlation between longer computing times and higher solution quality Murray and Church also compared neighbourhood search strategies on a slightly larger problem, with 431 harvest-units planned over three periods, without roads (Table 2.3). 18 Table 2.3: Murray and Church's (1993) comparison of the results of different algorithms applied to 431 harvest units over three planning periods (without roads). Search Method Optimum Time (using 486/50 VC ) Simulated Annealing 2092.0 24.8 minutes Hi l l Climbing 2108 2.19 hours Tabu Search 2176.0 5.37 hours Integer Programming 2212.0 60 hours Liu (1995) also applied a hill-climbing search to the spatial harvest-scheduling problem. He scheduled 431 harvest blocks, over a 100-year planning horizon and compared hill climbing's efficiency with simulated annealing (Table 2.4). Table 2.4: Liu's (1995) comparison of hill-climbing and simulated annealing models. M o d e l O p t i m u m (total m/) T i m e (minutes) Simulated Annealing 5,647,595 36.8 Hi l l Climbing 5,638,033 32.7 Once again, hill climbing yields a very good solution with efficient use of computing time. 19 The results of Tables 2.2 to 2.4 are not sufficient to justify any universal conclusions on the relative merits of the neighbourhood search models, but they do suggest that: there is a trade-off 'between the quality of the solution and the computing time needed to converge upon it The weakness of the hill-climbing method is that it usually converges upon a local optimum and hence must begin again from a new starting point. It is arguable that a reliable heuristic should be less dependent on the starting point. Hence, in order to avoid the inefficiency of continuously restarting the solution after converging upon a local optimum, downhill-moves must somehow be allowed, i.e., acceptance of non-improving solutions. However, given that the final objective is to converge upon the optimum solution, these must be used sparingly and in a controlled manner. In simulated annealing and tabu search, downhill-moves are allowed, and they differ only in the manner in which they are controlled. 2.2.2 Simulated Annealing Simulated annealing starts with a high probability of accepting non-improving moves and this probability declines toward zero as a function the number of iterations completed. The inspiration for this form of control was Metropolis' work in statistical thermodynamics (Metropolis et al. 1953). Metropolis deigned an algorithm to simulate the cooling of a material in a heat bath, a process known as annealing. The cooling of a material interested Metropolis because, when a solid material is heated past its melting point and thereafter cooled back to a solid state, the structural properties of the cooled 20 solid are found to depend on the rate of cooling. If the material is cooled too quickly, it will contain imperfections. Metropolis attempted to simulate the rate of cooling which results in a near-optimal material, i.e., one without cooling imperfections. Kirkpatrick (1983) later formed and tested a brilliant analogy between a) the optimal rate of cooling a solid (as explored by Metroplis through simulation); and, b) the optimal rate of rejecting inferior solutions in a neighbourhood search. Kirkpatrick asserted that this depends on the temperature, T (determined by the number of iterations), and the difference between^, the current solution, and b, the incumbent solution. Equation [1] illustrates how this is calculated: ? = e[(A-bvn [ 2 ] The incumbent solution, b, is accepted i f a randomly chosen number is greater than P. Otherwise, A remains the current solution. This implies that the probability of accepting an inferior solution decreases as both T is lowered and to the extent that A, the current solution, is superior to b, the incumbent solution. Lockwood and Moore (1992) were the first to model the harvest-scheduling problem using the simulated annealing method. They obtained solutions for two impressively large harvest-scheduling problems: 1) A forest of 6,148 stands was scheduled for one rotation in 4 hours. 2) A forest of 27,548 stands was scheduled for one rotation in 30 hours. Unfortunately, Lockwood and Moore did not compare their results with those of another algorithm applied to the same problem. They expressed interest in measuring their results 21 against the exact optimum, however, they noted, this is a matter of speculation given that the optimum solution to this problem is unknown and likely to remain so. Murray and Church (1993) made two comparisons between the results obtained by simulated annealing and other neighbourhood methods (Tables 2.2 and 2.3). Liu (1995) also compared simulated annealing and hill climbing (Table 2.4). Dahlin and Salinas (1993) also applied simulated annealing to the harvest-scheduling problem. They scheduled 65 stands over four periods of 15-years and compared the solutions between a simulated annealing algorithm, an MCIP algorithm, and a SNAP II program developed by Sessions and Sessions (1991).6 The results are presented in Table 2.5. Table 2.5: Results from Dahlin and Salinas (1993) comparison of models used to schedule 65 stands over four period. Model Roads Scheduled Solution (NPV) Time Simulated Annealing No 3659 2 hours SNAP II No 3638 15 minutes MCIP No 3488 2 hours Simulated Annealing Yes 6525 2 hours MCIP Yes 6223 2 hours SNAP II Yes 5536 15 minutes The simulated annealing algorithm produced the best solution to each problem in about 2 hours. Compared to the SNAP II program, the simulated annealing algorithm is 22 quite slow. SNAP II produced good solutions in one eighth of the computing time used by simulated annealing. The results from Murray and Church (1993), Dahlin and Salinas (1993), and Liu (1995) indicate that the simulated annealing method can produce better solutions to the harvest-scheduling problem than hill climbing or MCIP. Given time, it will explore the solution space with greater diversity; but at an increased computing-time that needs to be balanced against the benefit of better solutions. Another cost to using the simulated annealing algorithm is that it requires some fine-tuning to get good results. Specifically, there is fine-tuning needed to find the best initial temperature, cooling rate, and termination condition. 2.2.3 Tabu Search Tabu search differs from the other neighbourhood search methods in its strategy of diversification, i.e., the actions taken to guide the solution into new areas of the solution space. Diversification is achieved by: 1) breaking out of local optima; and, 2) avoiding unproductive cycling—movement back and forth between the same solutions. Tabu search is designed to overcome local optimality in a more orderly fashion than simulated annealing. It de-emphasizes randomization in the neighbourhood. The assumption is that an intelligent search should be based on more systematic forms of guidance (Glover and Laguna, 1993). Accordingly, many tabu search implementations are largely deterministic. 6 The SNAP II (Scheduling and Network Analysis Program) software package schedules harvests, with spatial constraints and roads, at the tactical level. The solution algorithm does not receive a detailed description in the manual. 23 Intelligent diversification is imposed through the use of memory. There are two types of memory used in tabu search: short-term and long-term. The short-term memory is a list of solution-elements recently removed from the current solution and flagged as ineligible (i.e., forbidden, taboo) from inclusion within the solution for a given number of iterations. In the harvest scheduling problem, these elements are particular harvest-units cut in particular periods. The purpose of this memory is to avoid repeating the formation of the same feasible solutions. The long-term memory'is a list of solutions recently replaced by superior solutions. This is a list of 'lesser' solutions and tabu search will select the best solution from this list when it has reached a local optimum. This is clever because, having reached a local optimum, and therefore having to accept an inferior solution, the search resumes from a promising solution whose neighbouring solutions have not been explored. Tabu search has been applied to the spatial harvest-scheduling problem by Murray and Church (1993) (Tables 2.2 and 2.3). Brumelle et al. (1998) also developed a tabu search algorithm for the harvest-scheduling problem. They applied it to two problems, each with a 60-year planning horizon, and compared their results to a MCIP algorithm (Table 2.6): Table 2.6: Brumelle et al. (1998) tabu search results Algor i thm 219 harvest-unit problem (max. m 3 harvested) 491 harvest-unit problem (max m 3 harvested) Tabu Search 571,432 1,787,577 MCIP 537,371 1,533,568 24 Brumelle et al. also observed that the tabu search is several orders of magnitude faster than the Monte Carlo method. Boston and Bettinger (1999) also applied a tabu search algorithm to the harvest-scheduling problem. They scheduled 625 stands over ten one-year periods for four different problems. The 4 problems differed in only two respects: the ages and the logging costs randomly assigned to each harvest-unit. Its best solution values, from 500 runs, were compared to the best solutions generated by simulated annealing and MCIP algorithms applied to the same problems. The integer programming optima were also calculated to function as upper bounds (Table 2.7). T a b l e 2.7: Results from Boston and Bettinger (1999). Problem Integer Optimum fabu Search Simulated Annealing MCIP 1 100% 93.7% 96.6% 86.8",. 2 100% 97.2% 98.1% 92.1% 3 100% 100% 99.8% 96.2% 4 100% 95.7% 96.5% 86.9% Simulated annealing was able to locate the best solution values to three of four problems, but had a greater range in objective function values than tabu search. These results differ from Murray and Church's (1993), in which tabu search had superior solutions to simulated annealing. This difference indicates the importance of the choice parameters used to govern the search strategies. 25 2.3 Genetic A lgor i thm The idea of a genetic algorithm (GA) can be understood as the intelligent exploitation of a random search. It originates from the idea that a vector of components may be viewed as analogous to the genetic structure of a chromosome; and that, just as in selective breeding desirable offspring are sought by combining parental chromosomes, so too, in combinatorial optimization, solutions may be sought by combining desirable pieces of existing solutions. Central to the G A approach is the careful use of what are called genetic operators, i.e., methods of manipulating chromosomes. The two most common genetic operators are crossover and mutation (Banzhaff et. al 1998). Crossover is the act of exchanging sections of the parents' chromosomes. For example, given parents PI and P2 with crossover at point X , the offspring will be the pair 01 and 02, as illustrated in Figure 2.1. PI 1 0 1 i 0 I 0 1 0 Ol 10 1 0 0 0 1 X P2 0 1 1 1 00 1 02 0 1 1 1 0 10 1 f F i g u r e 2.1: Example of cross-over operation. 26 Mutation, on the other hand, is a permutation of the chromosome itself, not unlike the permutation operation in neighbourhood search. Since each chromosome encodes a solution to the problem, its so-called fitness value is related to the value of the objective function for that solution. The higher the fitness value, the higher is the chance of being chosen as a parent. The reproductive plan is repeated for a fixed number of iterations. It is possible to explore many different methods within the G A approach to solving a problem. For example, programs may use: 1) different data structures to represent a chromosome;7 2) different genetic operators (e.g., more than one cross-over point could be used); 3) different methods for creating an initial population (e.g., random selection of feasible solutions versus biased selection of feasible solutions); and 4) different parameters (e.g., population size, probabilities of applying different operators). This flexibility of G A also implies that considerable time must be spent experimenting with various options to find the most efficient search. Liu (1995) applied a genetic algorithm to the harvest-scheduling problem. He compared the solution obtained from his GA-model to solutions yielded by simulated annealing and hill climbing for 431 harvest blocks scheduled over a 100-year planning horizon subject to even-flow and adjacency constraints (Table 2.8). 7 Classical genetic algorithms use a fixed-length binary string for the chromosomes and genetic operators; hence, mutation and cross-over were always 'binary'. The newer, so-called "evolution programs" allow any data structure to represent the chromosome, thereby allowing greater flexibility in choosing genetic operators. 27 Table 2.8: Liu's (1995) results comparing G A to simulated annealing and hill climbing. Model O p t i m u m (total m i T i m e (minutes) Simulated Annealing 5,647,595 36.8 Hi l l Climbing 5,638,033 32.7 Genetic Algorithm 5,618,245 378.0 Liu observed that this particular GA-model proved to be disappointingly slow because the cross-over operation, especially in the earlier operations, tended to direct the search too far away from the previous location; and it resumed from significantly inferior solutions before re-establishing its previous location. Liu suggests that this shortcoming may be remedied by improving the cross-over operation. Banzhaf et al. (1998) observe that, in nature, most cross-over events are successful (they result in viable offspring); whereas in GA, 75% of cross-overs are lethal to the offspring. GA's analogy to sexual reproduction breaks down when one recalls that biological cross-over usually results in the same gene from the father being matched with the same gene from the mother. In other words, the hair colour gene does not get swapped for the tallness gene. In GA, the same attention to preserving semantics is not possible. Hence, most cross-over operations result in "macromutations". This adds to the diversity of the search, but the cost in computing time is considerable. 2.3.2 Specialized Heuristics 28 The appeal of the exact and heuristic methods reviewed thus far is that their general problem-solving strategies can be applied to many types of problems. This quality is referred to as domain independence (Reeves 1993). Creating a specialised heuristic, however, requires that some problem-specific knowledge be used in designing the heuristic's strategy. This oftentimes limits the applicability of such strategies, but this may be a price worth paying in order to find a more efficient algorithm to the harvest-scheduling problem. Two specialised heuristics are reviewed here, and it is interesting that both are aimed at overcoming the shortcomings of exact methods discussed earlier. First, a heuristic coupled with linear programming, designed to produce integer values for the decision variables; and second, a heuristic coupled with a dynamic program, designed to solve larger problems. Weintraub et al. (1995) merged a linear programming algorithm with a heuristic algorithm to schedule harvest-units and roads as integer variables. This hybrid is a three-stage, iterative algorithm that: 1) solves a continuous LP problem; and then 2) processes the LP solution with heuristic rules for determining which fractional variables to round to integer values; and then 3) incorporates these decisions into the LP matrix, and returns to step one. The process stops when all road-building and harvest-unit variables have integer values and there are no additional feasible changes that improve the solution. Weintraub et al. tested this algorithm on two small problems of different sizes: 1) 11 polygons and 11 road-links scheduled over 3 periods; and 2) 28 polygons and 44 road-links scheduled over 3 periods. The solutions calculated by their algorithm deviated 0 % and 2.8 % from the integer optima, respectively. Computing time averaged less than 20 29 minutes. Although Weintraub et al. note that more refinements are needed , it is difficult to evaluate its practical merit because the problems it has been tested on are relatively small. Hoganson et al. (1999) developed a specialised heuristic for applying dynamic programming to large harvest-scheduling problems. It is a two stage procedure that first uses dynamic programming to calculate a set of optimal solutions for several smaller, overlapping areas of a large problem; and then, uses a heuristic to define and link these sub-problems such that solutions to the master problem are solved. Critical to the effectiveness of this algorithm is the degree to which sub-problems overlap in area. Hoganson et al. found that a 90% overlap in area of sub-problems produced best results. This algorithm was applied to three large forests, ranging from 2,954 to 3,215 harvest-units, for scheduling over five ten-year periods. Computing time, on a 90 M H z Pentium I microprocessor, was approximately 8 hours per solution. They evaluated the heuristic solutions by developing a procedure to determine their bounds,9 and estimated that these solutions were within 0.1 % of each optima. It is difficult to evaluate the efficiency of this specialised heuristic because of the method used to evaluate the solutions. Certainly, a comparison with an integer program exact optimum on a smaller problem would have helped in forming an evaluation. E.g., The algorithm has not been programmed into an automated, closed system; i.e., manual steps are still involved in applying the procedure. 9 The merit of this procedure is unclear to me. In effect, they modified the problems such that sub-optimal solutions to the former master problems became the optimal solutions to the modified problems. They then used their specialised heuristic again to solve these modified problems, checking how close these solutions are to the optima. 30 2.3 Simulation Simulation is a methodology for conducting experiments using a model of a real system. There are two general kinds of simulation: 1) deterministic simulation, which involves variables and parameters which have been fixed and are known with certainty; and 2) stochastic simulation, which assign probability distributions to some or all variables and parameters The purpose of simulation is to use a model of a real-world system as an experimental tool, in order to predict the behavior of the system for the purpose of designing the system or modifying its behavior. As such, it is distinguished from optimization procedures that seek to optimize some criterion. Many reasons are be advanced in support of simulation (Budnick et al. 1977): i) Simulation can provide solutions when analytic models fail to do so, ii) Models to be simulated can represent a real-world process more realistically than analytic models because fewer restrictive assumptions are required, iii) Changes in configuration or structure can be easily implemented to answer "what happens if . . .?" questions. Various management scenarios can therefore be tested, and iv) Simulation can be used for teaching purposes either to illustrate a model or to better comprehend a process, as in publicly contested management scenarios. Nelson et al. (1996) developed a deterministic simulation model of harvest-scheduling under adjacency constraints. They simulated harvest-scheduling activity with a greedy algorithm that cuts the oldest, eligible stands first. Liu (1995) compared the 31 results from his simulated annealing algorithm to those produced by Nelson's simulation model on a problem of 419 harvest-units scheduled for five twenty-year periods (Table 2.9). Table 2.9: Liu's (1995) comparison of results from Nelson's (1996) deterministic simulation model and a simulated annealing algorithm. The initial age of all stands is 90 years. SA (even-flow) A T L A S (even-flow) A T L A S (fall-down) Period 1 974,697 845,640 1,387,530 Period 2 1,015,575 852,225 1,256,358 Period 3 1,043,048 849,090 1,092,389 Period 4 1,095,800 844,243 778,791 Period 5 1,131,460 802,610 596,770 Total 5,258,580 4,193,808 5,111,838 Time 34 minutes 30 seconds 30 seconds These results indicate that the simulated annealing calculates solutions yielding more volume than the simulation model's greedy algorithm. Since simulated annealing schedules across all-periods, its even-flow schedule yields more timber (25% more). The greedy algorithm selects harvest-units sequentially and therefore cannot make tradeoffs between planning periods. In other words, because it cannot forego present harvests for the sake of a higher harvest later, the greedy algorithm is unable to generate globally 32 optimal solutions over the entire planning horizon. This difference is more pronounced with the above results because the schedule is for a forest which is undergoing conversion to a regulated state.10 Interestingly, when not constrained by even-flow, the greedy algorithm harvests only 2.9% less timber than the simulated annealing model. It also does so 68 times more quickly. The results indicate that there is a trade-off between total volume scheduled and speed. The clear advantage of the greedy algorithm is speed. The practical value of this speed advantage is that it might make relatively huge harvest-scheduling problems that are unsolvable by neighbourhood search algorithm, practicably solvable by a greedy algorithm." In a forest where all stands are eligible in period one, for example, there are more possible harvest schedules to choose from than in a regulated forest, simply because there are more eligible harvest units per period. Hence, simulated annealing's superiority to the greedy search ought to decrease as the forest approaches regulation. For example, in British Columbia, there are 35 Timber Supply and their A.A.C.'s cannot, for political reasons, be calculated piecemeal. At present, there are no spatially explicit harvest-schedules for these areas. Such schedules might be practicably accessible through a simulation model with a greedy algorithm. 33 Chapter 3: Methods and Procedures 3.1 Development of Indirect Search Algorithm 3.1.1 Description of Algorithm The indirect search algorithm developed for this study is a combination of greedy search and neighbourhood search algorithms. The greedy search algorithm for harvest-scheduling under adjacency constraints (based on Nelson er al. 1996) is illustrated in Figure 3.1. Like all greedy algorithms, it constructs the complete solution in a series of steps. It assigns the values for all of the decision variables to a prioritised queue, and at every step makes the best available decision; i.e., in each period it harvests the oldest eligible harvest-units first. This approach is called greedy because it is short-sighted, i.e., taking the best decisions at each step doesn't always return the best overall solution (Michalewicz and Fogel 2000). The indirect search method improves the greedy search's short-sighted solution by iteratively 1) randomly permuting one of its prioritised queue, 2) running the greedy search, and 3) measuring whether the permuted queue improve the objective function value. If the solution value increases, then the permuted queue becomes the current queue. If it does not, then the current queue is preserved. Current queues are permuted in this manner for a fixed number of iterations. In effect, the indirect search algorithm is a search for a set of prioritised queues for a greedy search algorithm for harvest-scheduling under 3 ¥ BEGIN Initialize run parameters Number of periods= P_MAX Periodic harvest target = VOL_MAXperiod I Begin run period = 1 Begin New Period -Form proritised queue of harvest units in descending order by age -Let x = 1 I Select harvest unit of xth rank from input queue N O Increment x harvest it and periodically constrain its neighbours •add unit's volume to period's volume Y E S N O Figure 3.1 : Flowchart of greedy heuristic for harvest-scheduling under adjacency constraints 35 adjacency constraints. In detail, the algorithm proceeds as follows: 1. Assign values to parameters alpha and beta that are less than or equal to the number of harvest-units in the problem. 2. Begin iteration by selecting a period in which the prioritised queue will be altered. 3. Run the greedy algorithm until this period is reached. 4. Randomly generate two integers, i and j , between 1 and alpha and 1 and beta, respectively. 5. In the current periodic queue, swap the i t h element with the j t h element, then harvest this period and all subsequent periods using the greedy algorithm.. 6. Calculate the objective function. 7. If the objective function value increases or remains the same, then let the permuted periodic queue become the new current periodic queue; otherwise, discard the permuted queue and revert to current periodic queue. Repeat steps 2 to 7 for a fixed number of iterations. A l l initial prioritised queues are formed with a view to greedily maximize the objective function. For example, i f the objective function is to maximize net present value, the initial prioritised queues are formed by ranking all harvest-units in descending order of net present value; but if the objective function is to maximize total volume harvested, then they are formed by ranking all harvest-units in descending order by age or by volume. 36 After a fixed number of iterations, prioritised queue in every period will have been repeatedly altered, tested and accepted or rejected. Hence, the heuristic element of this model "seeks", through the neighbourhood search algorithm of hill-climbing by random ascent, the best prioritised queue for each period, using improvements in the objective function as a guide to an improved queue. The solution to the harvest scheduling problem, i.e., the sequence of harvest-units cut, is thus indirectly formed by the search for a set of queues which maximises the model's objective function. 3.1.2 Choice of Algorithm's Parameters There are two important parameters in the indirect search algorithm. First, is a set of parameters regulating the selection of a prioritised queue for a particular period's to be permuted at the beginning of each iteration (step 2, above). In this study, each prioritised queue for all harvesting periods receives an equal number of permutations. The selection is structured such that the search begins by experimentally permuting the period-one queue for a fixed number of iterations before moving to period-two; the period-two queue is then experimentally permuted for a fixed number of iterations before moving to period-three, and so on. After the last periodic queue has been experimentally permuted for a fixed number of iterations, the search returns to the period-one queue for a second loop of iterations.1 Only two such loops were used for the runs in this paper. For example, i f 10,000 iterations are to be performed on a ten-period problem, then the first 500 iterations test the effects of permuting the period-one queue, the next 500 of permuting the period-two queue, and so on. After 500 iterations of searching for the best queue in period-ten, 37 the search returns to the period-one queue and continues there for 500 more iterations, and so on. This procedure of sequentially selecting a prioritised queue for each period was chosen because, in this model, the best queues in later periods are a function of the best queues in earlier periods, and not vice versa. The second important choice of parameters is for the values of alpha and beta (step one, above). These values determine the search space and its size for the prioritised queue in each period. In the indirect search algorithm, alpha equals the number of harvest-units which the greedy algorithm tests for eligibility before the periodic maximum volume is reached; and beta equals the number of harvest-units eligible at the beginning of a period. For example, suppose that at the beginning of a given period there are 450 eligible harvest-units (beta = 450); but the greedy algorithm only processes 85 of these before the periodic harvest-target is reached (alpha = 85). Values for alpha and beta are thus determined because a swap between harvest-units located in elements greater than the 85 t h of this queue would have no effect on the solution.. Since values for alpha and beta change from period to period, the algorithm continually recalculates these values. This method allows for a maximum of diversity in the search within a smaller search space. The diversity is maximised because all eligible units can have their positions altered in the prioritised queue. The size of the search space is smaller because the number of eligible harvest-units, p, is usually less than the total number of units in the problem, n; hence, the search space for the best queue in each period, p!, is usually less than n! ? The advantage of breaking the search into smaller neighbourhoods is analogous 1 The purpose looping back to the first period is to liberate the search fully from the deterministic influence of the initial prioritised queues upon the objective function value. 2 For the second loop, the same method of choosing alpha and beta is used; although this requires extra computing effort. 38 to breaking the search for one needle within one very large haystack into the search for one needle within with each of several small haystacks. 3.1.3 Methods of Verifying Solutions This algorithm was encoded in the C programming language and the program output file contained: 1) the final schedule, i.e., a list of polygons cut and the year in which they were cut; 2) the volume cut per period; and 3) the final objective function value. Verification of the solutions involved two processes. First, the objective function value was checked by calculating the volume per harvest unit implicit in the final il.^ ll.ll.at'JI.|U).llillHI,«l|jPB,f!lill e i a a a f, j i s t : • E E S 5 - 0 Polygon topology vi } i I S Format • ; { i <? Attribute | - D Specify i j i-O SurfaceType J iE-O Distance 3 © Age 1 f D i II | (HI 2 ; ®M i o ! • M is j l|l • 20 i • BiEBI $ G AdjTimer 1 $ - 0 Area if- O ProdAreo% &--0 FixedSchedu $ h O FrxedSched_ | % AgeRsv s mO UserAgeAttr Treated $ C Treat State Vol_Harvest 4hQ %BlkRsv ifi-O HarvestCost 4 C FailedAdj V j ; ^ V o l H a r v ;• # VolStanding $ - O Vol_ha_PR | HarvCost : 0 FSFlag ! I i 0 State j C Zone Figure 3.2: Viewer used to verify implementation of adjacency constraints 39 schedule. This was done using a Microsoft Excel spreadsheet. Second, the adjacency constraints were checked by importing the schedule into Forest PlanningStudio (Nelson et al. 1999), a software package which includes a map viewer. In Forest Planning Studio, adjacency constraints were checked by viewing the harvest-schedule, period by period.3 This viewer, illustrating an imported solution, is presented in Figure 3.2. 3.2 Case Studies 3.2.1 Rationale for Case Studies Two harvest scheduling problems are considered: 1) a set of small tactical planning problems with 625 harvest units over ten one-year periods; and 2) a large strategic planning problem, involving 3,857 harvest units over twenty ten-year periods. Although an objective in this study is to develop an algorithm for solving large problems efficiently, a set of smaller problems was solved in order to evaluate the efficiency of the indirect search algorithm by comparing its results to those produced by other methods. The data sets for the smaller problems are identical to those used by Boston and Bettinger (1999) and the results of the indirect search algorithm will be compared to theirs. Solutions to the larger, strategic problem will be evaluated by comparison to results from a linear programming model. 3.2.2 Description of Tactical Problems 3 Forest Planning Studio was also used to double-check the volume calculations in the imported solution. 40 Three data sets were provided by Dr. Kevin Boston and each consists of a 25 by 25 grid, with each cell representing a harvest unit of 30 ha. There is one yield curve based on radiata pine (Pinus radiata) from New Zealand (Goulding 1995). The ages were assigned to each data set using a random number generator and are uniformly distributed between 0 and 30 years. Logging costs per harvest-unit were similarly assigned and are uniformly distributed between $20 and $70 / m 3 . Hence, the data-sets differ in only two respects: the ages and the logging costs randomly assigned to each cell. A delivered log price of $100 / m 3 was used with an 8% discount rate. An even-flow periodic volume target was calculated by Boston and Bettinger using linear programming, and deviations were penalised at $100 / m 3 using a 9% discount rate. Each unit must be 19 years of age to be eligible for harvest and those units adjacent to units less than 2 years of age are ineligible. Adjacency occurs when units share an edge, i.e., each interior cell has four adjacent neighbours. 3.1.3 Formulation of Model for Tactical Problems The objective in these problems was to maximise net present value over a ten-year planning horizon with one-year periods. The model formulation is shown below. Maximise Z = 11 (Revit- Lcit). Vu . xlt -[ (Vp,. dl,) + (Vpt . dut)] [3] i t subject to: Volume constraint X Vjt • Xjt - dut + dlt = volume goal t for all t; [4] 41 Adjacency constraints for two periods njXu + YjXit +2Zxj(t.i)< n, for all i,t; [5] Integer requirement xlt e {0, 1} for al i i , /. [6] where: i = harvest-unit t - period Ni = set of harvest units adjacent to unit i nt = number of units adjacent to unit i Revu = revenue per cubic metre for unit i harvested in period t Leu = logging cost per cubic metre for unit / in period t Vjt - volume per hectare for unit i harvested in period t xit = 1 i f harvest-unit i harvested in period t, 0 otherwise Vpt = volume penalty per cubic metre in period t dut = positive deviation from volume goal in period t in cubic metres dlt = negative deviation from volume goal in period t in cubic metres 3.2.4 Description of Strategic Planning Problem The data set used in this problem represents Landscape Unit 26 (LU 26), from the interior of British Columbia. It comprises 23,926 ha and is divided into 3,857 harvest-units of irregular shape and size. Three yield curves, representing good, medium, and poor sites 42 are used. The age-class distribution of L U 26 is presented in Figure 3.3, and an age-class map is presented in Figure 3.4. 45% 40% S 35% 75 3 0 % 0 25% 15 20% 1 15% « 10% Q-5% 0% J* oP N # # ^ ^ <P <P 4* ^ ^ # Age Classes (years) Figure 3.3: Age class distribution of L U 26. Figure 3.4: Map of age classes of L U 26 43 The objective is to maximise total volume harvested subject to even-flow constraints. The planning horizon is 200 years and periods are 10 years. Harvest-units must be greater than or equal to 75 years of age to be eligible for harvest. Green-up constraints last 20 years and adjacency occurs when units share a common boundary node. 3.2.5 Formulation of Model for Strategic Problem The formulation of the model for the strategic planning problem is similar to that of the tactical plan, except that the goal is to maximize total volume. A penalty cost is used in the objective function to achieve an even-flow of plus or minus 5% between periods. The formulation of the model is shown below Maximise Z = IZ (Vit . xit ) - f(Vp,. dl,) + (Vpt . du,)] [7] i t subject to: Volume constraint Z Vu • xu - du, + dl, = volume goal, for all t; [8] Adjacency constraints for two periods njXit + YjXit +YjXi(t.i)< rii for all i,t; [9] ieN, i e /V, Integer requirement xit e {0, 1} for all / , t. [10] where: i = harvest-unit 44 t = period Nj = set of harvest-units adjacent to unit i rij = number of units adjacent to unit i Vit = volume per hectare for unit i harvested in period t Xu = 1 i f unit i harvested in period t, 0 otherwise Vpt = volume penalty per cubic metre in period t dut = positive deviation from volume goal in period t in cubic metres dlt = negative deviation from volume goal in period t in cubic metres 3.2.6 Formulation of Linear Programming Model The results of the indirect search application to the strategic planning problem are to be compared with those of a linear programming model. The objective of the LP model is to maximise total volume harvested subject to an even-flow constraint of plus or minus 5% of volume harvested between 10-year periods. There are no adjacency constraints and no integer constraints. A Model I formulation has been used, with two timing choices. The mathematical formulation is presented below. Maximise I K , Z = I I X i k H i k [11] i=l k=l subject to: Land accounting constraints 45 K, Txik < AREAj 0=l,...J) [12] *=/ Harvest accounting rows i K, Z Z HikjXik-Hj = 0 (j=l,...n) [13] ;=/ k=l Upper limit on periodic harvest fluctuation uHj-Hj+x>Q (j = \,...,n-l) [14] Lower limit on periodic harvest fluctuation lHj-HJ+l<0 (/=!,..., n-l) [15] L T S Y accounting row i K, Z Z CLTSYikXik - LTSY = 0 [16] /=/ k=I Harvest in last period not to exceed L T S Y H„-LTSY< 0 [17] where / = the number of timber stands Ki = the number of timing choices for harvest-unit i n = the number of planning periods Xtk = ha of harvest-unit i harvested under timing choice k AREAi = the total ha of harvest-unit i Hj/g = the volume of timber yielded from unit i under timing choice k in period j Hj = the total volume harvested in period j CLTSYjk = the contribution of 1 ha of stand s under timing choice k to L T S Y LTSY = accounting variable that measures long term sustained yield capacity of the 46 solution / = lower bound u = upper bound 3.2.7 Matrix Generation for Linear Programming Model Johnson and Scheurman (1977) first used the terms Model I and Model II to distinguish the two ways that decision-variables for a harvest-scheduling problem are defined. The distinction arises from the way the regenerated stands are handled. Model I defines decision variables that follow the life history of a hectare of land over all planning periods while Model II adds new decision variables for future stands. The advantage of using Model II formulation is that it provides a more compact matrix, with far fewer columns and only a minor increase in row number (Davis and Johnson, 1987). The disadvantage is that it is more difficult to track the passage of a hectare from rotation to rotation than with Model I. Since the linear programming package used in this work (Visual Xpress-MP) could accommodate the Model I formulation, Model I was chosen in order to simplify verifying and interpreting the solution. The matrix contained 61,734 columns. This value breaks down as follows: • Each of the 3,857 existing stands must be cut within the first 8 decades and there were two timing choices for each stand. One timing choice was for a 75 year rotation and the other for a 85-year rotation (3,857 x 8 x 2 = 61,712 columns) • 20 accounting variables, one for each period • One ending inventory variable, L T S Y • One total volume variable, TOT_VOL 47 The matrix contained 3,918 rows. This value breaks down as follows • R o w l : Objective function, e.g., max T O T V O L • Rows 2-21: Accounting rows defining each of 20 periodic volumes, HI To H20 • Row 22: Defines total volume harvested: e.g., - T O T V O L + HI + ... + H20 = 0 • Row 23: A constraint on ending inventory ensuring that the harvest in the last period not exceed the long term sustainable yield (LTSY) - E.g., H20<= 581,558 LTSY' s value was calculated according to Davis and Johnson's (1987) method illustrated in Table 3.1. Table 3.1: Calculation of minimum ending inventory value for LP model of L U 26 Stand Area (ha) Mean Annual Annual Group Increment Growth=mean (m3/year) annual increment x area 1 7,637.5 3.1 23,294.4 2 7,941.2 1.3 10,403.0 3 8,347.6 2.9 24,458.5 Total 58,155.8 • Rows 24-61: Even flow constraint (+/- 10% between periods) E.g., -0.9H1 + 1H2 <= 0 (row 24) -1.1H1 + 1H2>=0 (row 25) • Rows 62-3918: Area constraints for each of the 3,857 harvest units 48 The matrix for this model was generated in MPS format through a set of programs I wrote in Microsoft Visual C++. The matrix was then solved in a commercial software package, Visual Xpress-MP. The solutions were verified by spot-checking the total volumes harvested from 100 randomly selected harvested units over the entire planning horizon. 49 Chapter 4: Results 4.1 Results from Tactical Problems Thirty runs were performed for each of the three tactical planning problems using the indirect search algorithm. The mean objective function values for the three problems are presented in Table 4.1 alongside Boston and Bettinger's (1999) best objective function values found using tabu search, simulated annealing, and linear programming. Standard deviations of the mean objective function values were less than 1% of the mean for each problem. Table 4.1: Objective function values for three tactical planning problems. Units are in dollars. I'mhk'm Indirect Search: 1 ()().()()() iter. Indirect Search: 10.000 iter. Tabu Search Simulated Anneal ing One 144,928,544 142,849,440 I35.7')S.046 139,858,888 I4".5 10,000 (98.2%) (96.8%) (92.1%) (94.8%) (100%) T w o 166,044,592 165,179,472 161,395,343 162,857,021 170,948,003 (97.1%) (96.6%) (94.4%) (95.3%) (100%) 231,944,752 227,240,320 230,043,094 229,583,008 234,852,648 Three (98.8%) (96.8%) (98.0%) (97.8%) (100%) The results reveal that the indirect search, after 100,000 iterations, converges upon a higher objective function value than the other heuristic search methods in all three 50 IS • S U O I J t l [ O S S U I J E S U U B p s j E i n u i i s puB qo jBss nqej siq J O J sauii} Suimduioo sqj pjooaj jou pip uojsog J Q 'ApjBumjojuri _, 0'9 uoisjsA '++3 jETisiA U O S O J O I J M uo pauduioo SBAY uiqiuo§iE qojsas panpw aqi J O J urejSojd aqx , suiaiqoad paonoei aqi JOJ suonmari OOO'OOI • I 3 A 0 ssupress psjipm jo SSSJSOJJ :yp aanSij g Luaiqojd z tuaiqoJd ~ " V maiqoJd U0|}BJ9}| 000001 0009Z 00009 00093 0 1 1 1 [• %Z6 r %e6 •SUOIJBJ3JT 000'0C 1 S J TJ 3 I N ''a7 ISJIJ. sip Suunp jnooo uorinjos sip 01 siuauisAOjdun sqa jo jsora jcin sreaAai JJ ' T ^ ajnSij UT p91U9S9jd SI SUOI1BJ91T OOO'OOI §UTJtip TJ0JB9S J09JipUI 31T1 JO SSOjSojd fBOldXx ^spuooss Vm sgmuiui 1 si suorrejsii OOO'OI J 0 J 3 i m l Sunndraoo sq i "£ l ° u m c l '2 P T O I suisjqojd in suonnjos jousdns spuij. unnuoSre qoreas psiipui aqj 'suonmaji OOO'OI J 3 9 V ,'Jossaoojdojoxiu HI tumjuoj zfj]AI OSI?B u o spuooas zv P U B ssmuiiu 93 SBAY SUOIJBJSJI OOO'OOI J 0 J suiii gunndraoo 3 q x •ApAnoadsM 'umimido j q ainjo %8'86 P U B '%I'Z,6 '% £'86 uiiniAV are qojtaas pajipui aqi JOJ sanreA uouounj sAipafqo sip '£ 01 T suj3|qojd J O J •soumioos 4.2 Results for Strategic Problem The results for the strategic planning problem are presented in Table 4.2. Table 4.2: Results of LP and indirect search models for strategic planning problem LP Indirect Search 1.000 iterations Indirect Search 10.000 iterations Indirect Search 100.000 iterations 13,403,942 11.493..943 11,647,687 11,680,728 Total Volume (m3) (100%) (85.8%) (86.9%) (87.1%) Computing Time (min.) 16.5 6.3 62.5 633.3 The results show that between 1,000 and 100,000 iterations of the indirect search, the total volume harvested increased only slightly: from 85.7% to 87.1% of the LP-optimum. They also show that the size of the problem has disproportionately increased the computing time required relative to the tactical planning problem; i.e., although the strategic plan has twice as many periodic queues as the tactical plan and 6.2 as many harvest units, the computing time has increased not by a factor of 12.4 (6.2 x 2), but by a disproportionate factor of 23.7 (the cause of this will be addressed in the Discussion). Figure 4.2 illustrates the flow of timber over time for the strategic problem. It reveals two important results. First, significant improvements in the even-flow of timber 52 occurred between 1,000 and 10,000 iterations, but not between 10,000 and 100,000 iterations. There are two possible explanations for this: either the indirect search converged upon a near-optimal solution at 10,000 iterations, after which no significant improvements were possible; or, the search became trapped in local optima in each prioritised queue and could not find possible improvements. Given that indirect search has displayed the capacity for diversifying its search in the tactical problems, I am inclined to accept the former explanation; but more testing of the algorithm is needed before unqualified confidence in the search's capacity for diversification should be deemed prudent. ,000,000 C O E. cu E O > 100,000 .LP . 1,000 iterations . 10,000 iterations . 100,000 iterations Figure 4.2: Achieved timber timber flows for the strategic problem for the LP model and three sets of iterations of the indirect search algorithm. 53 The second important result revealed by Figure 4.2 is that in the first rotation the indirect search achieved far smaller timber flows than those of the LP model. The cause of this is adjacency constraints. This was confirmed by running the indirect search model without adjacency constraints and observing much higher flows in the first rotation. Hence, this was a highly constrained problem, implying that the number of eligible units per period, and therefore the search spaces for best prioritised queues, was relatively small. This supports the above conclusion that the algorithm made little improvement to the solution between 10,000 and 100,000 iterations because few significant improvements were possible. 54 Chapter 5 : Discussion 5.1 Explanation of Efficiency of Indirect Search Algorithm The indirect search converged upon solutions to the tactical problems that were superior to those reached by tabu search or simulated annealing. There are two possible explanations for these results. First, following an alteration in a prioritised queue, the algorithm has two venues by which to improve the solution: 1) a new sequence of harvest-units resulting from the alteration, and 2) an opportunity, i.e., a removal of adjacency constraints, allowing the greedy algorithm to immediately harvest a newly eligible harvest-unit. When an alteration is made directly upon the solution, as it is with simulated annealing and tabu search, it is not possible to take immediate advantage of the potential gains offered by the removal of adjacency constraints. Such gains may be made only through subsequent, random alterations of the solution. Hence the indirect search algorithm can improve the solution more quickly than other neighbourhood-search algorithms because of the temporal immediacy with which it exploits the removal of adjacency constraints caused by a permutation operation. Second, since a neighbourhood search is performed upon the prioritised queue of each period, there are multiple neighbourhoods. This is advantageous because when a local optimum is found for a given queue, the indirect search may continue by switching to a different periodic queue. There is no need to accept inferior solutions in order to carry on the indirect search for the best solution. Also, since the change in a prioritised queue for a given period can alter the effect of input queues of subsequent periods, it is 55 possible to reach a local optimum in a specific period's queue, and later, in the second loop of the search, return to this queue, and find that its effect on the objective function value has changed. In effect, there is a new neighbourhood search. This looping, therefore, allows for greater diversity in the indirect search without paying the cost of restarting the search from inferior solutions. 5.2 Computing Time and Problem Size The results from the strategic planning problem show that average computing time per iteration increased disproportionately (almost twofold) to the increase in problem size. The disproportionate increase occurred not because of the increase in the number of harvest-units, but because of the increase in the number of periods from 10 to 20. Extra computing time is needed during the re-calculation of periodic volumes for periods prior to the queue being altered. In other words, the larger strategic problem expanded its search space by having 6.2 times as many harvest units and twice as many periods; but the computational burden was also increased by re-calculating, on average, the periodic volumes for twice as many periods prior to the period whose queue was being altered. This additional computational burden, in retrospect, was unnecessary because the periodic volumes for those periods prior to the period whose queue was being altered are unaffected by the alteration. Therefore, a slight change in the indirect search program would have ensured that an expansion of the problem size would cause a proportionate increase in the average computing time per iteration. The computing time per iteration should be proportionate to the size of the problem; however, it becomes proportionately more costly per iteration than tabu search 56 or simulated annealing as the problem size increases. This is because calculating a change in the objective function value caused by directly altering the solution, as is the case in tabu search and simulated annealing, is constant, regardless of the problem size. This might lead one to infer that, at some point in the expansion of problem size, it becomes impractical to use indirect search instead of a conventional neighbourhood search for a solution. To determine whether this is the case, further empirical tests on increasingly larger problems are required.1 5.3 Possibility of Convergence Upon Global Optimum Another point to discuss is whether the indirect search method satisfies the theoretical condition for convergence upon a global optimum, viz., that every feasible solution be reachable from every other. Simulated annealing, for example, satisfies this condition by accepting inferior solutions; and the probability that it accepts inferior solutions depends on how many iterations have transpired. Research into the statistical behaviour of simulated annealing shows that to guarantee convergence to a global optimum, simulated annealing requires more iterations than an exhaustive search (Dowsland, 1993). Since the indirect search algorithm does not accept inferior solutions, it is worth addressing the question of whether, given an unlimited number iterations, there is anything which might prevent the search from converging upon an optimal solution ? One reason this inference may not be valid, a priori, is that just as the computing time per iteration increases relative to problem-size, so too might the average value of an iteration increase relative to the value of an iteration in conventional neighbourhood search. 57 To answer this question, consider a particular harvest-scheduling problem. Suppose that, in the optimal solution to this problem, a harvest-unit, e.g., harvest-unit #4, is harvested in period 9. Is it possible to think of how, given an unlimited number of iterations, this might not be found by indirect search? The answer is yes. This would occur if, 1. In period 6, all harvest-units adjacent to #4 are ineligible for harvest because they are too young. 2. In period 6, all eligible harvest-units are cut, including harvest-unit #4. The greedy heuristic in indirect search either harvests all eligible harvest-units in a period, or stops harvesting once the periodic volume target is reached. When there are no eligible harvest-units remaining at the end of a period, the swapping operation cannot prevent an eligible harvest-unit from being scheduled. Hence, it is not possible to move harvest-unit #4 from period 6 to period 9. It is possible to alter the indirect search algorithm so that it could, in its swapping operation, remove harvest-unit #4 from being scheduled in period 6. In fact, such an operation could be made conditional upon the parameter beta equalling alpha; i.e., when the number of eligible harvest-units in a period equals the number of units harvested. This possible alteration of the indirect search algorithm nevertheless fails to guarantee that all possible feasible solutions could be evaluated, given an unlimited number of iterations and loops. It might be that that this would require accepting inferior solutions. There is nothing in the indirect search algorithm to prevent it it from adopting 58 the strategies of simulated annealing or tabu search in this regard; but the search would undoubtedly be slower. Hence, indirect search does not satisfy the theoretical condition for convergence upon a global optimum. In practice, this may not matter, so long as the search is capable of finding better solutions than other methods. Rossier et al. (1986), for example, restricted their neighbourhood search in a travelling salesman problem by swapping only cities that were 'close' to one another. Their results suggest that, in the travelling salesman problem, restricted neighbourhoods yield best results even though the condition of reachability may have been violated. 5.4 D o m a i n Independence of Indirect Search The indirect search algorithm was designed to solve the spatial harvest-scheduling problem, but it is worth addressing the question of whether its general strategy, of iteratively permuting and improving the prioritised queue a greedy search, is applicable to other combinatorial problems. An obvious, but not necessarily correct, conclusion is that, wherever greedy searches are applicable, so too is indirect search, and that indirect search will improve upon the shortcomings of greedy search. This conclusion, of course, cannot be accepted, without empirical verification. Nonetheless, it can function as a working hypothesis for further research. A n example of this working hypothesis will now be applied to the travelling salesman problem. Conceptually, this is a very simple problem: the travelling salesman must visit every city in his territory exactly once, and then return home covering the shortest 59 distance. In the symmetric travelling salesman problem the distance between each pair of cities is the same, regardless of direction. The number of cities, n, determines the size of the solution space, n! / 2n. The most intuitive greedy algorithm for the travelling salesman problem is to start from a random city, proceed to the nearest unvisited city, and continue until every city has been visited once, at which time return to the first city. A demonstration of the applicability of the indirect search strategy to the travelling salesman problem will now be given. Figure 5.1 illustrates a sample of a symmetric travelling salesman problem with 4 cities. Figure 5.1: A sample travelling salesman problem with four cities For this problem, if the greedy algorithm for the travelling salesman problem were run four times, starting each time from a different city, then the 4 tours would turn out as illustrated in Table 5.1. 60 Table 5.1: Four tours producible by greedy algorithm S t a r t i n g P o i n t G r e e d y T o u r C o s t T o t a l C o s t A A-B-C-D-A 2+3+23+5 33 B B-A-C-D-B 3+2+5+23 36 C C-B-A-D-C 3+2+5+23 33 D D-A-B-C-D 5+2+3+23 33 There are 3 possible tours for a 4-city problem (i.e., 4! / (2 x 4) ), and the greedy algorithm can find only 2. The third tour is A-C-B-D-A , which costs only 4+3+7+5 =19, is the optimal tour. The question to pursue now is: whether an indirect search implementation of the symmetric travelling salesman problem can find this optimal tour. An indirect search algorithm for the travelling salesman problem could proceed as follows on a tour of n cities for x iterations: 1. For each city, form a prioritised queue of its closest cities, in descending order. 2. For x iterations, repeat steps 3 to 12. 3. Begin new tour by randomly selecting a city as a "switching city". 4. Visit the first city. The tour always starts at the same city. 5. If the number of cities visited is less than n, proceed to step 6, else proceed to step 10. 6. If this city does not equal the "switching city", proceed to step 7, else proceed to step 8. 7. Visit this city's highest ranked, eligible city on its prioritised queue. Return to step 5. 61 8. On the "switching city's" prioritised queue, swap the highest ranked eligible city with a randomly selected eligible city on its queue. 9. Visit the highest ranked, eligible city on the "switching city's" prioritised queue. Proceed to step 5. 10. Once the number of cities visited equals n, revisit the first city. 11. Calculate the total cost of the tour. If this is the lowest cost tour produced thus far, preserve the permutation made in step 8, otherwise undo it. 12. If the total number of iterations is less than x begin a new tour at step 3, preserving the present order of all prioritised queues. Figure 5.2 illustrates the application of this algorithm to the 4-city travelling salesman problem for two iterations. It demonstrates that the indirect search algorithm is capable of finding a shorter tour than the greedy algorithm. Further research is needed in order to evaluate the applicability of indirect search to other combinatorial optimization problems. 62 1) First iteration: Form initial prioritized queues. Calculate a greedy tour, starting at city A Initial Prioritzed Queues Start City Nearest Distance > A —*• B . * 2 4 III' D 5 2 T . .c 3 J -•* D 7 3 4 23 D <P A 5 B 7 C 23 Resulting greedy Tour, starting at A ABCDA Distance 2+3+23+5= 33 2) Second iteration: Permute a prioritized queue; i.e., randomly select a switching city A, and then randomly select an eligible city to switch with A's nearest city. E.g., switch B with C. Compute greedy tour. Start Prioritzed Queues after Permutation City Nearest Distance - > A - > C 4 • / B 2 « / D 5 2 3 7 c- 3 A 4 /..•* D 23 A 5 B 7 C 23 Resulting greedy Tour, starting at A ACBDA Distance 4+3+7+5= 19 Note on symbols: -*• represents algorithm referring to highest ranked, eligible city on its prioritized queue. represents algorithm selecting next city to visit, based on referral from prioritzed queue represents location of permutation Figure 5.2: Two iterations of indirect search applied to 4-city travelling salesman problem Chapter 6: Conclusions 6.1 S u m m a r y of Conclusions In the Introduction, it was stated that this study would seek to answer four questions. The first question was whether the indirect search algorithm can calculate solutions to the harvest-scheduling problem of a value comparable to other algorithms. Based on the comparison to Boston and Bettinger's (1999) work, the answer to this question is: yes. Of course, the question of whether the indirect search algorithm can consistently do so would require further comparisons Jthat are beyond the scope of this study. The second question was whether the computing time needed by indirect search is impracticably long for use on large problems. This question is more difficult to answer. On the one hand, it was observed that the computing time per iteration increases linearly as the problem size increases. On the other hand, it was also observed that excellent solutions can be calculated after relatively few iterations. Figures 4.1 and 4.2 illustrate that the indirect search algorithm begins the search with a good solution and that this can be quickly improved, and that thereafter, only minor increments in the solution value are made after many iterations. Analysts performing sensitivity analysis on large problems who choose to forego the many iterations that yield only minor gains in the solution value might therefore regard this as a practical algorithm for use on large problems. This is because the computing time required to improve the solution by a small amount may not 64 always be warranted. In the context of forest planning with uncertain variables, a small incremental increase in timber flow is usually regarded by decision-makers as something akin to a 'virtual harvest'. The third question aimed at identifying the causes of the relative efficiency of the indirect search strategy. In the Discussion, it was argued that its efficiency stems from three qualities: first, it is a search of multiple, intelligently restricted neighbourhoods; second, it can take immediate advantage of the effect(s) of removing from a schedule a harvest-unit which had been constraining other more valuable harvest-units; and finally, it can break out of local optima without resuming the search from inferior solutions. The final question was whether the general search strategy of indirect search might be applicable to other combinatorial optimisation problems. In the Discussion it was demonstrated that it can be applied to the travelling salesman problem and that it can improve upon the solution reached by a greedy algorithm alone. The question of its applicability to other combinatorial optimisation problems is beyond the scope of this study. 6.2 Suggestions for Fur ther Research The conclusions of this study warrant further research into the ability of indirect search to solve larger harvest-scheduling problems with more complex spatial constraints. Additional hard constraints in a problem would further reduce the size of 1 These comparisons would involve not only different data sets, but also different implementations o f simulated annealing and tabu search. 2 A s distinct from soft constraints, which are handled by penalty costs in the objective function. 65 the restricted neighbourhoods in an indirect search. This may improve the relative efficiency of this search method. Further research aimed at evaluating the relative efficiency of the indirect search strategy in its application to other combinatorial optimisation problems is also warranted by the conclusions of this study. 66 Literature Cited Arcus, A . L . 1966. COMSOAL: a computer method of sequencing operations for assembly lines. Int. J. Prod. Res. 4(4): 259-277. Banzhaf, W, Nordin, P., Keller, R., and Francone, F. 1998. Genetic Programming: An Introduction. Copublished by dpunkt.verlag and Morgan Kaufmann Publishers Inc. 470 p. Borges, J., Hoganson, H. , and Rose, D. 1998. Combining a decomposition strategy with dynamic programming to solve spatially constrained forest management scheduling problems. Forest Science 45(1):201-212. Boston, K . And Betinger, P. 1999. An analysis of Monte Carlo integer programming, simulated annealing, and tabu search heuristics for solving spatial harvest scheduling problems. Forest Science 45(2): 292-301. Brumelle, S., Granot, D., Halme, M . , and Vertinsky, I. 1998. A tabu search algorithm for finding a good forest harvest schedule satisfying green-up constraints. European Journal of Operational Research, 106:408-424. Budnick, F.S., Mojena, R., and Vollmann, T.E. 1977. Principles of Operations Research for Management. Richard D. Irwin, Inc. Homewood, Illinois. 756 p. Cawsey, Alison, 1998. The Essence of Artificial Intelligence. Prentice Hall, Toronto. 190 p. Conley, William, 1980. Computer Optimization Techniques. Petrocelli Books Inc., New York. 266 p. Dahlin, B. , and Salinas, O. 1993. Harvest Scheduling under Adjacency Constraints - A Case Study from the Swedish Sub-alpine Region. Scan. J. For. Res. 8:281-290. Davis, L.S., and Johnson, K . N . 1987. Forest Management: Third Edition. McGraw-Hill Inc., New York. 790 p. Dowsland, K . A . . 1993. Simulated Annealing. Pp. 21-69 in: Modern heurtistic techniques for combinatorial problems. C R . Reeves (Editor), Halsted Press, New York, 320 p. Glover, F. and Laguna, M . 1993. Tabu Search. Pp. 70-109. In Modern heuristic techniques for combinatorial problems. C R . Reeves (Editor), Halsted Press, New York, 320 p. 67 Golden, B.L. , and Alt, F.B. 1979. Interval estimation of a global optimum for large combinatorial problems. Nav. Res. Logist. 26:69-77. Goulding, C.J. 1995. Growth and yield models. In New Zealand Inst, of For. Handbook. Hammond, D. (ed.). New Zealandlnstitute of Forestry. Christchurch. 240 p. Hoganson, H .M. , and Borges, J.G. 1998. Using dynamic programming and overlapping subproblems to address adjacency in large harvest-scheduling problems. Forest Science 44:526-538. Johnson, K . N . , and Jones, D.B. 1979. A user's guide to multiple use sustained yield resource scheduling calculation (MUSYC). USDA Forest Service, Timber Management, Fort Collins, CO. 28 p. Johnson, K . N . , and Scheurmann, H.L. 1977. Techniques for prescribing optimal timber harvest and investment under different objectives- discussion synthesis. Forest Science Monograph 18. 21 p. Jones, J.G., Hyde, F . C , III, and Meecham, M . 1986. Four analytical approaches for integrating land management and transportation planning on forest lands. U S D A For. Serv. Res. Rep. INT-86. 26 p. Jones, J.G., Meneghin, B.J., and Kirby, M.W. 1991. Formulating adjacency constraints in linear optimization models for scheduling projects in tactical planning. For. Sci. 37:1283-1297. Kirby, M.W., Hager, W.A., and Wong, P. 1986. Simultaneous planning of wildland management and transportation alternatives. In Systems analysis in forestry and forest industries. Vol . 21. Edited by M . Kallio, A .E . Angersson, R. Seppala, and A . Morgan. North-Holland/TIMS Studies in Management Science. Elsevier Scientific Publishing Co., New York. pp. 371-387. Kirkpatrick, S., Gelatt, C D . , and Vecchi, M.P. 1983. Optimizationby simulated annealing. Science (Washington, D .C) , 220: 671-680. Liu, Guoliang, 1995. Natural Algorithms and Harvest Scheduling. M.F. Thesis, Faculty of Forestry, University of British Columbia, Vancouver. 65 p. Lockwood, C , and Moore, T. 1992. Harvest scheduling with spatial constraints: a simulated annealing approach. Can. J. For. Res. 23:468-478. Mealey, S.P., Liscomb, J.F., and Johnson, K . N . 1982. Solving the habitat dispersion problem in forest planning. In Transactions of the 47 t h North American Wildlife and Natural Resources Conference, Portland, OR, 26-31 March 1982. Edited by K. Sabol. Wildlife Management Institute, Washington, DC. pp. 142-153. 68 Meneghin, B.J., Kirby, M.W., and Jones, J.G. 1988. A n algorithm for writing adjacency constraints efficiently in linear programming models. In The 1988 Symposium on Systems Analysis in Forest Resources, Asilomar, CA, March 29 - April 1, 1988. USDA For. Serv. Gen. Tech. Rep. RM-161. pp. 46-53. Metropolis, N . , Rosenbluth, A.W., Rosenbluth, M.N . , and Teller, A . H . 1953. Equation of state calculations by fast computing machines, J. Chem. Phys. 21: 1087-1092. Michalewicz, Z., and Fogel, D.B. 2000. How to Solve It: Modern Heuristics. Springer-Verlag. New York 467 p. Murray, A.T., and Church, R.L., 1993. Heuristic solution approaches to operational forest planning problems. Published in 1995 in OR Spektrum 17:193-203. Murray, A.T., and Church, R.L. 1996. Analyzing Cliques for Imposing Adjacency Restrictions in Forest Models, Forest Science 42(2)715-724. Navon, D. 1971. Timber R A M . USDA For. Serv. Res. Pap. PSW-70. 48 p. Nelson, J., Brodie, J.D., and Sessions, J. 1988. Integrating short-term spatially feasible harvest plans with long-term harvest scheduled using Monte-Carlo integer programming and linear programming. In The 1988 Symposium on Systems Analysis in Forest Resources, March 29 to April 1. Technical coordinators: B . M . Kent and L.S. Davis. USDA For. Serv. Rocky Mt. For. Range Exp. Stn. Gen. Tech. Rep. RM-161. 13 p. Nelson, J., and Brodie, J.D. 1990. Comparison of a random search algorithm and mixed interger programming for solving area-based forest plans. Can. J. For. Res. 20:934-942. Nelson, J., Gizowski, D., and Shannon, T. 1996. A User's Manual for A T L A S V2.88a Windows Edition. Forest Operations Group, Faculty of Forestry, University of British Columbia, Vancouver. 32 p. Nelson, J., and Gizowski, D. 1999. A User's Manual Forest Planning Studio. Forest Operations Group, Faculty of Forestry, University of British Columbia, Vancouver. 54 p. O' Hara, A.J. , Faaland B.H. , and Bare, B.B. 1989. Spatially constrained timber harvest scheduling. Can J. For. Res. 19: 715 - 724. Reeves, C.R.. 1993. Genetic algorithms. Pp. 151-196 in: Modern heurtistic techniques for combinatorial problems. C R . Reeves (Editor), Halsted Press, New York, 320 P-69 Reeves, C.R., and Beasely, J.E. 1993. Introduction. Pp. 1-19 In Modern heuristic techniques for combinatorial problems. C R . Reeves (Editor), Halsted Press, New York, 320 p. Rossier, Y. , Troyon M . , and Liebling, T .M. 1986. Probabilistic exchange algorithms and euclidean travelling salesman problems. OR Spektrum, 8, 151-164. Sessions, J., and Sessions, J. 1988. Scheduling and network analysis program (SNAP): user's guide. Department of Forest Management, Oregon State University, Corvallis. 38 p. Stuart, T.W., and Johnson, K . N . 1985. F O R P L A N version II: a tool for forest management planning. Paper presented at the Joint National Meeting of the Institute of Management Sciences and the Operations Research Society of America, Boston, M . A . April 29 - May 1. 96 p. Thompson, E.F., Halterman, B.G., Lyons, T.S., and Miller, R.L. 1973. Integrating timber and wildfire management planning For. Chron. 49: 247-250. Torres-Rojo, J .M., and Brodie, J.D. 1990. Adjacency constraints in harvest scheduling: an aggregation heuristic. Can. J. For. Res. 20: 978-986. Ware, G.O., and Clutter, J.L. 1971. A mathematical programming system for management of industrial forests. For. Sci. 17: 428-445. Weintraub, A. , Epstein, R., and Barahona, F. 1988. Integrating the habitat dispersion problem with timber management planning. Mimeograph report. Industrial Engineering Department, University of Chile, Santiago. 15 p. Weintraub, A. , Jones, G., Meacham, M . , Magendzo, A. , and Malchuk, D. 1995. Heuristic procedures for solving mixed-integer harvest scheduling-transportation planning models. Can. J. For. Res. 25: 1618-1626. Yoshimoto, A. , and Brodie, J.D. 1994. Comparative analysis of algorithms to generate adjacency constraints. Can. J. For. Res. 24: 1277-1288. 70
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- An indirect search algorithm for solving the spatial...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
An indirect search algorithm for solving the spatial harvest-scheduling problem Crowe, Kevin Andrew 2000
pdf
Page Metadata
Item Metadata
Title | An indirect search algorithm for solving the spatial harvest-scheduling problem |
Creator |
Crowe, Kevin Andrew |
Date Issued | 2000 |
Description | The objective of this research was to develop, evaluate, and understand a new heuristic algorithm for solving the spatial harvest-scheduling problem. The new algorithm, indirect search, is a combination of a greedy heuristic and a neighborhood search. It was developed with the intention of quickly computing near-optimal solutions to large harvest-scheduling problems where harvest activities are treated as 0-1 variables. For this study, the algorithm solved two harvest-scheduling problems constrained by even-flow and two-period adjacency constraints: 1) a set of small tactical problems comprising 625 harvest-units scheduled over ten one-year periods; and 2) a strategic planning problem comprising 3,857 harvest-units scheduled over twenty ten-year periods. Excellent solutions to the tactical problem took 2 minutes and 42 seconds to compute and were superior to those calculated by implementations of a tabu search and a simulated annealing algorithm. The solution to the strategic problem was computed in 63 minutes and scheduled 86.9% of a linear programming model's total volume. The nature of the efficiency of this algorithm is discussed in some detail and it is also shown that the general strategy of indirect search can be applied to other combinatorial optimization problems. The indirect search algorithm performed well on the models tested thus far. These results warrant further research on: 1) applying indirect search to harvest-scheduling problems with more complex forms of spatial constraints; and 2) evaluating the efficiency of the indirect search strategy in its application to other combinatorial optimization problems. |
Extent | 6402052 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-07-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0089715 |
URI | http://hdl.handle.net/2429/10579 |
Degree |
Master of Forestry - MF |
Program |
Forestry |
Affiliation |
Forestry, Faculty of |
Degree Grantor | University of British Columbia |
GraduationDate | 2000-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2000-0376.pdf [ 6.11MB ]
- Metadata
- JSON: 831-1.0089715.json
- JSON-LD: 831-1.0089715-ld.json
- RDF/XML (Pretty): 831-1.0089715-rdf.xml
- RDF/JSON: 831-1.0089715-rdf.json
- Turtle: 831-1.0089715-turtle.txt
- N-Triples: 831-1.0089715-rdf-ntriples.txt
- Original Record: 831-1.0089715-source.json
- Full Text
- 831-1.0089715-fulltext.txt
- Citation
- 831-1.0089715.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0089715/manifest