Combining Tabu Search and Genetic Algorithm Heuristic Techniques to Solve Spatial Harvest Scheduling Problems
Abstract:The performance of two new heuristics that combine tabu search with a genetic crossover technique was examined for their usefulness in solving spatially constrained harvest scheduling problems. One heuristic utilized tabu search with 1-opt moves and a genetic crossover technique (TS/GA), and the other utilized tabu search with both 1-opt and 2-opt moves and a genetic crossover technique (TS2/GA). The heuristics were tested on four problems. Three problems used the simple unit-restriction model (URM) to portray greenup constraints, allowing them to be solved with mathematical programming techniques and thus providing a benchmark to compare against the solutions produced by the heuristic techniques. These were considered hypothetical problems, since the datasets were grids, and the age classes were assigned with three different rules. The fourth problem uses an operational dataset and includes both a maximum opening size constraint, which limits the size of an individual opening, and a maximum average opening size constraint, which represents the greenup constraint contained in the American Forest and Paper Association (AF&PA) Sustainable Forestry Initiative (AF&PA 2000). The greenup constraints contained in these problems accurately portray the greenup constraints facing the forest industry in the United States. For the three hypothetical problems, the TS/GA technique found solutions with an objective function value between 96.6% and 99.1% of an estimated optimal value, and between 93.4% to 94.4% of a relaxed linear programming value. The TS2/GA found better solutions for all three hypothetical problems, with the objective function values between 98.2% and 99.7% of the estimated optimal value and the 96.3% to 97.2% of the relaxed linear programming value. Compared with a general tabu search technique that used 1-opt moves (TS), adding the genetic crossover technique resulted in a 2% increase in the objective function value, and adding the 2-opt intensification capability resulted in a further 1.5% improvement. A similar pattern was observed when the problem using the operational dataset was solved. The addition of the genetic crossover technique did not increase the time required to produce a solution to any particular problem, yet the addition of the 2-opt procedure did. TS2/GA required about twice as much time as did TS or TS/GA when applied to the three hypothetical datasets, and 67% more time when applied to the problem using the operational dataset. FOR. SCI. 48(1):35–46.
Keywords: Harvest scheduling; environmental management; forest; forest management; forest resources; forestry; forestry research; forestry science; genetic algorithms; natural resource management; natural resources; spatially constrained scheduling problems; tabu search
Document Type: Miscellaneous
Affiliations: 1: Carter Holt Harvey Fibre Solutions, Grayburn House, Leith Place, Tokoroa, New Zealand, Phone: 64-7-886-2760 Kevin.Boston@chh.co.nz 2: Department of Forest Resources, Oregon State University, Corvallis, OR, 97331, Phone: (541) 737-8549 Pete.Bettinger@orst.edu
Publication date: February 1, 2002
- Forest Science is a peer-reviewed journal publishing fundamental and applied research that explores all aspects of natural and social sciences as they apply to the function and management of the forested ecosystems of the world. Topics include silviculture, forest management, biometrics, economics, entomology & pathology, fire & fuels management, forest ecology, genetics & tree improvement, geospatial technologies, harvesting & utilization, landscape ecology, operations research, forest policy, physiology, recreation, social sciences, soils & hydrology, and wildlife management.
Forest Science is published bimonthly in February, April, June, August, October, and December.
Also published by SAF:
Journal of Forestry
Other SAF Publications
- Submit a Paper
- Membership Information
- Author Guidelines
- Ingenta Connect is not responsible for the content or availability of external websites