TY - THES
AU - Crowe, Kevin Andrew
PY - 2000
TI - An indirect search algorithm for solving the spatial harvest-scheduling problem
KW - Thesis/Dissertation
LA - eng
M3 - Text
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/831/items/1.0089715
ER - End of Reference