Open Collections

An indirect search algorithm for solving the spatial harvest-scheduling problem

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2009-07-10

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.

http://hdl.handle.net/2429/10579

Forestry

University of British Columbia

UBCV

DSpace