- 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
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 Metadata
Title |
An indirect search algorithm for solving the spatial harvest-scheduling problem
|
Creator | |
Publisher |
University of British Columbia
|
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 | |
Type | |
File Format |
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 | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2000-11
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
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.