Heuristics for the capacitated dispersion problem. (9th April 2020)

• Record Type: Journal Article
• Authors: Peiró, Juanjo; Jiménez, Iris; Laguardia, José; Martí, Rafael
• Is Part Of: International transactions in operational research. Volume 28:Number 1(2021)
• Page Start: 119
• Page End: 141
• Publication Date: 2020-04-09
• Subjects: diversity maximization -- dispersion -- metaheuristics -- combinatorial optimization; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12799
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: In this paper, we investigate the adaptation of the greedy randomized adaptive search procedure (GRASP) and variable neighborhood descent (VND) methodologies to the capacitated dispersion problem. Dispersion and diversity problems arise in the placement of undesirable facilities, workforce management, and social media, among others. Maximizing diversity deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. We target here a realistic variant with capacity constraints for which a heuristic with a performance guarantee was previously introduced. In particular, we propose a hybridization of GRASP and VND implementing within the strategic oscillation framework. To evaluate the performance of our heuristic, we perform extensive experimentation to first set key search parameters, and then compare the final method with the previous heuristic. Additionally, we propose a mathematical model to obtain optimal solutions for small‐sized instances, and compare our solutions with the well‐known LocalSolver software.