Issue: 2026/Vol.36/No.3, Pages
EFFICIENT CAPACITATED CLUSTERING ALGORITHM THROUGH CONVEX POLYGON BOUNDARY PERTURBATION
Maria Afsharirad
This is not yet the definitive version of the paper. This version will undergo additional copyediting, typesetting and review before it is published in its final form, but we are providing this version to give early visibility of the article.
Cite as: M. Afsharirad. Efficient capacitated clustering algorithm through convex polygon boundary perturbation. Operations Research and Decisions 2026: 36(3). DOI 10.37190/ord/221011
Abstract
Capacitated Clustering Problem (CCP) assigns objects to capacitated clusters. Among various CCPs, this work focuses on the capacitated P-median problem (CPMP). Imposing a strict capacity on each cluster, often leads to inefficient overlap for geographical data, which significantly diminish efficiency. We propose a four-stage clustering algorithm, applying convex polygon boundary perturbation to minimize overlap while satisfying capacity constraints. Necessitating a fixed number of clusters in many applications introduces a challenge in meeting capacity constraint. While most methods open a new cluster for points left unassigned, this paper designs a placement algorithm without allowing new clusters. The proposed algorithm demonstrates superior performance compared to three state-of-the-art approaches on specific instances, achieves similar performance on others, with some results reaching optimality. A novel metric is introduced to compare different methods on the same benchmarks.
Keywords: Distributed network problems, capacitated clustering, capacitated P-median problem, convex polygon
Received: 21 September 2025 Accepted: 22 April 2026
Published online: 22 April 2026