Skip to main content

The continuous p-centre problem: An investigation into variable neighbourhood search with memory

Elshaikh, Abdalla, Salhi, Said, Nagy, Gábor (2015) The continuous p-centre problem: An investigation into variable neighbourhood search with memory. European Journal of Operational Research, 241 . pp. 606-621. ISSN 0377-2217. (doi:10.1016/j.ejor.2014.10.006) (KAR id:47096)

Abstract

A VNS-based heuristic using both a facility as well as a customer type neighbourhood structure is proposed to solve the p-centre problem in the continuous space. Simple but effective enhancements to the original Elzinga-Hearn algorithm as well as a powerful ‘locate-allocate’ local search used within VNS are proposed. In addition, efficient implementations in both neighbourhood structures are presented. A learning scheme is also embedded into the search to produce a new variant of VNS that uses memory. The effect of incorporating strong intensification within the local search via a VND type structure is also explored with interesting results. Empirical results, based on several existing data set (TSP-Lib) with various values of p, show that the proposed VNS implementations outperform both a multi-start heuristic and the discrete-based optimal approach that use the same local search.

Item Type: Article
DOI/Identification number: 10.1016/j.ejor.2014.10.006
Uncontrolled keywords: p-centre problem, continuous space, variable neighbourhood search with memory, adaptive search, Elzinga-Hearn algorithm
Subjects: H Social Sciences > HA Statistics > HA33 Management Science
Divisions: Faculties > Social Sciences > Kent Business School > Management Science
Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User: Said Salhi
Date Deposited: 11 Feb 2015 09:15 UTC
Last Modified: 08 Feb 2020 04:06 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/47096 (The current URI for this page, for reference purposes)
Salhi, Said: https://orcid.org/0000-0002-3384-5240
Nagy, Gábor: https://orcid.org/0000-0002-7609-5718
  • Depositors only (login required):

Downloads

Downloads per month over past year