Adaptive Heuristic Methods for the Continuous p-Centre Location Problems

Elshaikh, Abdalla Mohamed (2014) Adaptive Heuristic Methods for the Continuous p-Centre Location Problems. Doctor of Philosophy (PhD) thesis, University of Kent,. (Full text available)

PDF
Download (3MB) Preview
[img]
Preview

Abstract

This research studies the p-centre problem in the continuous space. This problem is particularly useful in locating emergency facilities, such as fire-fighting stations, police stations and hospitals where it is aimed to minimise the worst-case response time. This problem can be divided into a single facility minmax location problem (1-centre) and multi-facility minmax location problem (p-centre). The solution of the 1-centre location problem can be found optimally in polynomial time by using the well known Elzinga-Hearn algorithm for both the weighted and the unweighted case. The objective of the p-centre problem is to locate p facilities (p>1) so as to minimise the radius of the largest circle. However, in this case, we cannot always guarantee optimality as the problem is known to be NP hard. The aim of the research is to develop and analyse powerful meta-heuristics including the hybridisation of exact methods and heuristics to solve this global optimisation problem. To our knowledge this is the first study that meta-heuristics are developed for this problem. In addition larger instances previously used in the literature are tested .This is achieved by designing an efficient variable neighbourhood search, adapting a powerful perturbation method and extending a newly developed reformulation local search. Large instances are used to evaluate our approaches with promising results.

Item Type: Thesis (Doctor of Philosophy (PhD))
Uncontrolled keywords: continuous location, VNS, perturbation, RLS, large instances
Subjects: H Social Sciences > HF Commerce
H Social Sciences > HF Commerce > HF5351 Business
Divisions: Faculties > Social Sciences > Kent Business School
Depositing User: Users 1 not found.
Date Deposited: 11 Mar 2015 01:00 UTC
Last Modified: 01 Jun 2017 23:00 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/47618 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year