Issue: 2026/Vol.36/No.3, Pages 1-24
EFFICIENT CAPACITATED CLUSTERING ALGORITHM THROUGH CONVEX POLYGON BOUNDARY PERTURBATION
Maria Afsharirad
Cite as: M. Afsharirad. Efficient capacitated clustering algorithm through convex polygon boundary perturbation. Operations Research and Decisions 2026: 36(3), 1-24. 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