A matheuristic for large-scale capacitated clustering

Gnägi, Mario; Baumann, Philipp (2021). A matheuristic for large-scale capacitated clustering. Computers & operations research, 132, p. 105304. Elsevier 10.1016/j.cor.2021.105304

[img]
Preview
Text
A_Matheuristic_for_large-scale_capacitated_clustering.pdf - Published Version
Available under License Creative Commons: Attribution (CC-BY).

Download (1MB) | Preview

Clustering addresses the problem of assigning similar objects to groups. Since the size of the clusters is often constrained in practical clustering applications, various capacitated clustering problems have received increasing attention. We consider here the capacitated p-median problem (CPMP) in which p objects are selected as cluster centers (medians) such that the total distance from these medians to their assigned objects is minimized. Each object is associated with a weight, and the total weight in each cluster must not exceed a given capacity. Numerous exact and heuristic solution approaches have been proposed for the CPMP. The state-of-the-art approach performs well for instances with up to 5,000 objects but becomes computationally expensive for instances with a much larger number of objects. We propose a matheuristic with new problem decomposition strategies that can deal with instances comprising up to 500,000 objects. In a computational experiment, the proposed matheuristic consistently outperformed the state-of-the-art approach on medium- and large-scale instances while having similar performance for small-scale instances. As an extension, we show that our matheuristic can be applied to related capacitated clustering problems, such as the capacitated centered clustering problem (CCCP). For several test instances of the CCCP, our matheuristic found new best-known solutions.

Item Type:

Journal Article (Original Article)

Division/Institute:

03 Faculty of Business, Economics and Social Sciences > Department of Business Management > Institute of Financial Management > Professorship for Quantitative Methods in Business Administration

UniBE Contributor:

Gnägi, Mario and Baumann, Philipp

Subjects:

600 Technology > 650 Management & public relations

ISSN:

0305-0548

Publisher:

Elsevier

Language:

English

Submitter:

Nina Ackermann

Date Deposited:

23 Jul 2021 10:21

Last Modified:

25 Jul 2021 02:59

Publisher DOI:

10.1016/j.cor.2021.105304

BORIS DOI:

10.48350/157601

URI:

https://boris.unibe.ch/id/eprint/157601

Actions (login required)

Edit item Edit item
Provide Feedback