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...

Descripción completa

Detalles Bibliográficos
Autores principales: Liu, Yaoyao, Guo, Ping, Zeng, Yi
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