A COMPARISON OF P-DISPERSION HEURISTICS

被引：44

作者：

ERKUT, E ^{[1
]}

ULKUSAL, Y ^{[1
]}

YENICERIOGLU, O ^{[1
]}

机构：

[1] BOGAZICI UNIV,DEPT IND ENGN,ISTANBUL 80815,TURKEY

来源：

COMPUTERS & OPERATIONS RESEARCH | 1994年 / 21卷 / 10期

关键词：

D O I：

10.1016/0305-0548(94)90041-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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

引用

页码：1103 / 1113

页数：11

共 15 条

[1] HEURISTICS BASED ON SPACEFILLING CURVES FOR COMBINATORIAL PROBLEMS IN EUCLIDEAN-SPACE [J].