Max–min dispersion with capacity and cost for a practical location problem. (15th August 2022)

• Record Type: Journal Article
• Authors: Lozano-Osorio, Isaac; Martínez-Gavara, Anna; Martí, Rafael; Duarte, Abraham
• Is Part Of: Expert systems with applications. Volume 200(2022)
• Publication Date: 2022-08-15
• Subjects: Metaheuristics -- Combinatorial optimization -- Diversity maximization -- Dispersion -- Variable neighborhood search; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2022.116899
• Languages: English
• ISSNs: 0957-4174

Abstract

Abstract: Diversity and dispersion problems deal with selecting a subset of elements from a given set in such a way that their diversity is maximized. This study considers a practical location problem recently proposed in the context of max–min dispersion models. It is called the generalized dispersion problem, and it models realistic applications by introducing capacity and cost constraints. We propose two effective linear formulations for this problem, and develop a hybrid metaheuristic algorithm based on the variable neighborhood search methodology, to solve real instances. Extensive numerical computational experiments are performed to compare our hybrid metaheuristic with the state-of-art heuristic, and with integer linear programming formulations (ILP). Results on public benchmark instances show the superiority of our proposal with respect to the previous algorithms. Our extensive experimentation reveals that ILP models are able to optimally solve medium-size instances with the Gurobi optimizer, although metaheuristics outperform ILP both in running time and quality in large-size instances. Highlights: Resolution of an optimization model with applications on capacity location problems. An effective formulation is applied to solve medium-size instances to optimality. A variable neighborhood search is proposed by combining three different operators. Study efficient search strategies. Numerical and statistical analysis are performed to disclose the best strategies.