NEW HEURISTIC ALGORITHMS FOR THE RECTANGULAR P-COVER PROBLEM

Many heuristic algorithms have been proposed in the literature for the solution of p-center problems, most of which can be used in any metric space. However, little computational experience has been reported with these heuristics, most times for problems in R(2) with the Euclidean distance. In this paper, we consider the unweighted p-center problem in R(m) when distance is measured by the Tchebycheff norm, which we name the Rectangular p-Cover Problem. We propose new heuristic algorithms for this problem, and present computational results. Firstly a new class of heuristics based on the generation of seed seed points is given, which is obtained using a new assignment rule. Secondly, two new algorithms based on partitions are given, which can be seen as heuristics of improvement type. Finally, it is shown by computational experiments that the new algorithms improve some other related heuristics considered in this paper.