Efficient neighborhood evaluation for the maximally diverse grouping problem

Schulz, Arne

doi:10.1007/s10479-024-06217-9

Efficient neighborhood evaluation for the maximally diverse grouping problem

Publication date

2024-08-21

Document type

Forschungsartikel

Author

Schulz, Arne

Organisational unit

Betriebswirtschaftslehre, insb. Service Operations

DOI

10.1007/s10479-024-06217-9

URI

https://openhsu.ub.hsu-hh.de/handle/10.24405/22199

Scopus ID

2-s2.0-85201678195

Publisher

Springer Science and Business Media

Series or journal

Annals of Operations Research

ISSN

0254-5330

Periodical volume

341

Periodical issue

2-3

First page

1247

Last page

1265

Peer-reviewed

✅

Part of the university bibliography

✅

Language

English

Keyword

Combinatorial optimization

Computational efficiency

Grouping

Local search

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.

Description

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Version

Published version

Access right on openHSU

Metadata only access

Open Access Funding

Springer Nature (DEAL)