Cargando…
HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem
The capacitated clustering problem (CCP) divides the vertices of the undirected graph into several disjoint clusters so that the sum of the node weights in each cluster meets the capacity limit while maximizing the sum of the weight of the edges between nodes in the same cluster. CCP is a typical NP...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Hindawi
2022
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8799340/ https://www.ncbi.nlm.nih.gov/pubmed/35096045 http://dx.doi.org/10.1155/2022/6400318 |
_version_ | 1784642048552337408 |
---|---|
author | Liu, Yaoyao Guo, Ping Zeng, Yi |
author_facet | Liu, Yaoyao Guo, Ping Zeng, Yi |
author_sort | Liu, Yaoyao |
collection | PubMed |
description | The capacitated clustering problem (CCP) divides the vertices of the undirected graph into several disjoint clusters so that the sum of the node weights in each cluster meets the capacity limit while maximizing the sum of the weight of the edges between nodes in the same cluster. CCP is a typical NP-hard problem with a wide range of engineering applications. In recent years, heuristic algorithms represented by greedy random adaptive search program (GRASP) and variable neighborhood search (VNS) have achieved excellent results in solving CCP. To improve the efficiency and quality of the CCP solution, this study proposes a new hybrid algorithm HA-CCP. In HA-CCP, a feasible solution construction method is designed to adapt to the CCP with stricter upper and lower bound constraints and an adaptive local solution destruction and reconstruction method is designed to increase population diversity and improve convergence speed. Experiments on 90 instances of 4 types show that the best average solution obtained by HA-CCP on 58 instances is better than all comparison algorithms, indicating that HA-CCP has better solution stability. HA-CCP is also superior to all comparison algorithms in average solving efficiency. |
format | Online Article Text |
id | pubmed-8799340 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2022 |
publisher | Hindawi |
record_format | MEDLINE/PubMed |
spelling | pubmed-87993402022-01-29 HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem Liu, Yaoyao Guo, Ping Zeng, Yi Comput Intell Neurosci Research Article The capacitated clustering problem (CCP) divides the vertices of the undirected graph into several disjoint clusters so that the sum of the node weights in each cluster meets the capacity limit while maximizing the sum of the weight of the edges between nodes in the same cluster. CCP is a typical NP-hard problem with a wide range of engineering applications. In recent years, heuristic algorithms represented by greedy random adaptive search program (GRASP) and variable neighborhood search (VNS) have achieved excellent results in solving CCP. To improve the efficiency and quality of the CCP solution, this study proposes a new hybrid algorithm HA-CCP. In HA-CCP, a feasible solution construction method is designed to adapt to the CCP with stricter upper and lower bound constraints and an adaptive local solution destruction and reconstruction method is designed to increase population diversity and improve convergence speed. Experiments on 90 instances of 4 types show that the best average solution obtained by HA-CCP on 58 instances is better than all comparison algorithms, indicating that HA-CCP has better solution stability. HA-CCP is also superior to all comparison algorithms in average solving efficiency. Hindawi 2022-01-21 /pmc/articles/PMC8799340/ /pubmed/35096045 http://dx.doi.org/10.1155/2022/6400318 Text en Copyright © 2022 Yaoyao Liu et al. https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Research Article Liu, Yaoyao Guo, Ping Zeng, Yi HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem |
title | HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem |
title_full | HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem |
title_fullStr | HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem |
title_full_unstemmed | HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem |
title_short | HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem |
title_sort | ha-ccp: a hybrid algorithm for solving capacitated clustering problem |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8799340/ https://www.ncbi.nlm.nih.gov/pubmed/35096045 http://dx.doi.org/10.1155/2022/6400318 |
work_keys_str_mv | AT liuyaoyao haccpahybridalgorithmforsolvingcapacitatedclusteringproblem AT guoping haccpahybridalgorithmforsolvingcapacitatedclusteringproblem AT zengyi haccpahybridalgorithmforsolvingcapacitatedclusteringproblem |