The objective of the p-dispersion problem is to choose p out of n given points, such that the minimum distance between any pair of chosen points is as large as possible. Possible application areas include location theory and multicriteria optimization. The p-dispersion problem is known to be NP-hard. In this paper, the authors examine 10 heuristic methods for solving this problem, and provide a comparison of them based on several criteria. They report the present computational experience with the heuristics on randomly generated planar problems of different sizes. Most of the heuristics generate very good solutions with very little computational effort on a microcomputer. The authors suggest performing multiple applications of several heuristics to minimize the possibility of finding poor solutions.
