Operations Research and Decisions | 2026
Authors: Afsharirad M.
DOI: 10.37190/ord/221011
Journal: Operations Research and Decisions
Year: 2026
Publisher: Wroclaw University of Science and Technology
Document Type: Article
Open Access: All Open Access; Gold Open Access; Green Open Access
Cited by: 0
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. © 2026 Authors
Capacitated clustering; Capacitated P-median problem; Convex polygon; Distributed network problems