Skip to main content

An Adaptive Perturbation-Based Heuristic: An Application to the Continuous p-Centre Problem

Elshaikh, Abdella, Salhi, Said, Brimberg, Jack, Mladenovic, Nenad, Callaghan, Becky, Nagy, Gábor (2016) An Adaptive Perturbation-Based Heuristic: An Application to the Continuous p-Centre Problem. Computers and Operations Research, 75 . pp. 1-11. ISSN 0305-0548. (doi:10.1016/j.cor.2016.04.018) (KAR id:55688)

PDF Author's Accepted Manuscript
Language: English


Creative Commons Licence
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Download (574kB) Preview
[img]
Preview
PDF (pdf) Author's Accepted Manuscript
Language: English

Restricted to Repository staff only
Contact us about this Publication
[img]
Official URL
http://www.dx.doi.org/10.1016/j.cor.2016.04.018

Abstract

A self-adaptive heuristic that incorporates a variable level of perturbation, a novel local search and a learning mechanism is proposed to solve the p-centre problem in the continuous space. Empirical results, using several large TSP-Lib data sets, some with over 1300 customers with various values of p, show that our proposed heuristic is both effective and efficient. This perturbation metaheuristic compares favourably against the optimal method on small size instances. For larger instances the algorithm outperforms both a multi-start heuristic and a discrete-based optimal approach while performing well against a recent powerful VNS approach. This is a self-adaptive method that can easily be adopted to tackle other combinatorial/global optimisation problems. For benchmarking purposes, the medium size instances with nodes are solved optimally for the first time, though requiring a large amount of computational time. As a by-product of this research, we also report for the first time the optimal solution of the vertex p-centre problem for these TSP-Lib data sets.

Item Type: Article
DOI/Identification number: 10.1016/j.cor.2016.04.018
Uncontrolled keywords: p-centre problem, continuous space, perturbation search, adaptive search, large instances, optimal solutions
Subjects: H Social Sciences > H Social Sciences (General)
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: 25 May 2016 09:14 UTC
Last Modified: 08 Feb 2020 04:08 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/55688 (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