Abstract

This thesis is a critical investigation into the development, application and evaluation
of ant colony optimisation metaheuristics, with a view to solving a class of
capacitated facility location problems. The study is comprised of three phases.
The first sets the scene and motivation for research, which includes; key concepts
of ant colony optimisation, a review of published academic materials and a
research philosophy which provides a justification for a deductive empirical mode
of study. This phase reveals that published results for existing facility location
metaheuristics are often ambiguous or incomplete and there is no clear evidence
of a dominant method. This clearly represents a gap in the current knowledge
base and provides a rationale for a study that will contribute to existing knowledge,
by determining if ant colony optimisation is a suitable solution technique for
solving capacitated facility location problems.
The second phase is concerned with the research, development and application
of a variety of ant colony optimisation algorithms. Solution methods presented
include combinations of approximate and exact techniques. The study
identifies a previously untried ant hybrid scheme, which incorporates an exact
method within it, as the most promising of techniques that were tested. Also a
novel local search initialisation which relies on memory is presented. These hybridisations
successfully solve all of the capacitated facility location test problems
available in the OR-Library.
The third phase of this study conducts an extensive series of run-time analyses,
to determine the prowess of the derived ant colony optimisation algorithms
against a contemporary cross-entropy technique. This type of analysis for measuring
metaheuristic performance for the capacitated facility location problem is
not evident within published materials. Analyses of empirical run-time distributions
reveal that ant colony optimisation is superior to its contemporary opponent.
All three phases of this thesis provide their own individual contributions to existing
knowledge bases: the production of a series of run-time distributions will be
a valuable resource for future researchers; results demonstrate that hybridisation
of metaheuristics with exact solution methods is an area not to be ignored; the
hybrid methods employed in this study ten years ago would have been impractical
or infeasible; ant colony optimisation is shown to be a very flexible metaheuristic
that can easily be adapted to solving mixed integer problems using hybridisation
techniques.