期刊
COMPUTERS & OPERATIONS RESEARCH
卷 72, 期 -, 页码 118-127出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2016.02.016
关键词
Dispersion problem; Tabu search; Memetic algorithm; Heuristics
类别
资金
- Region of Pays de la Loire (France)
- PGMO project (Jacques Hadamard Mathematical Foundation, Paris)
Given a set V of n elements and a distance matrix [d(ij)](nxn) among elements, the max-mean dispersion problem (MaxMeanDP) consists in selecting a subset M from V such that the mean dispersion (or distance) among the selected elements is maximized. Being a useful model to formulate several relevant applications, MaxMeanDP is known to be NP-hard and thus computationally difficult. In this paper, we present a tabu search based memetic algorithm for MaxMeanDP Which relies on solution recombination and local optimization to find high quality solutions. One key contribution is the identification of the fast neighborhood induced by the one-flip operator which takes linear time. Computational experiments on the set of 160 benchmark instances with up to 1000 elements commonly used in the literature show that the proposed algorithm improves or matches the published best known results for all instances in a short computing time, with only one exception, while achieving a high success rate of 100%. In particular, we improve 53 previous best results (new lower bounds) out of the 60 most challenging instances. Results on a set of 40 new large instances with 3000 and 5000 elements are also presented. The key ingredients of the proposed algorithm are investigated to shed light on how they affect the performance of the algorithm. (C) 2016 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据