Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping
Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping
复制标题
基于邻域分解的变量邻域搜索和最大多样化分组的禁忌搜索
DOI：
10.1016/j.ejor.2020.07.048
复制
发表时间：
2021-03-16
影响因子：
6.4
通讯作者：
Yue, Dong
中科院分区：
文献类型：
--
作者：
Lai, Xiangjing;Hao, Jin-Kao;Yue, Dong
最大化的分组问题（MDGP）是许多现实世界应用程序的相关NP-HARD优化问题。但是，解决问题的大规模实例在计算上具有挑战性。这项工作致力于解决该问题的新启发式算法，该算法以两个原始功能为由。首先，它引入了第一个加速邻里检查的邻里分解策略。其次，它以概率的方式整合了两个基于互补的邻里分解的本地搜索程序（可变的邻域下降和禁忌搜索），以及一种自适应扰动策略，以确保在搜索空间的强化和多元化之间保持适当的平衡。文献中常用的320个基准实例的计算结果表明，提出的算法与最新的MDGP算法相比，通过报告了220个大实例的文献中最著名的结果（新的下限），通过报告了最新的最著名结果（新的下限）。进行了其他实验以分析算法的主要组成部分。所提出的算法可以帮助更好地解决最大不同分组模型可以提出的实用问题。 （c）2020 Elsevier B.V.保留所有权利。
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. (C) 2020 Elsevier B.V. All rights reserved.