Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 72, Issue -, Pages 118-127Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2016.02.016
Keywords
Dispersion problem; Tabu search; Memetic algorithm; Heuristics
Categories
Funding
- Region of Pays de la Loire (France)
- PGMO project (Jacques Hadamard Mathematical Foundation, Paris)
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available