.png){kind=icon}
.png){kind=icon}
Return
The capacitated dispersion problem: an optimization model and a memetic algorithm
.png){kind=icon}
PRE
AI
DOI：10.1007/s12293-020-00318-1.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The challenge of maximizing the diversity of a collection of points arises in a variety of settings, and the growing interest of dealing with diversity resulted in an effort to study these problems in the last few years. Generally speaking, maximizing diversity consists in selecting a subset of points from a given set in such a way that a measure of their diversity is maximized. Different objective functions have been proposed to capture the notion of diversity, being the sum and the minimum of the distances between the selected points the most widely used. However, in all these models, the number of points to be selected is established beforehand, which in some settings can be unrealistic. In this paper, we target a variant recently introduced in which the model includes capacity values, which reflects the real situation in many location problems. We propose a mathematical model and a heuristic based on the Scatter Search methodology to maximize the diversity while satisfying the capacity constraint. Scatter search is a memetic algorithm hybridizing evolutionary global search with a problem-specific local search. Our empirical analysis with previously reported instances shows that the mathematical model implemented in Gurobi solves to optimality many more instances than the previous published model, and the heuristic outperforms a very recent development based on GRASP. We present a statistical analysis that permits us to draw significant conclusions.
Keywords:
Maximum diversity
Metaheuristics
Mathematical formulations
Empirical comparison
Journal
IF:
2.3
Papers:
447
Citations:
718