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, mast 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 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.%Beaucoup d'algorithmes heuristiques ont été proposés en littérature pour la solution du problème p-centre, la plupart d'eux peut être utilisée dans n'importe quel espace métrique. Du fait, peu d'expériences de computation ont été élaborées avec ces heuristiques, la plupart du temps en R~2 avec la distance Euclidienne. Dans cet article, on considère les problèmes dans R~m du p-centre sans poids quand la distance mesurée par la norme de Tchebycheff, qui s'appelle le Problème dep-Couvrement Rectangulaire. On suppose de nouveaux algorithmes heuristiques pour ce problème, et on présente des résultats de computation. Premièrement, une nouvelle classe d'heuristiques basées sur l'engendrement des points de semence donné, qui est obtenue m utilisant une nouvelle règle d'allocation. Deuxièmement, deux nouveaux algorithmes basés dans la répartition sont donnés, lesquels peuvent être vus comme une amélioration des heuristiques. Finalement, on montre par expérience de computation que les nouveaux algorithmes améliorent certaines heuristiques considérées dans cet article.