Dispersion Problem Under Capacity and Cost Constraints: Multiple Neighborhood Tabu Search

Abstract

Diversity and dispersion problems consists of selecting a subset of elements from a given set so that their diversity is maximized. The one of most recently proposed variant is the MaxMin dispersion problem with capacity and cost constraints. This variant usually called the generalized dispersion problem. In this paper we propose variant of tabu search based on multiple neighborhoods to solve large-size instances. Extensive numerical computational experiments are performed to compare our tabu search metaheuristic with the state-of-art heuristic. Results on public benchmark instances show the superiority of our proposal with respect to the previous algorithms.