Efficient neighborhood evaluation for the maximally diverse grouping problem
针对最大化多样性分组问题，提出一种新的高效邻域实现方法，相比标准方法和邻域分解方法，在较大实例上可多进行最多160%的迭代，适用于其他分组或聚类问题的元启发式算法。
Abstract The Maximally Diverse Grouping Problem is one of the well-known combinatorial optimization problems with applications in the assignment of students to groups or courses. Due to its NP-hardness several (meta)heuristic solution approaches have been presented in the literature. Most of them include the insertion of an item of one group into another group and the swap of two items currently assigned to different groups as neighborhoods. The paper presents a new efficient implementation for both neighborhoods and compares it with the standard implementation, in which all inserts/swaps are evaluated, as well as the neighborhood decomposition approach. The results show that the newly presented approach is clearly superior for larger instances allowing for up to 160% more iterations in comparison to the standard implementation and up to 76% more iterations in comparison to the neighborhood decomposition approach. Moreover, the results can also be used for (meta)heuristic algorithms for other grouping or clustering problems.