Related Experiment Video
Updated: Oct 5, 2025

Operation of the Collaborative Composite Manufacturing CCM System
Published on: October 1, 2019
HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem
Yaoyao Liu1, Ping Guo1,2, Yi Zeng1,2
1College of Computer Science, Chongqing University, Chongqing 400044, China.
Abstract:
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.
More Related Videos
12:27Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
Published on: February 15, 2017
09:27Adaptation of Hybridization Capture of Chromatin-associated Proteins for Proteomics to Mammalian Cells
Published on: June 1, 2018
Related Concept Videos
Cluster Sampling Method
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
Equivalent Capacitance
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Mesh Analysis for AC Circuits
The process of harmonizing these impedances begins with a clear understanding of the input and output signals. Once these signals are known, the...
Fast Decoupled and DC Powerflow
Distributed Loads: Problem Solving