Ant Colony Optimisation – A Proposed Solution Framework for the Capacitated Facility Location Problem

Venables, Harry (2011) Ant Colony Optimisation – A Proposed Solution Framework for the Capacitated Facility Location Problem. Doctoral thesis, University of Sunderland.

[img]
Preview
PDF
HarryVenablesPhDThesisJune2011.pdf - Accepted Version

Download (6MB)

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.

Item Type: Thesis (Doctoral)
Subjects: Business and Management > Business
Computing > Information Systems
Divisions: Collections > Theses
Depositing User: Barry Hall
Date Deposited: 21 Aug 2013 14:01
Last Modified: 07 Mar 2017 17:37
URI: http://sure.sunderland.ac.uk/id/eprint/4061

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year