Efficient capacitated clustering algorithm through convex polygon boundary perturbation
Operations Research and Decisions · 2026
DOI: 10.37190/ord/221011 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research and Decisions, 2026. Verfasst von Maria Afsharirad.
Abstract (Originalsprache)
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.
Zitieren
APA
Afsharirad, M. (2026). Efficient capacitated clustering algorithm through convex polygon boundary perturbation. Operations Research and Decisions. https://doi.org/10.37190/ord/221011
Vancouver
Afsharirad M. Efficient capacitated clustering algorithm through convex polygon boundary perturbation. Operations Research and Decisions. 2026. doi:10.37190/ord/221011
BibTeX
@article{Afsharirad2026,
author = {Afsharirad, Maria},
title = {Efficient capacitated clustering algorithm through convex polygon boundary perturbation},
journal = {Operations Research and Decisions},
year = {2026},
doi = {10.37190/ord/221011}
}
EUVIMED