A comparison of p-dispersion heuristics
A comparison of p-dispersion heuristics
复制标题
DOI：
10.1016/0305-0548(94)90041-8
复制
发表时间：
1994-12
期刊：
影响因子：
--
通讯作者：
E. Erkut;Y. Ülküsal;Oktay Yeniçerioglu
中科院分区：
文献类型：
--
作者：
E. Erkut;Y. Ülküsal;Oktay Yeniçerioglu
P-离散度问题的目标是从给定的点中选择一个点，使得任何一对所选点之间的最小距离尽可能大。可能的应用领域包括选址理论和多目标优化。P-色散问题是已知的NP-难问题。在本文中，我们考察了解决该问题的10种启发式方法，并基于几个标准对它们进行了比较。我们报告了我们在不同大小的随机生成的平面问题上使用启发式算法的计算经验。大多数启发式算法在微型计算机上只需很少的计算工作就能产生非常好的解。我们建议执行多个启发式方法的多次应用，以最大限度地减少找到糟糕解决方案的可能性。
The objective of thep-dispersion problem is to choosepout ofngiven 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. Thep-dispersion problem is known to be NP-hard. In this paper, we examine 10 heuristic methods for solving this problem, and provide a comparison of them based on several criteria. We report our 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. We suggest performing multiple applications of several heuristics to minimize the possibility of finding poor solutions.