UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

An indirect search algorithm for solving the spatial harvest-scheduling problem Crowe, Kevin Andrew

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.

Item Media

Item Citations and Data

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.

Usage Statistics