An adaptive perturbation-based heuristic: An application to the continuous p-centre problem ☆

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 575 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.