Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping

The maximally diverse grouping problem (MDGP) is a relevant NP-hard optimization problem with a number of real-world applications. However, solving large instances of the problem is computationally challenging. This work is dedicated to a new heuristic algorithm for the problem, which distinguishes itself by two original features. First, it introduces the first neighborhood decomposition strategy to accelerate neighborhood examinations. Second, it integrates, in a probabilistic way, two complementary neighborhood decomposition based local search procedures (variable neighborhood descent and tabu search) as well as an adaptive perturbation strategy to ensure a suitable balance between intensification and diversification of the search space. Computational results on 320 benchmark instances commonly used in the literature show that the proposed algorithm competes favorably with the state-of-the-art MDGP algorithms, by reporting improved best-known results (new lower bounds) of the literature for 220 large instances. Additional experiments are conducted to analyze the main components of the algorithm. The proposed algorithm can help to better solve practical problems that can be formulated by the maximally diverse grouping model.