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

Xiangjing Lai, Jin-Kao Hao, Zhang-Hua Fu and Dong Yue

European Journal of Operational Research, 2021, vol. 289, issue 3, 1067-1086

Abstract: 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.

Keywords: Heuristics; grouping and clustering; neighborhood decomposition; local search (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720306743
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:3:p:1067-1086

DOI: 10.1016/j.ejor.2020.07.048

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().