Skip to main content

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,. (KAR id:47618)

Language: English
Download (3MB) Preview
[thumbnail of The whole  Thesis (Abdalla Elshaikh).pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format


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))
Thesis advisor: Salhi, Said
Thesis advisor: Nagy, Gabor
Uncontrolled keywords: continuous location, VNS, perturbation, RLS, large instances
Subjects: H Social Sciences > HF Commerce
H Social Sciences > HF Commerce > HF5351 Business
Divisions: Divisions > Kent Business School - Division > Kent Business School (do not use)
Funders: [UNSPECIFIED] Libyan Government
Depositing User: Users 1 not found.
Date Deposited: 11 Mar 2015 01:00 UTC
Last Modified: 16 Feb 2021 13:23 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year