EUVIMEDEUVIMED entdecken
Crossref

Efficient capacitated clustering algorithm through convex polygon boundary perturbation

Maria Afsharirad

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →