Skip to main content
Kent Academic Repository

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 this file
[thumbnail of The whole  Thesis (Abdalla Elshaikh).pdf]


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: Organisations -1 not found.
Depositing User: Users 1 not found.
Date Deposited: 11 Mar 2015 01:00 UTC
Last Modified: 10 Dec 2022 03:04 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

Elshaikh, Abdalla Mohamed.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.