# HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem

Authors: Yaoyao Liu; Ping Guo; Yi Zeng
Journal: Computational Intelligence and Neuroscience
 (2022)

---

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


---

## Body

## 1. Introduction

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 closely related to the graph partition problem (GPP) [1–5], where the goal is to find a partition of the vertex set in k classes while minimizing the number of cut edges and respecting a balance constraint between the classes. Moreover, the maximum diversity grouping problem (MDGP) [6–13] is used to partition the vertices of an edge-weighted and undirected complete graph into m groups such that the total weight of the groups is maximized subject to some group size constraints. Consequently, the objective of the handover minimization problem (HMP) in the mobile network [14] is to minimize the sum of weights of the edges with endpoints in different clusters. In addition, CCP also has essential applications in vehicle routing [15] and mail delivery [16].Optimization problems in real life are becoming more complex, with large-scale, nonlinear, multi-constrain characteristics. In recent years, many intelligent optimization algorithms [17–22] have been proposed to solve some complex practical problems effectively. Since Mulvey and Beck [23] proposed the CCP model in 1984, much literature has been on CCP and related issues. The greedy random adaptive search program (GRASP) is an effective method to solve CCP. Deng and Bard [24] combined a GRASP with path relinking (PR) and proposed GRASP-PR with a postprocessing stage. Morán-Mirabal et al. [14] proposed three random heuristic methods to solve the handover minimization problem in mobile networks: a GRASP with path relinking for the generalized quadratic assignment problem (denoted by GQAP), a GRASP with evolutionary path relinking (denoted by GevPR-HMP), and a biased random-key genetic algorithm (BRKGA). Martínez-Gavara et al. [25] proposed the greedy random adaptive search program (GRASP), Tabu search method (TS), a hybrid method combining GRASP and TS (GRASP + TS), and Tabu search with strategic oscillation (TS_SO). Martínez-Gavara et al. [26] proposed three random heuristic algorithms: greedy random adaptive search process (GRASP2-1), iterative greedy (IG), and their hybrid IG-GRASP.Algorithms based on variable neighborhood search (VNS) [27, 28] are another method of solving CCP. Lai and Hao [29] proposed an iterative variable neighborhood search (IVNS) algorithm. Brimberg et al. [30] proposed the general VNS (GVNS) and the skewed general VNS (SGVNS). Lai X et al. [31] proposed the neighborhood decomposition-driven variable neighborhood search (NDVNS) for capacitated clustering. In addition, a Tabu search designed specifically for CCP includes the TS (denoted as FITS) and the memetic algorithm (MA) proposed in the literature [32].CCP is an NP problem. By imposing upper and lower limits on the size of clusters, CCP becomes a typical constrained clustering problem. The complexity of CCP is related to the scale of the problem and the upper and lower limits of its capacity. Large-scale CCPs require more calculation time to obtain a good solution than those of small and medium CCPs. In particular, it is challenging to find feasible solutions for CCPs with strict upper or lower limits. Literature [26] introduced a hybrid method called IG-GRASP to solve CCP. On the one hand, IG-GRASP initializes a new solution and restarts the search when it falls into the local optimum and fails to break out the local optimum after a preset number of searches. This process discards the results of the previous stage search. As mentioned in [26], it is more efficient to construct a link solution of the current solution than to construct a new solution. On the other hand, as described in Section 3.3, the destruction strength of the current solution by the IG-GRASP destructive method depends on the number of clusters and nodes of the instance. When applying IG-GRASP to solve large-scale instances, the destructive method may excessively destroy the current solution, which is not conducive to the final convergence of the algorithm to a better solution. In addition, the construction method of IG-GRASP is difficult to successfully construct feasible initial solutions for some instances with strict upper and lower limits of capacity. Recently, algorithms based on VNS have been proposed to solve CCP, including IVNS, GVNS, and SGVNS. The experimental results in the literature [32] show that SGVNS has the best performance. We believe this is mainly due to the extension of the search to other promising areas of the solution space by adding skewed acceptance criteria. The algorithms based on VNS all use a random shaking process to introduce diversity to search. To improve the efficiency and quality of CCP solutions, this study proposes a new hybrid algorithm HA-CCP, which intelligently combines IG-GRASP and SGVNS algorithms. HA-CCP follows the framework of SGVNS and uses partial destruction and reconstruction strategies to introduce diversity to search. In addition, we also designed a new initial solution constructive method and partial destructive method to avoid the above limitations in IG-GRASP. The main contributions of this study include the following:(1)
A solution construction method CM2 is designed. Even if the upper and lower boundaries of the cluster are very tight, CM2 can successfully build a feasible solution. It can construct feasible solutions in a wider range of CCP solutions to make the algorithm run correctly and perform better than the random construction method [29, 31, 32].(2)
A destructive method DM3 is designed to destruct partial solutions. It adaptively destructs the solution according to the number of clusters and nodes of the instance while limiting the maximum number of deleted nodes in large-scale instances. In large-scale instances, the performance of DM3 is significantly better than DM2 [26].(3)
A hybrid algorithm HA-CCP is proposed to solve CCP. The HA-CCP follows the framework of SGVNS, uses the partial destruction and reconstruction strategy to shake the current solution, uses the proposed solution constructor to construct the initial solution, reconstructs the partial solution, and uses the proposed destruction method to destroy the partial solution. Compared with the existing VNS-based CCP algorithm [29–31], HA-CCP uses a non-fully random method to shake the current solution to improve the efficiency of the algorithm and the quality of the solution.The experimental results on 90 benchmark test instances show that HA-CCP is superior to all comparison algorithms except NDVNS (because NDVNS [31] does not provide calculation time) in terms of average solving efficiency. In terms of solution quality, HA-CCP obtained 57 best average results and 30 best results, indicating that HA-CCP outperformed all comparison algorithms in average results. However, the solution quality of HA-CCP on MDG-a instances is inferior to NDVNS.The rest of the study is organized as follows. In Section2, the definition of the CCP and the latest heuristics for CCP are introduced. Then, the overall framework of HA-CCP and the proposed construction method CM2 and destruction method DM3 are introduced in Section 3. Section 4 gives the experimental results and time-to-target analysis on benchmark instances. Section 5 analyzes the contribution of the critical algorithmic component to the performance of the proposed algorithms. Finally, conclusions and future work are provided in Section 6.


## 2. Background and Literature Review

This section introduces the concept of the CCP and the state-of-the-art CCP algorithms in the literature. Some of these algorithms are also used for analysis and comparison in Section 4.


### 2.1. Basic Concepts

For undirected weighted graphs,G=V,E, where V=v1,v2,…,vn is a set of n nodes and E is the set of edges. wi≥0 is the weight of the node vi∈V. cij is the weight of the edge. V is divided into p clusters Vk⊂V, and Vi∩Vj=∅i,j∈1,2,…,pandi≠j. If vi∈Vg, let the binary variable Xig=1; otherwise, Xig=0,i=1,2,...,n;g=1,2,...,p. The CCP based on G can be expressed as an optimization problem [29, 32]:(1)maximize∑g=1p∑i=1n−1∑j=i+1ncijXigXjg,(2)subject  to∑g=1pXig=1,∀vi∈V,(3)Lg≤∑i=1nwiXig≤Ug,∀g∈1,…,p,(4)Xig∈0,1,∀vi∈V,g∈1,….p,Here, equation (2) requires that each node be allocated and only allocated to one cluster, and equation (3) requires that the sum of the node weight of each cluster is not less than the lower limit of capacity Lg and does not exceed the upper limit of capacity Ug. The subset of the solution x is called the partial solution of x.


### 2.2. IG-GRASP for CCP

IG-GRASP [26] is the latest algorithm for solving CCP based on GRASP, as shown in Algorithm 1. It first constructs an initial solution with the construction method CM (line 6) and then improves the initial solution with the local search method IM2-1 (line 7). Subsequently, the algorithm repeatedly applies the destructive method DM2 to destruct the solution (line 9), the CM to reconstruct the solution (line 10), and the IM2-1 for local search (line 11). If several attempts cannot improve the solution (lines 8–18), the algorithm constructs a new solution (line 6) and starts again.Algorithm 1:IG-GRASP.
Input: graphG=V,E;Output: best solutionxb;(1)
x⟵EmptySolution();(2)
T⟵n ;/∗T is the maximum time allowed, and n is the number of nodes in graph G∗/(3)
NI⟵γ∗n;/∗NI is the maximum of iteration without improving allowed∗/(4)
xb⟵x;/∗xb is the best solution generated∗/(5)
whileTis  not  reacheddo(6)
yc⟵CM xb,G ;/∗CM is the construction method∗/(7)
x⟵IM 2 − 1 yc ;/∗IM2-1 is the local search method∗/(8)
whilel<NIdo(9)
y⟵DM2 x ;/∗ Partially destruct the solution x∗/(10)
yc⟵CM y,G ;/∗ Reconstruct solution ∗/(11)
x⟵IM2-1 yc ;/∗ Local search ∗/(12)
iffx>fxbthen(13)
xb⟵x;(14)
l⟵0;(15)
else(16)
l⟵l+1;(17)
end if;(18)
end while;(19)
end while;(20)
returnxb;In Algorithm1, CM (line 6) is used to construct a feasible solution. It starts by seeding the p clusters V1,V2,…,Vp with p randomly selected nodes. Then, the clusters are explored in lexicographical order assigning nodes until all of them satisfy the lower bound constraint. To do so, the candidate list VCL is formed with all the unassigned nodes and the value Ivi,k=∑j∈Vkcij is calculated for all pairs i,k of nodes and clusters. RVCLk, the restricted candidate list of nodes for cluster k, can be formed as follows:(5)RVCLk=vi∈VCLk:Ivi,k≥αImaxvi,k,where Imaxk=maxIvi,k,α∈0,1 is a parameter used to balance randomness and greed. Finally, CM randomly selects a node in RVCLk and assigns to cluster k. The nodes are allocated in this way until cluster k satisfies the lower bound of capacity. Then, all clusters are processed in this way until all clusters meet the lower limit of capacity. In the next step, CM assigns all unallocated nodes to these clusters so that each cluster meets the capacity limit constraint. In particular, CM constructs the candidate list CL by equation (6), builds RCL by equation (7), selects one pair i,k at random, and assigns node i to cluster k. CM stops when all the nodes have been assigned in this way.(6)CL=i,k:1≤k≤p,Wk+wi≤UkwhereWk=∑j∈kwj,(7)RCL=i,k∈CL:Ivi,k≥αImaxv,k.DM2 (Algorithm1, line 9) is used to destruct part of the solution. It aims to remove some nodes from the cluster so that those nodes can be assigned to a different cluster to increase the value of the objective function. DM2 first constructs a deleted candidate list DCLk for the cluster kk=1,2,...,p as follows:(8)DCLk=vi∈Vk:CRvi,Vk≤γk,where CRvi,Vk=Cvi,Vk/Cvi is the relative contribution of node vi to cluster k, Cvi,Vk=∑vj∈Vkcij is the contribution of node vi to the objective function value in cluster k, and Cvi=∑vj∈Vcij is the potential contribution of the node vi to the objective function value, γk=δminvi∈VkCRvi,Vk+1−δmaxvi∈VkCRvi,Vk is a threshold, and δ∈0,1 is a parameter to control the size of the deleted candidate list. The DM2 method deletes the percentage β elements from DCLk of each cluster k. So, the actual number of nodes removed from cluster k is max1,⌊βDCLk⌋, where DCLk is the length of the list DCLk.


### 2.3. VNS Algorithms for CCP

The VNS algorithm is a classic local search algorithm for combinatorial and global optimization problems (see [33–36]). It first constructs a feasible initial solution and then iteratively applies a shaking and local search to find the global optimal solution. Lai and Hao [29] followed the general VNS framework and proposed iterative variable neighborhood search (IVNS) for CCP. IVNS constructs the initial solution with a random construction procedure, shakes the current solution with a random shaking procedure, and finds the local optimal solution with the extended variable neighborhood descent (EVND).Brimberg et al. [30] proposed two heuristic algorithms based on VNS to solve CCP. The first is to combine variable neighborhood descent (VND) with general VNS to obtain the general variable neighborhood search (GVNS). The second is to combine VND with skewed VNS to obtain skewed general variable neighborhood search (SGVNS). SGVNS expands the search range to other promising areas of the solution space by a skew operation. The acceptance criteria for skewed moves in SGVNS are described as follows:(9)fx″fxb+εdx″,xb>1andfx″fx+εdx″,x>1,where xb is the best solution, x is the current solution, and x″ is the new solution obtained after one application of shaking and local search. ε is a parameter, and function d denotes a measure of distance between two solutions, according to [30], and dx″,xb can be calculated as follows:(10)dx″,xb=i,j:gx″,i=gx″,j∧gxb,i≠gxb,j∨gxb,i=gxb,j∧gx″,i≠gx″,ji,j:gx″,i=gx″,j∧gxb,i=gxb,j,where 1≤i<j≤n and gx″,i is the label of the cluster where the node i is located in the solution x″.


### 2.4. Tabu Search

FITS [32] is a Tabu search approach to solve CCP. It starts from generating feasible solutions and then enters the searching stage until the running deadline is reached. The searching stage alternates between a feasible local search phase (FLS for short) and an infeasible local search phase (InfLS for short). If FLS is trapped in a deep local optimum, FITS will switch to InfLS to guide the search towards new search regions. It alternately explores the feasible and infeasible solution space to avoid falling into the local optimum easily.


## 2.1. Basic Concepts

For undirected weighted graphs,G=V,E, where V=v1,v2,…,vn is a set of n nodes and E is the set of edges. wi≥0 is the weight of the node vi∈V. cij is the weight of the edge. V is divided into p clusters Vk⊂V, and Vi∩Vj=∅i,j∈1,2,…,pandi≠j. If vi∈Vg, let the binary variable Xig=1; otherwise, Xig=0,i=1,2,...,n;g=1,2,...,p. The CCP based on G can be expressed as an optimization problem [29, 32]:(1)maximize∑g=1p∑i=1n−1∑j=i+1ncijXigXjg,(2)subject  to∑g=1pXig=1,∀vi∈V,(3)Lg≤∑i=1nwiXig≤Ug,∀g∈1,…,p,(4)Xig∈0,1,∀vi∈V,g∈1,….p,Here, equation (2) requires that each node be allocated and only allocated to one cluster, and equation (3) requires that the sum of the node weight of each cluster is not less than the lower limit of capacity Lg and does not exceed the upper limit of capacity Ug. The subset of the solution x is called the partial solution of x.


## 2.2. IG-GRASP for CCP

IG-GRASP [26] is the latest algorithm for solving CCP based on GRASP, as shown in Algorithm 1. It first constructs an initial solution with the construction method CM (line 6) and then improves the initial solution with the local search method IM2-1 (line 7). Subsequently, the algorithm repeatedly applies the destructive method DM2 to destruct the solution (line 9), the CM to reconstruct the solution (line 10), and the IM2-1 for local search (line 11). If several attempts cannot improve the solution (lines 8–18), the algorithm constructs a new solution (line 6) and starts again.Algorithm 1:IG-GRASP.
Input: graphG=V,E;Output: best solutionxb;(1)
x⟵EmptySolution();(2)
T⟵n ;/∗T is the maximum time allowed, and n is the number of nodes in graph G∗/(3)
NI⟵γ∗n;/∗NI is the maximum of iteration without improving allowed∗/(4)
xb⟵x;/∗xb is the best solution generated∗/(5)
whileTis  not  reacheddo(6)
yc⟵CM xb,G ;/∗CM is the construction method∗/(7)
x⟵IM 2 − 1 yc ;/∗IM2-1 is the local search method∗/(8)
whilel<NIdo(9)
y⟵DM2 x ;/∗ Partially destruct the solution x∗/(10)
yc⟵CM y,G ;/∗ Reconstruct solution ∗/(11)
x⟵IM2-1 yc ;/∗ Local search ∗/(12)
iffx>fxbthen(13)
xb⟵x;(14)
l⟵0;(15)
else(16)
l⟵l+1;(17)
end if;(18)
end while;(19)
end while;(20)
returnxb;In Algorithm1, CM (line 6) is used to construct a feasible solution. It starts by seeding the p clusters V1,V2,…,Vp with p randomly selected nodes. Then, the clusters are explored in lexicographical order assigning nodes until all of them satisfy the lower bound constraint. To do so, the candidate list VCL is formed with all the unassigned nodes and the value Ivi,k=∑j∈Vkcij is calculated for all pairs i,k of nodes and clusters. RVCLk, the restricted candidate list of nodes for cluster k, can be formed as follows:(5)RVCLk=vi∈VCLk:Ivi,k≥αImaxvi,k,where Imaxk=maxIvi,k,α∈0,1 is a parameter used to balance randomness and greed. Finally, CM randomly selects a node in RVCLk and assigns to cluster k. The nodes are allocated in this way until cluster k satisfies the lower bound of capacity. Then, all clusters are processed in this way until all clusters meet the lower limit of capacity. In the next step, CM assigns all unallocated nodes to these clusters so that each cluster meets the capacity limit constraint. In particular, CM constructs the candidate list CL by equation (6), builds RCL by equation (7), selects one pair i,k at random, and assigns node i to cluster k. CM stops when all the nodes have been assigned in this way.(6)CL=i,k:1≤k≤p,Wk+wi≤UkwhereWk=∑j∈kwj,(7)RCL=i,k∈CL:Ivi,k≥αImaxv,k.DM2 (Algorithm1, line 9) is used to destruct part of the solution. It aims to remove some nodes from the cluster so that those nodes can be assigned to a different cluster to increase the value of the objective function. DM2 first constructs a deleted candidate list DCLk for the cluster kk=1,2,...,p as follows:(8)DCLk=vi∈Vk:CRvi,Vk≤γk,where CRvi,Vk=Cvi,Vk/Cvi is the relative contribution of node vi to cluster k, Cvi,Vk=∑vj∈Vkcij is the contribution of node vi to the objective function value in cluster k, and Cvi=∑vj∈Vcij is the potential contribution of the node vi to the objective function value, γk=δminvi∈VkCRvi,Vk+1−δmaxvi∈VkCRvi,Vk is a threshold, and δ∈0,1 is a parameter to control the size of the deleted candidate list. The DM2 method deletes the percentage β elements from DCLk of each cluster k. So, the actual number of nodes removed from cluster k is max1,⌊βDCLk⌋, where DCLk is the length of the list DCLk.


## 2.3. VNS Algorithms for CCP

The VNS algorithm is a classic local search algorithm for combinatorial and global optimization problems (see [33–36]). It first constructs a feasible initial solution and then iteratively applies a shaking and local search to find the global optimal solution. Lai and Hao [29] followed the general VNS framework and proposed iterative variable neighborhood search (IVNS) for CCP. IVNS constructs the initial solution with a random construction procedure, shakes the current solution with a random shaking procedure, and finds the local optimal solution with the extended variable neighborhood descent (EVND).Brimberg et al. [30] proposed two heuristic algorithms based on VNS to solve CCP. The first is to combine variable neighborhood descent (VND) with general VNS to obtain the general variable neighborhood search (GVNS). The second is to combine VND with skewed VNS to obtain skewed general variable neighborhood search (SGVNS). SGVNS expands the search range to other promising areas of the solution space by a skew operation. The acceptance criteria for skewed moves in SGVNS are described as follows:(9)fx″fxb+εdx″,xb>1andfx″fx+εdx″,x>1,where xb is the best solution, x is the current solution, and x″ is the new solution obtained after one application of shaking and local search. ε is a parameter, and function d denotes a measure of distance between two solutions, according to [30], and dx″,xb can be calculated as follows:(10)dx″,xb=i,j:gx″,i=gx″,j∧gxb,i≠gxb,j∨gxb,i=gxb,j∧gx″,i≠gx″,ji,j:gx″,i=gx″,j∧gxb,i=gxb,j,where 1≤i<j≤n and gx″,i is the label of the cluster where the node i is located in the solution x″.


## 2.4. Tabu Search

FITS [32] is a Tabu search approach to solve CCP. It starts from generating feasible solutions and then enters the searching stage until the running deadline is reached. The searching stage alternates between a feasible local search phase (FLS for short) and an infeasible local search phase (InfLS for short). If FLS is trapped in a deep local optimum, FITS will switch to InfLS to guide the search towards new search regions. It alternately explores the feasible and infeasible solution space to avoid falling into the local optimum easily.


## 3. A Hybrid Algorithm for CCP: HA-CCP

In this section, we propose a hybrid algorithm HA-CCP to solve CCP. HA-CCP uses a process based on the combination of greediness and randomization to construct the initial solution, uses the VND method to perform a local search to find the local optimal solution, and uses the destruction and reconstruction partial solution to shake the current solution. In addition, an acceptance criterion for skewed moves was added to enable HA-CCP to extend the search range to other promising areas of the solution space, thereby reducing repeated searches for some areas of the solution space and increasing the diversity of the search. For ease of description, in the rest of this study,xb represents the best solution obtained so far, x represents the current solution, and x″ represents the new solution obtained after one application of destruction, reconstruction, and local search of x.


### 3.1. HA-CCP Framework

The overall framework of HA-CCP is shown in Algorithm2. It constructs an initial solution x with CM2 (Algorithm 2 line 2; see Section 3.2), and if x is not a feasible solution (Algorithm 2 line 3), an empty solution is returned (Algorithm 2 line 4); otherwise, x is improved with VND [30] (Algorithm 2 line 5) and the improved solution is copied as the current best solution xb (Algorithm 2 line 6). Then, it enters the iterative process to optimize the solution until the loop condition is no longer satisfied. Each iteration consists of four stages: (1) the current solution is partially destructed (Algorithm 2 line 8; see Section 3.3); (2) the destroyed solution is reconstructed (Algorithm 2 line 9); if x″is not a feasible solution (Algorithm 2 line 10), x″ is updated with x (Algorithm 2 line 11); (3) VND is used to perform a local search on the reconstructed solution to obtain a new solution x″ (Algorithm 2 line 13); and (4) if the new solution x″ is better than the best solution xb, the current solution x and the best solution xb are updated with the new solution x″; otherwise, whether to accept the new solution x″ as the current solution x according to acceptance criteria is determined. If the acceptance criteria were satisfied, the new solution x″ is accepted as the current solution x. Otherwise, the current solution x is not updated (Algorithm 2 lines 14–21). Because the three processes of partial destruction, reconstruction, and local search have a certain degree of randomness, each iteration will produce a different new solution.Compared with Algorithm1 (IG-GRASP), Algorithm 2 (HA-CCP) has the following differences:(1)
Local Search. In Algorithm 1, IM2-1 has to be used (Algorithm 1, line 7) to improve the solution, which searches in neighborhood N4(x) [25], but Algorithm 2 applies the VND [30] based on 3 neighborhoods (Algorithm 2, line 5)(2)
Partial Destruction Solution. Algorithm 1 partially destructs the solution with DM2 (Algorithm 1, line 9), but Algorithm 2 adopts DM3 (Algorithm 2, line 8)(3)
Acceptance Criteria. Algorithm 1 adopts the “always replace” acceptance criterion (Algorithm 1, lines 12–17), but Algorithm 2 adopts the “conditional acceptance” criterion (Algorithm 2, lines 18–20)(4)
Jump out of the Local Optimum. Algorithm 1 jumps out of the local optimization after the preset number of iterations without any improvement (Algorithm 1, Line 8), but Algorithm 2 appropriately accepts the suboptimal solution as the current solution to moving the search to other areas of the solution space (Algorithm 2, line 19)(5)
Algorithm1 has one possible starting point for a new round of search: the current solution x (Algorithm 1, lines 12–17), but Algorithm 2 has two: the current solution x and the new solution x″(Algorithm 2, lines 14–21). Therefore, Algorithm 2 has a larger optimization search space than Algorithm 1Compared with the SGNVS algorithm, Algorithm2 (HA-CCP) has the following differences:(1)
In terms of the construction of the initial solution, HA-CCP uses a combination of randomization and greediness to construct the initial solution, and SGNVS uses a completely random construction method to construct the initial solution.(2)
In terms of introducing diversity for search, HA-CCP adopts the strategy of destructing and reconstructing the current solution, and the VNS-based SGVNS adopts a completely random shake process.(3)
In terms of perturbation strength, HA-CCP controls the number of the deleted nodes of the destructive method according to the number of nodes, clusters, and the parameterd_max of the current instance, while SGNVS adjusts the perturbation strength according to the solution obtained in the search process.Algorithm 2: HA-CCP.
Input: graphG=V,E, the cutoff time T;Output: the best solutionxb;(1)
x is an empty solution;(2)
x⟵CM2 x,G;/∗ Construct an initial solution, Algorithm 3∗/(3)
ifxis not  a  feasible  solutionthen(4)
return an empty solution;(5)
x⟵VND x;/∗ Improve solution x, refers to [30]∗/(6)
xb⟵x;(7)
whileelapsed time<Tdo(8)
x″⟵DM3 x;/∗ Destruct part of the solution, Algorithm 6∗/(9)
x″⟵CM2 x″,G,;/∗ Reconstruct a solution, Algorithm 3∗/(10)
ifx″is not  a  feasible  solutionthen(11)
x″⟵x ;(12)
end if;(13)
x''⟵VND x″;/∗ Improve solution x, refers to [30] ∗/(14)
iffx″>fxbthen(15)
xb⟵x″ ;/∗ Update the best solution xb with x″∗/(16)
x⟵x″ ;/∗ Update the current solution x with x″∗/(17)
else(18)
iffx″/fxb+εdx″,xb>1andfx″/fx+εdx″,x>1then/∗ Acceptance criteria, equation. (9)∗/(19)
x⟵x″;/∗ Accept the new solution x″ as the current solution x∗/(20)
end if;(21)
end if;(22)
end while;(23)
returnxb;


### 3.2. Construction Method: CM2

To construct a feasible solution, we propose CM2 in Algorithm3. CM2 includes two steps. The first step (Algorithm 3, lines 4–16) is as follows: assigning nodes to each cluster until all clusters meet the lower limit of capacity. For cluster p1≤k≤p, CM2 first constructs a candidate list VCLk with all the unallocated nodes (Algorithm 3, line 6). If the VCLk is not empty (Algorithm 3, lines 7–10), the increment VCLk of the objective function value is calculated and the restricted candidate list RVCLk isconstructed by equation (5). Then, a node in RVCLk is randomly selected and assigned to cluster k. If VCL is empty (Algorithm 3, lines 11–14), it indicates that all nodes have been allocated, but the cluster in solution x does not meet the lower limit of capacity. In this case, we apply Algorithm 4 to fix x into a feasible solution.The second step (Algorithm3, lines 18–29) is as follows: assigning the remaining unallocated nodes to suitable clusters. It first constructs the candidate list CL by equation (6). If CL is not empty (Algorithm 3, lines 20–23), the restricted candidate list RCL isconstructed by equation (7). Then, a pair of elements v,k in RCL is randomly selected and v is assigned to cluster k. All unallocated nodes are allocated in this way. If the CL is empty (Algorithm 3, lines 24–27), it indicates that there is an unallocated node v, and allocating it to any cluster will cause the cluster capacity to exceed the upper limit. For this case, we apply the LWA (Algorithm 5) for processing. CM2 performs the solution construction process up to 10 times (Algorithm 3, lines 1–3). If the feasible solution is successfully constructed, it will jump out of the loop and return to the feasible solution (Algorithm 3, lines 30–34).Algorithm 3: CM2 /∗Construction method∗/.
Input: graphG=V,E, a solution x;Output:x;/∗ A solution ∗/(1)
NI⟵10;(2)
whileNI>0do(3)
NI⟵NI−1;(4)
fork⟵1 to pdo(5)
whileWk<Lkdo(6)
VCLk⟵AN;/∗AN is the set of unallocated nodes∗/(7)
ifVCLkis  not emptythen(8)
RVCLk⟵ ConstructRCLV(VCLk);(9)
v⟵ RandomSelect RVCLk⟵;(10)
x⟵ AddvIntoVk x,v ;(11)
else(12)
x⟵ repair (x);/∗ Algorithm 4∗/(13)
gotolabel;(14)
end if;(15)
end while;(16)
end for;(17)
x′,AN′⟵x,AN ;//backup x,AN(18)
whileAN≠∅do(19)
CL⟵ ConstructCL AN;(20)
ifCL is not emptythen(21)
RCL⟵ ConstructRCL CL;(22)
v,k⟵ RandomSelect RCL;(23)
x⟵ AddvIntoVk(x, v);(24)
else(25)
x,AN⟵x′,AN′; //restore x,AN(26)
x⟵ LWA x,AN; /∗ Algorithm 5∗/(27)
break;(28)
end if;(29)
end while;(30)
label:(31)
ifxis a feasible solutionthen(32)
break;(33)
end if;(34)
end while;(35)
returnx;Algorithm4 describes the repair method. For the cluster g that does not meet the lower limit of capacity, we first construct a feasible move-in node candidate list MCLg (Algorithm 4, line 3) by equation (11). If MCLg is empty (Algorithm 4, line 4), the infeasible solution x (Algorithm 4, line 5) is returned; otherwise, the restricted candidate list RMCLk is constructed in a similar way to the restricted candidate list RVCLk (Algorithm 4, line 6). Then, a node in RMCLk is randomly selected and it is moved to the cluster g(Algorithm 4, lines 7–8). The node is moved in this way until all clusters meet the lower capacity constraint, and the repair ends.(11)MCLg=vi:1≤i≤n,vi∈Vs,1≤s≤p,s≠g,Ws−wi≥Ls,Wg+wi≤Ug.Algorithm 4: Repair.
Input: solutionx;/∗ A infeasible solution ∗/Output: x;/∗ A solution ∗/(1)
forg⟵1 to pdo(2)
whileWg<Lgdo(3)
MCLg⟵ConstructMCL();(4)
ifMCLgis emptythen(5)
returnx;(6)
RMCLg⟵ConstructRMCL MCLg;(7)
v⟵RandomSelect RMCLg;(8)
x⟵MovevIntog x,v;(9)
end while;(10)
end for;(11)
returnx;LWA is shown in Algorithm5. It first selects a node v with the largest weight among the unallocated nodes (Algorithm 5, line 2). Then, as in equation (6), a feasible allocation candidate list CCL is formed just for node v (Algorithm 5, line 3). Second, if CCL is empty (Algorithm 5, line 4), the infeasible solution x (Algorithm 5, line 5) is returned. Otherwise, the restricted candidate list RCCL is constructed by equation (7) (Algorithm 5, line 6). Finally, a pair (v, g) is selected randomly from RCCL, and the node v is assigned to cluster g (Algorithm 5, lines 7–9). The remaining unallocated nodes are allocated according to the above way.Algorithm 5: LWA.
Input: solutionx, AN;/∗Partial solution, unallocated node set ∗/Output: x;/∗ A solution ∗/(1)
whileAN≠∅do(2)
v⟵GetLargestNode AN;/∗v is a unallocated node with the largest weight∗/(3)
CCL⟵ConstructCCL();(4)
ifCCL is emptythen(5)
returnx;(6)
RCCL⟵ConstructRCCLCCL;(7)
g⟵RandomSelect RCCL;(8)
x⟵AddvIntog x,v,g;(9)
AN⟵AN/v;(10)
end while;(11)
returnx;


### 3.3. Destruction Method: DM3

To destruct partial solution, [26] proposed DM2. MD2 deletes at least one node for each cluster. For large instances, as the number of nodes and clusters increases, the number of deleted nodes increases for each cluster. On the one hand, it increases the time cost, and on the other hand, it is difficult to converge to a high-quality solution due to too many deleted nodes. To limit the number of deleted nodes, we propose a new destruction method DM3, in Algorithm 6.Algorithm6 sets the upper limit of the number of deleted nodes to dmax (Algorithm 6, lines 8–9). DM3 first selects nodes to be deleted from each cluster to construct the deletion candidate list by equation (8) (Algorithm 6, lines 3–6) and then puts all these nodes in the list GDCL (Algorithm 6, line 7). If the number of nodes in GDCL exceeds dmax, dmax nodes are randomly selected for deletion from the solution (Algorithm 6, line 11).Algorithm 6: DM3 /∗Destruction method∗/.
Input: solutionx;/∗current solution ∗/Output:x′;/∗ The destructed solution∗/(1)
GDCL⟵∅;/∗ Global delete candidate list ∗/(2)
total_del_count⟵0;/∗Total number of deleted nodes∗/(3)
fork⟵1 to pdo(4)
DCLk⟵ConstructDCL x,k;/∗Construct by equation (8)∗/(5)
total_del_count⟶total_del_count+max1,nβ∗DCLkn ;(6)
end for;(7)
GDCL⟵DCL1∪DCL2∪…∪DCLp;(8)
iftotal_del_count>dmaxthen(9)
total_del_count⟵dmax;(10)
end if;(11)
x′⟵RandomDelect(GDCL, total_del_count, x);(12)
returnx′;


## 3.1. HA-CCP Framework

The overall framework of HA-CCP is shown in Algorithm2. It constructs an initial solution x with CM2 (Algorithm 2 line 2; see Section 3.2), and if x is not a feasible solution (Algorithm 2 line 3), an empty solution is returned (Algorithm 2 line 4); otherwise, x is improved with VND [30] (Algorithm 2 line 5) and the improved solution is copied as the current best solution xb (Algorithm 2 line 6). Then, it enters the iterative process to optimize the solution until the loop condition is no longer satisfied. Each iteration consists of four stages: (1) the current solution is partially destructed (Algorithm 2 line 8; see Section 3.3); (2) the destroyed solution is reconstructed (Algorithm 2 line 9); if x″is not a feasible solution (Algorithm 2 line 10), x″ is updated with x (Algorithm 2 line 11); (3) VND is used to perform a local search on the reconstructed solution to obtain a new solution x″ (Algorithm 2 line 13); and (4) if the new solution x″ is better than the best solution xb, the current solution x and the best solution xb are updated with the new solution x″; otherwise, whether to accept the new solution x″ as the current solution x according to acceptance criteria is determined. If the acceptance criteria were satisfied, the new solution x″ is accepted as the current solution x. Otherwise, the current solution x is not updated (Algorithm 2 lines 14–21). Because the three processes of partial destruction, reconstruction, and local search have a certain degree of randomness, each iteration will produce a different new solution.Compared with Algorithm1 (IG-GRASP), Algorithm 2 (HA-CCP) has the following differences:(1)
Local Search. In Algorithm 1, IM2-1 has to be used (Algorithm 1, line 7) to improve the solution, which searches in neighborhood N4(x) [25], but Algorithm 2 applies the VND [30] based on 3 neighborhoods (Algorithm 2, line 5)(2)
Partial Destruction Solution. Algorithm 1 partially destructs the solution with DM2 (Algorithm 1, line 9), but Algorithm 2 adopts DM3 (Algorithm 2, line 8)(3)
Acceptance Criteria. Algorithm 1 adopts the “always replace” acceptance criterion (Algorithm 1, lines 12–17), but Algorithm 2 adopts the “conditional acceptance” criterion (Algorithm 2, lines 18–20)(4)
Jump out of the Local Optimum. Algorithm 1 jumps out of the local optimization after the preset number of iterations without any improvement (Algorithm 1, Line 8), but Algorithm 2 appropriately accepts the suboptimal solution as the current solution to moving the search to other areas of the solution space (Algorithm 2, line 19)(5)
Algorithm1 has one possible starting point for a new round of search: the current solution x (Algorithm 1, lines 12–17), but Algorithm 2 has two: the current solution x and the new solution x″(Algorithm 2, lines 14–21). Therefore, Algorithm 2 has a larger optimization search space than Algorithm 1Compared with the SGNVS algorithm, Algorithm2 (HA-CCP) has the following differences:(1)
In terms of the construction of the initial solution, HA-CCP uses a combination of randomization and greediness to construct the initial solution, and SGNVS uses a completely random construction method to construct the initial solution.(2)
In terms of introducing diversity for search, HA-CCP adopts the strategy of destructing and reconstructing the current solution, and the VNS-based SGVNS adopts a completely random shake process.(3)
In terms of perturbation strength, HA-CCP controls the number of the deleted nodes of the destructive method according to the number of nodes, clusters, and the parameterd_max of the current instance, while SGNVS adjusts the perturbation strength according to the solution obtained in the search process.Algorithm 2: HA-CCP.
Input: graphG=V,E, the cutoff time T;Output: the best solutionxb;(1)
x is an empty solution;(2)
x⟵CM2 x,G;/∗ Construct an initial solution, Algorithm 3∗/(3)
ifxis not  a  feasible  solutionthen(4)
return an empty solution;(5)
x⟵VND x;/∗ Improve solution x, refers to [30]∗/(6)
xb⟵x;(7)
whileelapsed time<Tdo(8)
x″⟵DM3 x;/∗ Destruct part of the solution, Algorithm 6∗/(9)
x″⟵CM2 x″,G,;/∗ Reconstruct a solution, Algorithm 3∗/(10)
ifx″is not  a  feasible  solutionthen(11)
x″⟵x ;(12)
end if;(13)
x''⟵VND x″;/∗ Improve solution x, refers to [30] ∗/(14)
iffx″>fxbthen(15)
xb⟵x″ ;/∗ Update the best solution xb with x″∗/(16)
x⟵x″ ;/∗ Update the current solution x with x″∗/(17)
else(18)
iffx″/fxb+εdx″,xb>1andfx″/fx+εdx″,x>1then/∗ Acceptance criteria, equation. (9)∗/(19)
x⟵x″;/∗ Accept the new solution x″ as the current solution x∗/(20)
end if;(21)
end if;(22)
end while;(23)
returnxb;


## 3.2. Construction Method: CM2

To construct a feasible solution, we propose CM2 in Algorithm3. CM2 includes two steps. The first step (Algorithm 3, lines 4–16) is as follows: assigning nodes to each cluster until all clusters meet the lower limit of capacity. For cluster p1≤k≤p, CM2 first constructs a candidate list VCLk with all the unallocated nodes (Algorithm 3, line 6). If the VCLk is not empty (Algorithm 3, lines 7–10), the increment VCLk of the objective function value is calculated and the restricted candidate list RVCLk isconstructed by equation (5). Then, a node in RVCLk is randomly selected and assigned to cluster k. If VCL is empty (Algorithm 3, lines 11–14), it indicates that all nodes have been allocated, but the cluster in solution x does not meet the lower limit of capacity. In this case, we apply Algorithm 4 to fix x into a feasible solution.The second step (Algorithm3, lines 18–29) is as follows: assigning the remaining unallocated nodes to suitable clusters. It first constructs the candidate list CL by equation (6). If CL is not empty (Algorithm 3, lines 20–23), the restricted candidate list RCL isconstructed by equation (7). Then, a pair of elements v,k in RCL is randomly selected and v is assigned to cluster k. All unallocated nodes are allocated in this way. If the CL is empty (Algorithm 3, lines 24–27), it indicates that there is an unallocated node v, and allocating it to any cluster will cause the cluster capacity to exceed the upper limit. For this case, we apply the LWA (Algorithm 5) for processing. CM2 performs the solution construction process up to 10 times (Algorithm 3, lines 1–3). If the feasible solution is successfully constructed, it will jump out of the loop and return to the feasible solution (Algorithm 3, lines 30–34).Algorithm 3: CM2 /∗Construction method∗/.
Input: graphG=V,E, a solution x;Output:x;/∗ A solution ∗/(1)
NI⟵10;(2)
whileNI>0do(3)
NI⟵NI−1;(4)
fork⟵1 to pdo(5)
whileWk<Lkdo(6)
VCLk⟵AN;/∗AN is the set of unallocated nodes∗/(7)
ifVCLkis  not emptythen(8)
RVCLk⟵ ConstructRCLV(VCLk);(9)
v⟵ RandomSelect RVCLk⟵;(10)
x⟵ AddvIntoVk x,v ;(11)
else(12)
x⟵ repair (x);/∗ Algorithm 4∗/(13)
gotolabel;(14)
end if;(15)
end while;(16)
end for;(17)
x′,AN′⟵x,AN ;//backup x,AN(18)
whileAN≠∅do(19)
CL⟵ ConstructCL AN;(20)
ifCL is not emptythen(21)
RCL⟵ ConstructRCL CL;(22)
v,k⟵ RandomSelect RCL;(23)
x⟵ AddvIntoVk(x, v);(24)
else(25)
x,AN⟵x′,AN′; //restore x,AN(26)
x⟵ LWA x,AN; /∗ Algorithm 5∗/(27)
break;(28)
end if;(29)
end while;(30)
label:(31)
ifxis a feasible solutionthen(32)
break;(33)
end if;(34)
end while;(35)
returnx;Algorithm4 describes the repair method. For the cluster g that does not meet the lower limit of capacity, we first construct a feasible move-in node candidate list MCLg (Algorithm 4, line 3) by equation (11). If MCLg is empty (Algorithm 4, line 4), the infeasible solution x (Algorithm 4, line 5) is returned; otherwise, the restricted candidate list RMCLk is constructed in a similar way to the restricted candidate list RVCLk (Algorithm 4, line 6). Then, a node in RMCLk is randomly selected and it is moved to the cluster g(Algorithm 4, lines 7–8). The node is moved in this way until all clusters meet the lower capacity constraint, and the repair ends.(11)MCLg=vi:1≤i≤n,vi∈Vs,1≤s≤p,s≠g,Ws−wi≥Ls,Wg+wi≤Ug.Algorithm 4: Repair.
Input: solutionx;/∗ A infeasible solution ∗/Output: x;/∗ A solution ∗/(1)
forg⟵1 to pdo(2)
whileWg<Lgdo(3)
MCLg⟵ConstructMCL();(4)
ifMCLgis emptythen(5)
returnx;(6)
RMCLg⟵ConstructRMCL MCLg;(7)
v⟵RandomSelect RMCLg;(8)
x⟵MovevIntog x,v;(9)
end while;(10)
end for;(11)
returnx;LWA is shown in Algorithm5. It first selects a node v with the largest weight among the unallocated nodes (Algorithm 5, line 2). Then, as in equation (6), a feasible allocation candidate list CCL is formed just for node v (Algorithm 5, line 3). Second, if CCL is empty (Algorithm 5, line 4), the infeasible solution x (Algorithm 5, line 5) is returned. Otherwise, the restricted candidate list RCCL is constructed by equation (7) (Algorithm 5, line 6). Finally, a pair (v, g) is selected randomly from RCCL, and the node v is assigned to cluster g (Algorithm 5, lines 7–9). The remaining unallocated nodes are allocated according to the above way.Algorithm 5: LWA.
Input: solutionx, AN;/∗Partial solution, unallocated node set ∗/Output: x;/∗ A solution ∗/(1)
whileAN≠∅do(2)
v⟵GetLargestNode AN;/∗v is a unallocated node with the largest weight∗/(3)
CCL⟵ConstructCCL();(4)
ifCCL is emptythen(5)
returnx;(6)
RCCL⟵ConstructRCCLCCL;(7)
g⟵RandomSelect RCCL;(8)
x⟵AddvIntog x,v,g;(9)
AN⟵AN/v;(10)
end while;(11)
returnx;


## 3.3. Destruction Method: DM3

To destruct partial solution, [26] proposed DM2. MD2 deletes at least one node for each cluster. For large instances, as the number of nodes and clusters increases, the number of deleted nodes increases for each cluster. On the one hand, it increases the time cost, and on the other hand, it is difficult to converge to a high-quality solution due to too many deleted nodes. To limit the number of deleted nodes, we propose a new destruction method DM3, in Algorithm 6.Algorithm6 sets the upper limit of the number of deleted nodes to dmax (Algorithm 6, lines 8–9). DM3 first selects nodes to be deleted from each cluster to construct the deletion candidate list by equation (8) (Algorithm 6, lines 3–6) and then puts all these nodes in the list GDCL (Algorithm 6, line 7). If the number of nodes in GDCL exceeds dmax, dmax nodes are randomly selected for deletion from the solution (Algorithm 6, line 11).Algorithm 6: DM3 /∗Destruction method∗/.
Input: solutionx;/∗current solution ∗/Output:x′;/∗ The destructed solution∗/(1)
GDCL⟵∅;/∗ Global delete candidate list ∗/(2)
total_del_count⟵0;/∗Total number of deleted nodes∗/(3)
fork⟵1 to pdo(4)
DCLk⟵ConstructDCL x,k;/∗Construct by equation (8)∗/(5)
total_del_count⟶total_del_count+max1,nβ∗DCLkn ;(6)
end for;(7)
GDCL⟵DCL1∪DCL2∪…∪DCLp;(8)
iftotal_del_count>dmaxthen(9)
total_del_count⟵dmax;(10)
end if;(11)
x′⟵RandomDelect(GDCL, total_del_count, x);(12)
returnx′;


## 4. Computational Experiments

This section describes the computational experiments that we conducted to evaluate the effectiveness and efficiency of the HA-CCP. We first conducted some preliminary experiments to find suitable parameters for HA-CCP. Then, we compare the result of HA-CCP with the state-of-the-art CCP algorithms: IVNS [29], GVNS [30], SGVNS [30], FITS [32], and DNVNS [31]. Section 4.1 introduces benchmark instances and experimental setup, and Section 4.2 describes the comparative experiments on benchmark instances. Section 4.3 illustrates a comparative experiment based on time-to-target (TTT) analysis method.


### 4.1. Benchmark Instances and Experimental Setup

We conducted experiments to evaluate HA-CCP on 90 benchmark instances (available at http://www.optsicom.es/ccp and [30]), which is commonly used to evaluate algorithms for CCP (see, for instance, [29–32]). It contains four sets: RanReal240, RanReal480, RanReal960, and MDG-a instances. Table 1 lists the experimental datasets. In the second column, n represents the number of nodes of the instance and p represents the number of clusters.Table 1
Experimental dataset.
Dataset nameFeatureNumber of instancesRanReal240n=240andp=1220RanReal480n=480andp=2020RanReal960n=960and30≤p≤6030MDG-an=2000andp=5020We use the following indicators to measure the advantages of each algorithm:#Best/Avg counted the number of instances where a specific algorithm outperforms the other algorithms in terms of the best and the average objective value.AverageDevbest/Devavg indicates the average percent deviation of a specific algorithm’s best/average result from the best solution obtained in all algorithms participating in the comparison, where Devbest=f∗−fbest/f∗×100 and Devavg=f∗−favg/f∗×100, and fbest is the best result of each algorithm, favg is the average result of each algorithm, and f∗ is the best solution obtained by participating in the comparison of all algorithms.Avg Time recorded the average calculation time (in seconds) required for a particular algorithm to reach its final objective function value.pvaluebest/pvalueavg represents the pvalue of the best/average result obtained through the pairwise Wilcoxon statistical test.Note that, in Section4.2, we use the result of IVNS, GVNS, SGVNS, FITS, and NDVNS present in [31]. The experiments of IVNS, GVNS, SGVNS, and FITS were executed on an Intel E5-2670 Processor (2.8 GHz) with 2 G Byte RAM running under Linux. HA-CCP is implemented in C++, compiled with the g++ compiler using the option “-O3,” and carried out on a server under Ubuntu Linux (version 16.04) with 1 Core of an Intel Xeon (Cascade Lake) Platinum 8269CY 2.5 GHz CPU and 2 G Byte RAM. These results are obtained by running each instance independently 20 times with the running time set to n seconds, where n is the number of nodes in a given instance.The HA-CCP has five parameters: the parameterα used to balance randomness and greed in CM2, the parameter δ that controls the size of the deleted candidate list in DM3, the percentage β of deleted nodes in the candidate list of each cluster, and the upper limit of the number of deleted nodes dmax in DM3 and parameter ε (for skewed moves) in HA-CCP. For α,δ,andβ, we conducted the test experiment on 13 instances with different characteristics in RanReal240, RanReal480, RanReal960, and MDG-a. For α, we keep the other parameters unchanged and change the value of α from 0.2 to 0.8 in steps of 0.2. The best value is obtained when α = 0.6. For δ and β, we use a similar method to obtain δ  = 0.7 and β  = 0.1. The value settings of parameters α,δ,β are consistent with the literature [26], so we did not report the results of this experiment.Fordmax, we test it in the range of {20, 24, 30, 40, 60}. We conducted this experiment on 9 instances with different characteristics in RanReal960 and MDG-a. The statistical results of the experiment are shown in Table 2. In terms of the best objective function value and average objective function value (#Best/Avg), HA-CCP obtains the best value at dmax=24, including obtaining 4 best objective function values and 6 best average values. According to the average percentage deviation (AvgDevbest/Devavg), HA-CCP has the smallest deviation of the best solution obtained when dmax=240.02%/0.15%, and there is not much difference between the parameter values in terms of average time. Therefore, we set dmax=24.Table 2
Bestdmax parameter values identified for HA-CCP.
dmax2024304060#Best/Avg3/34/60/00/00/0p valuebest/p valueavg1.00/0.0040.18/0.0040.004/0.0040.004/0.004Avg Devbest/Devavg (%)0.04/0.180.02/0.150.04/0.190.11/0.240.17/0.29AvgTime (s)1074.011062.571051.711037.851012.09For parameterε, according to [30], ε=0.01. On this basis, we test ε=0.01 and ε=0.005 on 4 instances from RanReal with p≤12 and 13 instances from RanReal240, RanReal480, RanReal960, and MDG-a with p>12. The test results are shown in Tables 3 and 4. On the instances with p≤2, the effect of ε=0.01 is better than ε=0.005. In the other instance, ε=0.005 presents a better effect. Therefore, in instances where the number of clusters is greater than 12, we set ε=0.005, and in other instances, we set ε=0.01.Table 3
Bestε parameter values identified for HA-CCP on the instances with p≤12.
ε0.010.005#Best/Avg4/41/0p valuebest/p valueavg0.25/0.125Avg Devbest/Devavg (%)0.00/0.050.03/0.18AvgTime (s)118.23108.86Table 4
Bestε parameter values identified for HA-CCP on the instances with p>12.
ε0.010.005#Best/Avg2/011/13p valuebest/p valueavg0.022/2.4E − -4Avg Devbest/Devavg (%)0.10/0.240.007/0.16AvgTime (s)807.47837.90


### 4.2. Algorithm Comparison Experiment

To evaluate the performance of HA-CCP, we compared the solution of HA-CCP, IVNS [29], GVNS [30], SGVNS [30], FITS [32], and NDVNS [31]. The instances in the experiment are divided into small and medium instances and large-scale instances.The experimental statistical results on the datasets of small and medium instances (RanReal240 and RanReal480) are shown in Table5. Tables 6 and 7 give detailed results. In Table 5, HA-CCP is better than other algorithms on 19 instances in terms of the best objective function value and has better performance on 36 instances from the average result. According to the average percentage deviation, HA-CCP has the smallest deviation from the best solution obtained in the experiment 0.02%/0.13%. The statistical test shows a significant performance difference between HA-CCP and other comparison algorithms p−value≤0.05, except for the best results of NDVNS.Table 5
Experimental statistical results on RanReal240 and RanReal480.
IVNSGVNSSGVNSFITSNDVNSHA-CPP#Best/Avg3/00/02/18/019/319/36p valuebest/p valueavg3.46E − 07/2.54E − 102.54E − 10/2.54E − 102.47E − 05/1.25E − 82.46E − 04/1.25E − 080.87/7.62E − 08Avg Devbest/Devavg (%)0.17/0.350.35/0.630.08/0.190.09/0.270.03/0.250.02/0.13AvgTime (s)280.01296.66226.89249.39—217.25Note. In Table 5, the symbol “—” denotes the cases when the result is not reported in the literature.Table 6
Comparative results of different algorithms on RanReal240 and RanReal480.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPRanReal240_01224831.56/224571.29224580.56/224207.09224968.01/224769.72224941.48/224802.06224949.51/224689.70225003.70/224897.01RanReal240_02204624.36/204275.49204205.41/203682.12204624.36/204444.31204624.36/204359.38204563.81/204214.81204624.36/204515.06RanReal240_03198861.68/198606.95198472.78/197806.87199059.56/198849.22198954.91/198799.84198976.88/198681.37199079.37/198915.84RanReal240_04225390.88/225069.14225144.59/224463.81225627.16/225389.88225627.16/225364.97225618.17/225185.91225683.17/225346.54RanReal240_05195540.41/195184.84194911.72/194361.91195516.57/195306.51195564.48/195320.28195539.89/195401.63195540.41/195469.00RanReal240_06216713.91/216355.53216383.13/215849.06216733.31/216584.23216747.32/216487.02216747.32/216173.65216730.26/216613.93RanReal240_07209216.90/208992.44209118.64/208329.21209223.34/209080.57209305.70/209029.23209273.70/209063.40209282.88/209150.41RanReal240_08205246.82/204842.79204754.36/204137.78205154.20/204951.2205246.82/204961.05205246.82/205099.31205246.82/205110.51RanReal240_09209142.07/208720.16208702.16/208276.52209007.44/208904.78209159.16/208952.48209186.90/208987.58209057.64/208897.23RanReal240_10192885.48/192598.79192343.75/191874.34193062.60/192842.05192986.21/192811.13192948.92/192523.02193044.16/192954.72RanReal240_11204647.20/204377.08204399.04/203900.12204615.71/204480.92204722.75/204559.39204722.75/204398.23204722.75/204638.07RanReal240_12201028.32/200763.75200822.69/200150.52201076.30/200938.30201117.11/200797.67200978.99/200737.16201117.11/201006.45RanReal240_13202331.20/202027.28201977.87/201356.20202321.58/202198.63202335.99/202139.57202345.12/202276.80202345.48/202285.83RanReal240_14228870.89/228520.04228661.60/228054.32228775.14/228569.78228870.89/228554.78228870.89/228396.82228971.03/228740.72RanReal240_15191152.17/190827.68190575.48/189965.59191238.53/191058.62191255.87/190923.28191263.28/190945.28191243.76/191117.60RanReal240_16204074.95/203668.49203816.48/203270.11203991.53/203649.04204054.99/203710.39204074.95/203918.76204072.57/203961.38RanReal240_17195206.73/194950.57194840.79/194404.70195423.83/195241.19195561.36/195243.32195509.13/195236.75195393.97/195278.93RanReal240_18194916.37/194704.23194915.62/194114.09195120.98/194967.73195100.39/194872.13195167.14/194886.16195167.14/195069.80RanReal240_19199200.03/198905.05198828.82/198119.14199307.33/199093.86199225.98/199040.43199216.46/198895.83199307.33/199204.90RanReal240_20212264.10/211871.74211984.80/211458.51212268.46/212037.43212268.52/212049.85212323.22/212130.13212229.46/212111.19RanReal480_01554337.23/553795.85553224.53/552326.59555430.60/554994.68555489.92/554376.54556639.68/555566.55556126.86/555338.06RanReal480_02510066.41/509058.46508711.62/507540.62510718.79/510304.78511280.50/509757.15511666.95/510495.78511566.55/510924.27RanReal480_03496334.51/495409.98495140.23/493706.92497725.86/496785.80497295.19/496059.50497846.57/495871.46498028.54/497109.59RanReal480_04521669.00/520051.55520653.34/519051.60522572.81/521952.28522305.16/521062.13522748.49/520295.34522790.22/521999.31RanReal480_05483670.19/482390.51481803.95/480508.80483819.77/482603.84484084.66/482867.74484742.51/482831.18485138.44/484092.59RanReal480_06533589.61/532462.25532702.72/531627.12534515.67/533916.00533991.27/533036.36535503.61/533138.78534961.79/534114.47RanReal480_07545343.81/544060.83544445.60/542318.56545812.49/545302.82545470.73/544651.12546951.97/545548.47546503.90/545582.87RanReal480_08531974.48/531023.25531287.92/529525.39532736.12/532109.62532417.42/531667.91533098.56/531631.32532891.23/532161.08RanReal480_09555604.38/554820.43555163.27/553394.39556865.18/556081.91556868.85/555634.40557283.90/555998.60557120.25/556265.26RanReal480_10519066.57/518412.32517431.34/516228.20520014.70/518024.16520257.54/518071.71520481.15/518812.29520492.06/519891.18RanReal480_11523463.33/522201.99522626.50/521218.97524124.60/523508.02523991.29/522816.94524059.91/522416.53524669.99/523760.48RanReal480_12501462.57/500055.30499914.17/498596.97502570.10/501632.20501915.56/500776.79502656.68/501171.81503359.96/502069.60RanReal480_13534294.24/533478.80533672.27/532322.68535411.94/534651.24535025.51/533823.79535633.80/533605.55535251.73/534707.51RanReal480_14513186.65/512501.71512764.33/511212.78514537.52/513935.11514107.62/513053.25514696.90/512600.42515476.42/514801.49RanReal480_15516657.20/515416.17515607.47/514465.20518029.18/517189.00517205.02/516018.38518605.32/516455.65518370.90/517283.29RanReal480_16549230.25/548274.66549033.57/547075.83549840.64/549253.54549552.63/548462.13550482.48/549108.44550317.71/549881.85RanReal480_17537223.44/536149.06536402.45/534770.20537993.79/537568.15537924.55/536745.39538331.26/536829.04538745.70/537826.26RanReal480_18525490.09/524515.11524631.54/522908.72526349.49/525453.50525822.76/524712.42526466.23/523932.37526314.82/525702.47RanReal480_19522280.40/521442.89521672.59/519720.44522757.15/522218.13522316.22/521267.22523219.84/522114.62522958.23/522365.10RanReal480_20518436.63/516935.15516488.64/515450.41518847.01/518202.52518349.10/517430.77519492.21/518475.86519277.92/518518.27#Best3/00/02/18/019/319/36p Value3.46E − 07/2.54E – 102.54E − 10/2.54E − 102.47E − 05/1.25E − 082.46E − 04/1.25E − 080.87/7.62E − 08Note. In Table 6, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 7
Devbest, Devavg, and average time of different algorithms on RanReal240 and RanReal480.
Instance nameIVNSGVNSSGVNSFITSDNVNSHA-CCPRanReal240_010.08/0.19/155.570.19/0.35/155.920.02/0.10/127.160.03/0.09/149.090.02/0.14/-0.00/0.05/127.88RanReal240_020.00/0.17/184.440.2/0.46/159.560.00/0.09/158.200.00/0.13/150.750.03/0.20/-0.00/0.05/111.58RanReal240_030.11/0.24/186.060.3/0.64/164.110.01/0.12/139.260.06/0.14/169.950.05/0.20/-0.00/0.08/135.66RanReal240_040.13/0.27/159.700.24/0.54/175.000.02/0.13/137.870.02/0.14/118.580.03/0.22/-0.00/0.15/124.67RanReal240_050.01/0.19/155.020.33/0.61/179.730.02/0.13/136.480.00/0.12/132.330.01/0.08/-0.01/0.05/135.27RanReal240_060.02/0.18/174.510.17/0.41/187.590.01/0.08/126.610.00/0.12/155.990.00/0.26/-0.01/0.06/129.28RanReal240_070.04/0.15/160.670.09/0.47/195.330.04/0.11/144.350.00/0.13/144.960.02/0.12/-0.01/0.07/127.25RanReal240_080.00/0.20/145.940.24/0.54/193.880.05/0.14/122.790.00/0.14/124.220.00/0.07/-0.00/0.07/112.98RanReal240_090.02/0.22/194.360.23/0.44/171.090.09/0.13/136.240.01/0.11/141.690.00/0.10/-0.06/0.14/98.89RanReal240_100.09/0.24/183.490.37/0.62/145.390.00/0.11/162.770.04/0.13/134.200.06/0.28/-0.01/0.06/111.58RanReal240_110.04/0.17/157.980.16/0.40/155.120.05/0.12/136.250.00/0.08/129.910.00/0.16/-0.00/0.04/125.15RanReal240_120.04/0.18/186.710.15/0.48/157.430.02/0.09/123.130.00/0.16/132.030.07/0.19/-0.00/0.06/108.32RanReal240_130.01/0.16/173.460.18/0.49/171.440.01/0.07/127.250.00/0.10/131.340.00/0.03/-0.00/0.03/139.97RanReal240_140.04/0.20/147.560.14/0.40/164.870.09/0.18/112.270.04/0.18/135.870.04/0.25/-0.00/0.10/122.04RanReal240_150.06/0.23/167.880.36/0.68/188.750.01/0.11/154.190.00/0.18/131.830.00/0.17/-0.01/0.08/101.57RanReal240_160.00/0.20/165.220.13/0.39/181.820.04/0.21/130.930.01/0.18/89.110.00/0.08/-0.00/0.06/102.24RanReal240_170.18/0.31/171.750.37/0.59/179.250.07/0.16/149.060.00/0.16/171.030.03/0.17/-0.09/0.14/132.10RanReal240_180.13/0.24/154.600.13/0.54/169.520.02/0.10/167.150.03/0.15/152.830.00/0.14/-0.00/0.05/110.87RanReal240_190.05/0.20/173.650.24/0.60/179.990.00/0.11/140.210.04/0.13/98.090.05/0.21/-0.00/0.05/121.71RanReal240_200.03/0.21/188.640.16/0.41/175.520.03/0.13/112.330.03/0.13/115.380.00/0.09/-0.04/0.10/99.55RanReal480_010.41/0.51/391.120.61/0.77/419.980.22/0.30/301.250.21/0.41/340.600.00/0.19/-0.09/0.23/349.71RanReal480_020.31/0.51/403.380.58/0.81/414.240.19/0.27/293.360.08/0.37/355.590.00/0.23/-0.02/0.15/330.24RanReal480_030.34/0.53/420.240.58/0.87/427.120.06/0.25/331.810.15/0.40/352.060.04/0.43/-0.00/0.18/332.28RanReal480_040.21/0.52/383.190.41/0.72/428.090.04/0.16/332.130.09/0.33/399.510.01/0.48/-0.00/0.15/329.59RanReal480_050.30/0.57/417.550.69/0.95/448.150.27/0.52/325.050.22/0.47/335.840.08/0.48/-0.00/0.22/301.91RanReal480_060.36/0.57/393.370.52/0.72/428.170.18/0.30/300.770.28/0.46/390.060.00/0.44/-0.10/0.26/280.00RanReal480_070.29/0.53/395.010.46/0.85/423.310.21/0.30/342.070.27/0.42/390.230.00/0.26/-0.08/0.25/285.02RanReal480_080.21/0.39/388.450.34/0.67/398.320.07/0.19/356.390.13/0.27/380.640.00/0.28/-0.04/0.18/283.23RanReal480_090.30/0.44/376.210.38/0.70/421.610.08/0.22/350.350.07/0.30/383.670.00/0.23/-0.03/0.18/255.35RanReal480_100.27/0.40/383.710.59/0.82/428.060.09/0.47/300.430.05/0.47/328.850.00/0.32/-0.00/0.12/307.38RanReal480_110.23/0.47/383.910.39/0.66/421.150.10/0.22/320.080.13/0.35/383.650.12/0.43/-0.00/0.17/299.74RanReal480_120.38/0.66/397.430.68/0.95/409.110.16/0.34/270.860.29/0.51/347.320.14/0.43/-0.00/0.26/349.86RanReal480_130.25/0.40/404.230.37/0.62/390.760.04/0.18/327.700.11/0.34/330.840.00/0.38/-0.07/0.17/333.59RanReal480_140.44/0.58/405.040.53/0.83/419.870.18/0.30/319.140.27/0.47/352.070.15/0.56/-0.00/0.13/340.90RanReal480_150.38/0.61/384.960.58/0.80/418.770.11/0.27/313.910.27/0.50/387.020.00/0.41/-0.05/0.25/282.23RanReal480_160.23/0.40/345.110.26/0.62/419.820.12/0.22/301.160.17/0.37/392.780.00/0.25/-0.03/0.11/294.16RanReal480_170.28/0.48/386.160.43/0.74/411.520.14/0.22/320.590.15/0.37/360.930.08/0.36/-0.00/0.17/336.43RanReal480_180.19/0.37/368.200.35/0.68/431.300.02/0.19/278.260.12/0.33/320.600.00/0.48/-0.03/0.15/330.79RanReal480_190.18/0.34/400.780.30/0.67/435.580.09/0.19/306.800.17/0.37/380.690.00/0.21/-0.05/0.16/343.32RanReal480_200.20/0.49/385.300.58/0.78/420.080.12/0.25/339.090.22/0.40/353.520.00/0.20/-0.04/0.19/345.87Average0.17/0.35/280.010.35/0.63/296.660.08/0.19/226.890.09/0.27/249.390.03/0.25/-0.02/0.13/217.25Note. In Table 7, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution. The symbol “-” denotes the cases when the result is not reported in the literature.The experimental statistical results on the dataset of large-scale instances (RanReal960) are shown in Table8. The detailed results are given in Tables 9 and 10. According to Table 8, HA-CCP has obvious advantages in average results. It obtained 20 best average results out of 30 instances and 11 best results. HA-CCP surpasses other comparison algorithms in terms of the average percent deviation of average result from best-found solutions (AvgeDevavg=0.19). The pvaluebest/pvalueavg row shows a statistically significant difference in performance between HA-CCP and all the reference algorithms except NDVNS.Table 8
Experimental statistical results on RanReal960.
IVNSGVNSSGVNSFITSNDVNSHA-CPP#Best/Avg0/00/00/01/218/1011/18p valuebest/p valueavg4.32E − 08/4.32E − 084.32E − 08/4.32E − 084.32E − 08/4.32E − 081.18E − 05/1.18E − 050.14/0.07Avg Devbest/Devavg (%)0.81/1.020.81/1.120.19/0.390.52/0.620.04/0.240.04/0.19AvgTime (s)843.9862.2840.91893.11—723.82Note. In Table 8, the symbol “—” denotes the cases when the result is not reported in the literature.Table 9
Comparative results of different algorithms on RanReal960.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPRanReal960_01.301331323.28/1329095.101331996.73/1328415.401337853.23/1335679.541333878.00/1332712.781340369.47/1338452.931339904.73/1337999.56RanReal960_02.301426870.24/1423903.721427037.60/1422960.001433071.63/1430808.901434529.49/1433886.301435819.84/1433258.341435087.46/1433503.63RanReal960_03.301390084.19/1387508.881390367.98/1386753.981395846.80/1394012.261392101.18/1390924.211398554.78/1397154.111397520.91/1396135.59RanReal960_04.301407607.65/1405972.041406916.02/1403198.731413478.82/1410438.071414344.67/1412460.011414919.86/1412464.181413878.60/1411928.57RanReal960_05.301363405.33/1360883.591362240.30/1359314.241370560.76/1367959.841365975.96/1365612.741372686.88/1370958.721371391.13/1369452.03RanReal960_06.301413074.62/1409803.61410969.99/1408670.371417338.38/1415708.821413476.58/1412750.081420632.38/1419467.401420942.81/1418222.26RanReal960_07.301332205.25/1329503.041332748.04/1329170.211339735.87/1337029.011334504.35/1334263.931341829.68/1340275.061341640.99/1340054.65RanReal960_08.301462280.35/1458524.761460407.11/1457531.521466738.95/1464441.531463737.39/1462602.721469545.99/1466830.821467330.75/1465505.59RanReal960_09.301378445.37/1376305.911380206.02/1374713.941385287.77/1382960.301381577.32/1379280.981387514.11/1385397.311385795.46/1384258.20RanReal960_10.301377646.33/1374311.231377009.66/1373790.241384154.95/1381870.761379905.83/1378772.671386801.94/1384724.791384935.52/1383811.91RanReal960_01.401034548.05/1031462.281032872.42/1030512.991041148.42/1038487.541035642.67/1034626.821042735.72/1040717.991042362.60/1041082.27RanReal960_02.401108588.66/1106671.471109086.02/1106469.641115789.54/1113937.771110547.59/1110074.361117471.02/1115602.031117552.44/1115723.68RanReal960_03.401081509.08/1079553.821080281.13/1077244.611086488.77/1085060.191083240.15/1082948.771089012.05/1087325.531088964.98/1087568.20RanReal960_04.401096347.39/1092785.741096438.26/1091633.051100866.71/1098759.101103897.12/1101073.371102222.98/1100256.111101734.58/1100608.60RanReal960_05.401056103.80/1054445.691057478.73/1054478.201063682.56/1062213.711059158.09/1058478.461066415.88/1064390.341066157.77/1065037.50RanReal960_06.401096895.36/1095721.541099861.44/1093932.851104590.22/1102651.281100368.74/1100064.661107955.38/1105069.061107485.89/1105353.87RanReal960_07.401034299.55/1032667.931035241.97/1031362.331041064.58/1038879.341043376.95/1039933.231043921.14/1041464.081043176.75/1042209.24RanReal960_08.401137464.75/1136002.241136567.63/1133556.701142282.86/1141171.701139865.05/1138054.461144615.34/1141877.821143818.84/1142790.55RanReal960_09.401068288.24/1066496.301068892.92/1066427.061076229.18/1073798.911072116.14/1071426.071076786.59/1075606.231076536.88/1074554.12RanReal960_10.401069556.59/1067889.461069985.94/1067548.971077400.98/1074400.361072919.65/1071480.211079212.31/1077123.001078818.14/1077728.42RanReal960_01.60726465.37/724244.42725912.84/723156.84732096.63/730601.10727690.58/727222.73733900.43/731787.78733960.17/732785.75RanReal960_02.60770060.9/768413.74770477.46/768062.71776289.95/775060.74773921.97/772572.49776085.50/774619.17777733.23/776084.26RanReal960_03.60753090.65/751419.9753094.36/750898.37760248.25/758432.10756677.95/755442.64760728.09/758924.49761312.30/760046.12RanReal960_04.60762952.42/761387.83763837.98/760835.94769112.25/767780.08765253.27/764696.30770170.61/768057.59769559.96/768476.28RanReal960_05.60741248.79/739443.77741932.85/738830.28748581.43/746014.20743715.56/743165.17748244.40/747006.91749316.68/747647.96RanReal960_06.60761947.94/760369.56762260.95/759048.94767679.61/765628.88763029.06/761957.51768180.66/765223.34769233.87/767971.96RanReal960_07.60723439.86/721167.69723786.02/720360.15728827.33/727427.19725993.23/725733.17731064.84/728984.94732249.82/730484.07RanReal960_08.60789552.19/786344.58787775.07/785553.15794363.93/792538.90791334.42/790285.98794354.56/791262.07795313.86/793390.82RanReal960_09.60747509.96/745313.38746710.78/744341.99753943.93/751871.94750858.18/749209.83754578.20/753033.20754811.24/753473.44RanReal960_10.60748812.21/746701.78747565.74/745004.51754666.01/752583.88749883.45/748985.05755076.90/753154.35756020.38/754733.58#Best0/00/00/01/218/1011/18p value4.32E − 08/4.32E − 084.32E − 08/4.32E − 084.32E − 08/4.32E − 081.18E − 05/1.18E − 050.14/0.07Note. In Table 9, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 10
Devbest, Devavg, and average time of different algorithms on RanReal960.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPRanReal960_01.300.67/0.84/918.260.62/0.89/811.540.19/0.35/856.210.48/0.57/915.530/0.14/-0.03/0.18/720.64RanReal960_02.300.62/0.83/797.610.61/0.90/842.950.19/0.35/835.980.09/0.13/904.230/0.18/-0.05/0.16/731.68RanReal960_03.300.61/0.79/883.410.59/0.84/860.630.19/0.32/829.850.46/0.55/836.810/0.1/-0.07/0.17/673.02RanReal960_04.300.52/0.63/919.960.57/0.83/832.990.10/0.32/822.400.04/0.17/929.490/0.17/-0.07/0.21/780.14RanReal960_05.300.68/0.86/804.130.76/0.97/883.850.15/0.34/840.420.49/0.52/957.250/0.13/-0.09/0.24/686.23RanReal960_06.300.55/0.78/857.850.70/0.86/801.300.25/0.37/834.760.53/0.58/935.810.02/0.1/-0.00/0.19/777.19RanReal960_07.300.72/0.92/875.580.68/0.94/850.220.16/0.36/816.600.55/0.56/894.980/0.12/-0.01/0.13/769.18RanReal960_08.300.49/0.75/804.150.62/0.82/822.220.19/0.35/831.190.40/0.47/948.470/0.18/-0.15/0.27/686.39RanReal960_09.300.65/0.81/815.060.53/0.92/863.400.16/0.33/812.810.43/0.59/884.890/0.15/-0.12/0.23/641.61RanReal960_10.300.66/0.9/878.660.71/0.94/850.020.19/0.36/792.140.50/0.58/897.680/0.15/-0.13/0.22/775.20RanReal960_01.400.79/1.08/877.730.95/1.17/847.870.15/0.41/832.620.68/0.78/913.510/0.19/-0.04/0.16/724.70RanReal960_02.400.8/0.97/824.060.76/0.99/876.230.16/0.32/830.260.63/0.67/938.570.01/0.17/-0.00/0.16/689.19RanReal960_03.400.69/0.87/905.640.80/1.08/850.330.23/0.36/816.430.53/0.56/829.180/0.15/-0.00/0.13/726.02RanReal960_04.400.68/1.01/800.470.68/1.11/904.060.27/0.47/761.940.00/0.26/931.930.15/0.33/-0.20/0.30/737.53RanReal960_05.400.97/1.12/826.350.84/1.12/857.740.26/0.39/803.470.68/0.74/882.950/0.19/-0.02/0.13/737.69RanReal960_06.401.00/1.10/876.400.73/1.27/835.260.30/0.48/840.430.68/0.71/795.610/0.26/-0.04/0.23/764.48RanReal960_07.400.92/1.08/882.220.83/1.20/884.530.27/0.48/871.150.05/0.38/891.650/0.24/-0.07/0.16/796.50RanReal960_08.400.62/0.75/807.240.70/0.97/851.960.20/0.30/827.890.42/0.57/884.170/0.24/-0.07/0.16/711.17RanReal960_09.400.79/0.96/818.160.73/0.96/878.540.05/0.28/847.560.43/0.50/873.440/0.11/-0.02/0.21/716.20RanReal960_10.400.89/1.05/872.900.85/1.08/863.940.17/0.45/860.780.58/0.72/943.530/0.19/-0.04/0.14/689.14RanReal960_01.601.02/1.32/789.021.10/1.47/901.120.25/0.46/907.890.85/0.92/901.040.01/0.3/-0.00/0.16/751.24RanReal960_02.600.99/1.20/826.250.93/1.24/874.070.19/0.34/873.060.49/0.66/887.610.21/0.4/-0.00/0.21/687.37RanReal960_03.601.08/1.30/808.811.08/1.37/852.820.14/0.38/873.260.61/0.77/923.810.08/0.31/-0.00/0.17/658.15RanReal960_04.600.94/1.14/853.850.82/1.21/830.990.14/0.31/839.140.64/0.71/819.90/0.27/-0.08/0.22/723.40RanReal960_05.601.08/1.32/831.310.99/1.40/895.340.10/0.44/868.220.75/0.82/889.580.14/0.31/-0.00/0.22/691.55RanReal960_06.600.95/1.15/766.030.91/1.32/872.940.20/0.47/836.760.81/0.95/864.120.14/0.52/-0.00/0.16/727.95RanReal960_07.601.20/1.51/918.061.16/1.62/909.030.47/0.66/878.590.85/0.89/875.950.16/0.45/-0.00/0.24/680.08RanReal960_08.600.72/1.13/851.600.95/1.23/911.420.12/0.35/859.760.50/0.63/870.010.12/0.51/-0.00/0.24/761.94RanReal960_09.600.97/1.26/770.731.07/1.39/849.730.11/0.39/868.300.52/0.74/900.640.03/0.24/-0.00/0.18/740.51RanReal960_10.600.95/1.23/855.351.12/1.46/898.950.18/0.45/857.380.81/0.93/870.890.12/0.38/-0.00/0.17/758.65Average0.81/1.02/843.90.81/1.12/862.20.19/0.39/840.910.52/0.62/893.110.04/0.24/-0.04/0.19/723.82Note. In Table 10, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution. The symbol “-” denotes the cases when the result is not reported in the literature.The experimental statistical results on the dataset of large-scale instances (MDG-a) are presented in Table11. Tables 12 and 13 give detailed results. It can be seen from Table 7 that NDVNS has obvious advantages in solution quality, but HA-CCP is better than other algorithms (such as IVNS, GVNS, SGVNS, and FITS), which is also proved by the results of statistical testing.Table 11
Experimental statistical results on the MDG-a.
IVNSGVNSSGVNSFITSNDVNSHA-CPP#Best/Avg0/00/00/00/020/160/4p valuebest/p valueavg7.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/0.01AvgDevbest/Devavg (%)2.63/3.40.99/1.010.43/0.572.12/2.430.00/0.160.1/0.21AvgTime (s)1862.551712.931839.951867.01-1757.32Note. In Table 11, the symbol “-” denotes the cases when the result is not reported in the literature.Table 12
Comparative results of different algorithms on the MDG-a.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPMDG-a_21379241.00/376249.80388647.00/387189.20389269.00/389208.15383164.00/382387.05391259.00/390647.15390987.00/390660.00MDG-a_22380665.00/377418.75384487.00/384018.35386354.00/386007.50380817.00/380489.60388476.00/387718.60387838.00/387393.10MDG-a_23375697.00/374941.20386154.00/385489.20387267.00/387019.40380630.00/379334.85389363.00/388908.60389071.00/388611.10MDG-a_24378258.00/376540.75387095.00/386473.15388423.00/388008.45381783.00/380560.55390269.00/389655.40390051.00/389525.40MDG-a_25389242.00/384685.70387121.00/395749.55398108.00/397471.50390623.00/386346.05399478.00/399002.40399215.00/398869.20MDG-a_26392407.00/389113.50396756.00/400015.60402135.00/401471.95393222.00/392916.10403457.00/402740.95403425.00/402759.75MDG-a_27375566.00/373113.95380243.00/379248.65381896.00/381208.70377617.00/376721.60383780.00/382951.05383246.00/382731.55MDG-a_28378486.00/375546.50386018.00/385207.20387594.00/387004.55380748.00/379732.95389025.00/388516.50388553.00/388208.60MDG-a_29377175.00/372663.75382108.00/381301.50383937.00/383008.55378239.00/377540.40385316.00/384816.05384933.00/384588.45MDG-a_30389615.00/386318.15394817.00/394281.50396678.00/396041.70389452.00/389254.10398211.00/397776.80398004.00/397503.15MDG-a_31376920.00/374627.70384718.00/384018.25386587.00/385749.40379407.00/378922.70388375.00/387562.05387609.00/387276.55MDG-a_32382405.00/379790.40391693.00/391004.60393098.00/392578.60383333.00/382737.35394611.00/394031.35394290.00/393941.40MDG-a_33377689.00/373096.60382576.00/381876.80384291.00/383273.45379047.00/376641.80385806.00/385212.70385583.00/385036.20MDG-a_34384412.00/381472.65393135.00/392409.55394676.00/394176.80386544.00/385459.25396725.00/395823.10396214.00/395706.85MDG-a_35385251.00/383302.15393384.00/392174.20394687.00/394059.40386347.00/385302.60396054.00/395455.20395848.00/395472.25MDG-a_36394867.00/389332.30400271.00/400019.40402087.00/401287.65396368.00/394103.05403604.00/403111.10402998.00/402698.45MDG-a_37384811.00/380906.40387006.00/386276.45388411.00/387875.60386195.00/385797.30390289.00/389612.25389769.00/389349.00MDG-a_38387472.00/384752.55394264.00/393879.15395865.00/395287.90388712.00/387807.15397407.00/396710.05397249.00/396775.25MDG-a_39381738.00/378840.90390008.00/389147.50391415.00/391074.95385975.00/383036.10393415.00/392799.15392913.00/392506.70MDG-a_40392751.00/391517.70403662.00/403108.90405184.00/405008.90396321.00/395505.80407084.00/406615.75406672.00/406245.60#Best0/00/00/00/020/160/4p Value7.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74e-067.74E-06/0.01Note. In Table 12, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 13
Devbest, Devavg, and average time of different algorithms on the MDG-a.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPMDG-a_213.07/3.84/1938.050.67/1.04/1518.30.51/0.52/1867.832.07/2.27/1872.280.00/0.16/-0.07/0.15/1765.62MDG-a_222.01/2.85/1840.871.03/1.15/1806.640.55/0.64/1801.351.97/2.06/1931.750.00/0.19/-0.16/0.28/1719.05MDG-a_233.51/3.7/1868.530.82/0.99/1741.740.54/0.60/1839.262.24/2.58/1937.180.00/0.12/-0.07/0.19/1773.65MDG-a_243.08/3.52/1892.930.81/0.97/1697.710.47/0.58/1830.542.17/2.49/1903.310.00/0.16/-0.06/0.19/1807.82MDG-a_252.56/3.7/1829.423.09/0.93/1663.950.34/0.50/1870.122.22/3.29/1824.790.00/0.12/-0.07/0.15/1731.29MDG-a_262.74/3.56/1923.601.66/0.85/1665.890.33/0.49/1790.92.54/2.61/1926.980.00/0.18/-0.01/0.17/1701.12MDG-a_272.14/2.78/1790.230.92/1.18/1635.810.49/0.67/1890.331.61/1.84/1837.590.00/0.22/-0.14/0.27/1630.26MDG-a_282.71/3.46/1920.760.77/0.98/1681.610.37/0.52/1879.052.13/2.39/1733.960.00/0.13/-0.12/0.21/1849.73MDG-a_292.11/3.28/1903.370.83/1.04/1835.420.36/0.60/1859.381.84/2.02/1913.920.00/0.13/-0.10/0.19/1780.88MDG-a_302.16/2.99/1820.660.85/0.99/1692.740.38/0.54/1793.72.20/2.25/1867.390.00/0.11/-0.05/0.18/1801.66MDG-a_312.95/3.54/1912.220.94/1.12/1691.170.46/0.68/1789.282.31/2.43/1703.240.00/0.21/-0.20/0.28/1637.96MDG-a_323.09/3.76/1888.870.74/0.91/1663.50.38/0.52/1853.432.86/3.01/1913.130.00/0.15/-0.08/0.17/1739.88MDG-a_332.10/3.29/1908.540.84/1.02/1816.250.39/0.66/1908.271.75/2.38/1960.620.00/0.15/-0.06/0.2/1788.08MDG-a_343.10/3.84/1812.310.90/1.09/1759.610.52/0.64/1840.432.57/2.84/1820.160.00/0.23/-0.13/0.26/1721.00MDG-a_352.73/3.22/1810.680.67/0.98/1661.620.35/0.50/1797.992.45/2.71/1895.510.00/0.15/-0.05/0.15/1827.95MDG-a_362.16/3.54/1838.150.83/0.89/1700.470.38/0.57/1842.451.79/2.35/1715.110.00/0.12/-0.15/0.22/1731.4MDG-a_371.40/2.40/1851.540.84/1.03/1752.650.48/0.62/1833.761.05/1.15/1935.180.00/0.17/-0.13/0.24/1746.95MDG-a_382.50/3.18/1863.120.79/0.89/1769.980.39/0.53/1804.212.19/2.42/1909.010.00/0.18/-0.04/0.16/1806.92MDG-a_392.97/3.7/1901.770.87/1.08/1732.950.51/0.59/1887.261.89/2.64/1874.830.00/0.16/-0.13/0.23/1763.7MDG-a_403.52/3.82/1735.430.84/0.98/1770.490.47/0.51/1819.482.64/2.84/1864.350.00/0.12/-0.10/0.21/1821.44Average2.63/3.4/1862.550.99/1.01/1712.930.43/0.57/1839.952.12/2.43/1867.010.00/0.16/-0.1/0.21/1757.32Note. In Table 13, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution. The symbol “-” denotes the cases when the result is not reported in the literature.From the above experimental results, it can be seen that (1) the average solving efficiency of HA-CCP on all instances is better than all comparison algorithms except NDVNS (because NDVNS does not give the solution time). (2) In terms of solution quality, HA-CCP obtained 58 best average solutions and 30 best solutions on 90 instances, which is better than all comparison algorithms in average results. This shows that HA-CCP has better solution stability. (3) The solution quality of HA-CCP on MDG-a instances is inferior to NDVNS. Therefore, the improvement of HA-CCP combined with NDVNS deserves further study.


### 4.3. Time-to-Target Analysis

To further evaluate the efficiency of the HA-CCP algorithm, we apply the time-to-target (TTT) analysis [37], which identifies the empirical probability distribution of the time required to reach a given objective function value. In this experiment, we choose algorithms with known good performance to compare with HA-CCP: VNS, GVNS, and SGVNS. We used the source code of IVNS (http://www.info.univ-angers.fr/pub/hao/ccp.html), GVNS, and SGVNS (http://www.mi.sanu.ac.rs/∼nenad/ccp/), which can be found online. The instance we chose in the experiment is the same as the test instance in [32], and the objective function value recommended in [32] is used. We carried out TTT experiments under the calculation conditions described in Section 4.2 by executing 100 times on each instance for each algorithm. For each instance/target pair, the running time is sorted in ascending order, and the probability associated with the ith sorted running time ti is pi=i−0.5/100, and the points ti,pi are drawn. Figure 1 shows the experimental results. The abscissa of the figure represents the time-to-target value in seconds (s). The maximum coordinate value of the abscissa is set to a different value to make the comparisons clearer. It can be seen from Figure 1 that in Figures 1(a)–1(f), HA-CCP and SGVNS have similar performance. HA-CCP has the shortest calculation time in the remaining instances.Figure 1
Probability distribution of the time required to reach the value of the objective function. (a) Instance: RanReal240_05 and target:193000. (b) Instance: RanReal240_09 and target: 207700. (c) Instance: RanReal240_16 and target: 202000. (d) Instance: RanReal480_05 and target: 473000. (e) Instance: RanReal480_14 and target: 500. (f) Instance: RanReal480_18 and target: 515000. (g) Instance: RanReal960_02.30 and target: 1380000. (h) Instance: RanReal960_06.30 and target: 1370000. (i) Instance: RanReal960_07.40 and target: 1000000. (j) Instance: RanReal960_05.60 and target: 710000. (k) Instance: MDG-a_23 and target: 360000. (l) Instance: MDG-a_35 and target: 330000.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)


## 4.1. Benchmark Instances and Experimental Setup

We conducted experiments to evaluate HA-CCP on 90 benchmark instances (available at http://www.optsicom.es/ccp and [30]), which is commonly used to evaluate algorithms for CCP (see, for instance, [29–32]). It contains four sets: RanReal240, RanReal480, RanReal960, and MDG-a instances. Table 1 lists the experimental datasets. In the second column, n represents the number of nodes of the instance and p represents the number of clusters.Table 1
Experimental dataset.
Dataset nameFeatureNumber of instancesRanReal240n=240andp=1220RanReal480n=480andp=2020RanReal960n=960and30≤p≤6030MDG-an=2000andp=5020We use the following indicators to measure the advantages of each algorithm:#Best/Avg counted the number of instances where a specific algorithm outperforms the other algorithms in terms of the best and the average objective value.AverageDevbest/Devavg indicates the average percent deviation of a specific algorithm’s best/average result from the best solution obtained in all algorithms participating in the comparison, where Devbest=f∗−fbest/f∗×100 and Devavg=f∗−favg/f∗×100, and fbest is the best result of each algorithm, favg is the average result of each algorithm, and f∗ is the best solution obtained by participating in the comparison of all algorithms.Avg Time recorded the average calculation time (in seconds) required for a particular algorithm to reach its final objective function value.pvaluebest/pvalueavg represents the pvalue of the best/average result obtained through the pairwise Wilcoxon statistical test.Note that, in Section4.2, we use the result of IVNS, GVNS, SGVNS, FITS, and NDVNS present in [31]. The experiments of IVNS, GVNS, SGVNS, and FITS were executed on an Intel E5-2670 Processor (2.8 GHz) with 2 G Byte RAM running under Linux. HA-CCP is implemented in C++, compiled with the g++ compiler using the option “-O3,” and carried out on a server under Ubuntu Linux (version 16.04) with 1 Core of an Intel Xeon (Cascade Lake) Platinum 8269CY 2.5 GHz CPU and 2 G Byte RAM. These results are obtained by running each instance independently 20 times with the running time set to n seconds, where n is the number of nodes in a given instance.The HA-CCP has five parameters: the parameterα used to balance randomness and greed in CM2, the parameter δ that controls the size of the deleted candidate list in DM3, the percentage β of deleted nodes in the candidate list of each cluster, and the upper limit of the number of deleted nodes dmax in DM3 and parameter ε (for skewed moves) in HA-CCP. For α,δ,andβ, we conducted the test experiment on 13 instances with different characteristics in RanReal240, RanReal480, RanReal960, and MDG-a. For α, we keep the other parameters unchanged and change the value of α from 0.2 to 0.8 in steps of 0.2. The best value is obtained when α = 0.6. For δ and β, we use a similar method to obtain δ  = 0.7 and β  = 0.1. The value settings of parameters α,δ,β are consistent with the literature [26], so we did not report the results of this experiment.Fordmax, we test it in the range of {20, 24, 30, 40, 60}. We conducted this experiment on 9 instances with different characteristics in RanReal960 and MDG-a. The statistical results of the experiment are shown in Table 2. In terms of the best objective function value and average objective function value (#Best/Avg), HA-CCP obtains the best value at dmax=24, including obtaining 4 best objective function values and 6 best average values. According to the average percentage deviation (AvgDevbest/Devavg), HA-CCP has the smallest deviation of the best solution obtained when dmax=240.02%/0.15%, and there is not much difference between the parameter values in terms of average time. Therefore, we set dmax=24.Table 2
Bestdmax parameter values identified for HA-CCP.
dmax2024304060#Best/Avg3/34/60/00/00/0p valuebest/p valueavg1.00/0.0040.18/0.0040.004/0.0040.004/0.004Avg Devbest/Devavg (%)0.04/0.180.02/0.150.04/0.190.11/0.240.17/0.29AvgTime (s)1074.011062.571051.711037.851012.09For parameterε, according to [30], ε=0.01. On this basis, we test ε=0.01 and ε=0.005 on 4 instances from RanReal with p≤12 and 13 instances from RanReal240, RanReal480, RanReal960, and MDG-a with p>12. The test results are shown in Tables 3 and 4. On the instances with p≤2, the effect of ε=0.01 is better than ε=0.005. In the other instance, ε=0.005 presents a better effect. Therefore, in instances where the number of clusters is greater than 12, we set ε=0.005, and in other instances, we set ε=0.01.Table 3
Bestε parameter values identified for HA-CCP on the instances with p≤12.
ε0.010.005#Best/Avg4/41/0p valuebest/p valueavg0.25/0.125Avg Devbest/Devavg (%)0.00/0.050.03/0.18AvgTime (s)118.23108.86Table 4
Bestε parameter values identified for HA-CCP on the instances with p>12.
ε0.010.005#Best/Avg2/011/13p valuebest/p valueavg0.022/2.4E − -4Avg Devbest/Devavg (%)0.10/0.240.007/0.16AvgTime (s)807.47837.90


## 4.2. Algorithm Comparison Experiment

To evaluate the performance of HA-CCP, we compared the solution of HA-CCP, IVNS [29], GVNS [30], SGVNS [30], FITS [32], and NDVNS [31]. The instances in the experiment are divided into small and medium instances and large-scale instances.The experimental statistical results on the datasets of small and medium instances (RanReal240 and RanReal480) are shown in Table5. Tables 6 and 7 give detailed results. In Table 5, HA-CCP is better than other algorithms on 19 instances in terms of the best objective function value and has better performance on 36 instances from the average result. According to the average percentage deviation, HA-CCP has the smallest deviation from the best solution obtained in the experiment 0.02%/0.13%. The statistical test shows a significant performance difference between HA-CCP and other comparison algorithms p−value≤0.05, except for the best results of NDVNS.Table 5
Experimental statistical results on RanReal240 and RanReal480.
IVNSGVNSSGVNSFITSNDVNSHA-CPP#Best/Avg3/00/02/18/019/319/36p valuebest/p valueavg3.46E − 07/2.54E − 102.54E − 10/2.54E − 102.47E − 05/1.25E − 82.46E − 04/1.25E − 080.87/7.62E − 08Avg Devbest/Devavg (%)0.17/0.350.35/0.630.08/0.190.09/0.270.03/0.250.02/0.13AvgTime (s)280.01296.66226.89249.39—217.25Note. In Table 5, the symbol “—” denotes the cases when the result is not reported in the literature.Table 6
Comparative results of different algorithms on RanReal240 and RanReal480.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPRanReal240_01224831.56/224571.29224580.56/224207.09224968.01/224769.72224941.48/224802.06224949.51/224689.70225003.70/224897.01RanReal240_02204624.36/204275.49204205.41/203682.12204624.36/204444.31204624.36/204359.38204563.81/204214.81204624.36/204515.06RanReal240_03198861.68/198606.95198472.78/197806.87199059.56/198849.22198954.91/198799.84198976.88/198681.37199079.37/198915.84RanReal240_04225390.88/225069.14225144.59/224463.81225627.16/225389.88225627.16/225364.97225618.17/225185.91225683.17/225346.54RanReal240_05195540.41/195184.84194911.72/194361.91195516.57/195306.51195564.48/195320.28195539.89/195401.63195540.41/195469.00RanReal240_06216713.91/216355.53216383.13/215849.06216733.31/216584.23216747.32/216487.02216747.32/216173.65216730.26/216613.93RanReal240_07209216.90/208992.44209118.64/208329.21209223.34/209080.57209305.70/209029.23209273.70/209063.40209282.88/209150.41RanReal240_08205246.82/204842.79204754.36/204137.78205154.20/204951.2205246.82/204961.05205246.82/205099.31205246.82/205110.51RanReal240_09209142.07/208720.16208702.16/208276.52209007.44/208904.78209159.16/208952.48209186.90/208987.58209057.64/208897.23RanReal240_10192885.48/192598.79192343.75/191874.34193062.60/192842.05192986.21/192811.13192948.92/192523.02193044.16/192954.72RanReal240_11204647.20/204377.08204399.04/203900.12204615.71/204480.92204722.75/204559.39204722.75/204398.23204722.75/204638.07RanReal240_12201028.32/200763.75200822.69/200150.52201076.30/200938.30201117.11/200797.67200978.99/200737.16201117.11/201006.45RanReal240_13202331.20/202027.28201977.87/201356.20202321.58/202198.63202335.99/202139.57202345.12/202276.80202345.48/202285.83RanReal240_14228870.89/228520.04228661.60/228054.32228775.14/228569.78228870.89/228554.78228870.89/228396.82228971.03/228740.72RanReal240_15191152.17/190827.68190575.48/189965.59191238.53/191058.62191255.87/190923.28191263.28/190945.28191243.76/191117.60RanReal240_16204074.95/203668.49203816.48/203270.11203991.53/203649.04204054.99/203710.39204074.95/203918.76204072.57/203961.38RanReal240_17195206.73/194950.57194840.79/194404.70195423.83/195241.19195561.36/195243.32195509.13/195236.75195393.97/195278.93RanReal240_18194916.37/194704.23194915.62/194114.09195120.98/194967.73195100.39/194872.13195167.14/194886.16195167.14/195069.80RanReal240_19199200.03/198905.05198828.82/198119.14199307.33/199093.86199225.98/199040.43199216.46/198895.83199307.33/199204.90RanReal240_20212264.10/211871.74211984.80/211458.51212268.46/212037.43212268.52/212049.85212323.22/212130.13212229.46/212111.19RanReal480_01554337.23/553795.85553224.53/552326.59555430.60/554994.68555489.92/554376.54556639.68/555566.55556126.86/555338.06RanReal480_02510066.41/509058.46508711.62/507540.62510718.79/510304.78511280.50/509757.15511666.95/510495.78511566.55/510924.27RanReal480_03496334.51/495409.98495140.23/493706.92497725.86/496785.80497295.19/496059.50497846.57/495871.46498028.54/497109.59RanReal480_04521669.00/520051.55520653.34/519051.60522572.81/521952.28522305.16/521062.13522748.49/520295.34522790.22/521999.31RanReal480_05483670.19/482390.51481803.95/480508.80483819.77/482603.84484084.66/482867.74484742.51/482831.18485138.44/484092.59RanReal480_06533589.61/532462.25532702.72/531627.12534515.67/533916.00533991.27/533036.36535503.61/533138.78534961.79/534114.47RanReal480_07545343.81/544060.83544445.60/542318.56545812.49/545302.82545470.73/544651.12546951.97/545548.47546503.90/545582.87RanReal480_08531974.48/531023.25531287.92/529525.39532736.12/532109.62532417.42/531667.91533098.56/531631.32532891.23/532161.08RanReal480_09555604.38/554820.43555163.27/553394.39556865.18/556081.91556868.85/555634.40557283.90/555998.60557120.25/556265.26RanReal480_10519066.57/518412.32517431.34/516228.20520014.70/518024.16520257.54/518071.71520481.15/518812.29520492.06/519891.18RanReal480_11523463.33/522201.99522626.50/521218.97524124.60/523508.02523991.29/522816.94524059.91/522416.53524669.99/523760.48RanReal480_12501462.57/500055.30499914.17/498596.97502570.10/501632.20501915.56/500776.79502656.68/501171.81503359.96/502069.60RanReal480_13534294.24/533478.80533672.27/532322.68535411.94/534651.24535025.51/533823.79535633.80/533605.55535251.73/534707.51RanReal480_14513186.65/512501.71512764.33/511212.78514537.52/513935.11514107.62/513053.25514696.90/512600.42515476.42/514801.49RanReal480_15516657.20/515416.17515607.47/514465.20518029.18/517189.00517205.02/516018.38518605.32/516455.65518370.90/517283.29RanReal480_16549230.25/548274.66549033.57/547075.83549840.64/549253.54549552.63/548462.13550482.48/549108.44550317.71/549881.85RanReal480_17537223.44/536149.06536402.45/534770.20537993.79/537568.15537924.55/536745.39538331.26/536829.04538745.70/537826.26RanReal480_18525490.09/524515.11524631.54/522908.72526349.49/525453.50525822.76/524712.42526466.23/523932.37526314.82/525702.47RanReal480_19522280.40/521442.89521672.59/519720.44522757.15/522218.13522316.22/521267.22523219.84/522114.62522958.23/522365.10RanReal480_20518436.63/516935.15516488.64/515450.41518847.01/518202.52518349.10/517430.77519492.21/518475.86519277.92/518518.27#Best3/00/02/18/019/319/36p Value3.46E − 07/2.54E – 102.54E − 10/2.54E − 102.47E − 05/1.25E − 082.46E − 04/1.25E − 080.87/7.62E − 08Note. In Table 6, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 7
Devbest, Devavg, and average time of different algorithms on RanReal240 and RanReal480.
Instance nameIVNSGVNSSGVNSFITSDNVNSHA-CCPRanReal240_010.08/0.19/155.570.19/0.35/155.920.02/0.10/127.160.03/0.09/149.090.02/0.14/-0.00/0.05/127.88RanReal240_020.00/0.17/184.440.2/0.46/159.560.00/0.09/158.200.00/0.13/150.750.03/0.20/-0.00/0.05/111.58RanReal240_030.11/0.24/186.060.3/0.64/164.110.01/0.12/139.260.06/0.14/169.950.05/0.20/-0.00/0.08/135.66RanReal240_040.13/0.27/159.700.24/0.54/175.000.02/0.13/137.870.02/0.14/118.580.03/0.22/-0.00/0.15/124.67RanReal240_050.01/0.19/155.020.33/0.61/179.730.02/0.13/136.480.00/0.12/132.330.01/0.08/-0.01/0.05/135.27RanReal240_060.02/0.18/174.510.17/0.41/187.590.01/0.08/126.610.00/0.12/155.990.00/0.26/-0.01/0.06/129.28RanReal240_070.04/0.15/160.670.09/0.47/195.330.04/0.11/144.350.00/0.13/144.960.02/0.12/-0.01/0.07/127.25RanReal240_080.00/0.20/145.940.24/0.54/193.880.05/0.14/122.790.00/0.14/124.220.00/0.07/-0.00/0.07/112.98RanReal240_090.02/0.22/194.360.23/0.44/171.090.09/0.13/136.240.01/0.11/141.690.00/0.10/-0.06/0.14/98.89RanReal240_100.09/0.24/183.490.37/0.62/145.390.00/0.11/162.770.04/0.13/134.200.06/0.28/-0.01/0.06/111.58RanReal240_110.04/0.17/157.980.16/0.40/155.120.05/0.12/136.250.00/0.08/129.910.00/0.16/-0.00/0.04/125.15RanReal240_120.04/0.18/186.710.15/0.48/157.430.02/0.09/123.130.00/0.16/132.030.07/0.19/-0.00/0.06/108.32RanReal240_130.01/0.16/173.460.18/0.49/171.440.01/0.07/127.250.00/0.10/131.340.00/0.03/-0.00/0.03/139.97RanReal240_140.04/0.20/147.560.14/0.40/164.870.09/0.18/112.270.04/0.18/135.870.04/0.25/-0.00/0.10/122.04RanReal240_150.06/0.23/167.880.36/0.68/188.750.01/0.11/154.190.00/0.18/131.830.00/0.17/-0.01/0.08/101.57RanReal240_160.00/0.20/165.220.13/0.39/181.820.04/0.21/130.930.01/0.18/89.110.00/0.08/-0.00/0.06/102.24RanReal240_170.18/0.31/171.750.37/0.59/179.250.07/0.16/149.060.00/0.16/171.030.03/0.17/-0.09/0.14/132.10RanReal240_180.13/0.24/154.600.13/0.54/169.520.02/0.10/167.150.03/0.15/152.830.00/0.14/-0.00/0.05/110.87RanReal240_190.05/0.20/173.650.24/0.60/179.990.00/0.11/140.210.04/0.13/98.090.05/0.21/-0.00/0.05/121.71RanReal240_200.03/0.21/188.640.16/0.41/175.520.03/0.13/112.330.03/0.13/115.380.00/0.09/-0.04/0.10/99.55RanReal480_010.41/0.51/391.120.61/0.77/419.980.22/0.30/301.250.21/0.41/340.600.00/0.19/-0.09/0.23/349.71RanReal480_020.31/0.51/403.380.58/0.81/414.240.19/0.27/293.360.08/0.37/355.590.00/0.23/-0.02/0.15/330.24RanReal480_030.34/0.53/420.240.58/0.87/427.120.06/0.25/331.810.15/0.40/352.060.04/0.43/-0.00/0.18/332.28RanReal480_040.21/0.52/383.190.41/0.72/428.090.04/0.16/332.130.09/0.33/399.510.01/0.48/-0.00/0.15/329.59RanReal480_050.30/0.57/417.550.69/0.95/448.150.27/0.52/325.050.22/0.47/335.840.08/0.48/-0.00/0.22/301.91RanReal480_060.36/0.57/393.370.52/0.72/428.170.18/0.30/300.770.28/0.46/390.060.00/0.44/-0.10/0.26/280.00RanReal480_070.29/0.53/395.010.46/0.85/423.310.21/0.30/342.070.27/0.42/390.230.00/0.26/-0.08/0.25/285.02RanReal480_080.21/0.39/388.450.34/0.67/398.320.07/0.19/356.390.13/0.27/380.640.00/0.28/-0.04/0.18/283.23RanReal480_090.30/0.44/376.210.38/0.70/421.610.08/0.22/350.350.07/0.30/383.670.00/0.23/-0.03/0.18/255.35RanReal480_100.27/0.40/383.710.59/0.82/428.060.09/0.47/300.430.05/0.47/328.850.00/0.32/-0.00/0.12/307.38RanReal480_110.23/0.47/383.910.39/0.66/421.150.10/0.22/320.080.13/0.35/383.650.12/0.43/-0.00/0.17/299.74RanReal480_120.38/0.66/397.430.68/0.95/409.110.16/0.34/270.860.29/0.51/347.320.14/0.43/-0.00/0.26/349.86RanReal480_130.25/0.40/404.230.37/0.62/390.760.04/0.18/327.700.11/0.34/330.840.00/0.38/-0.07/0.17/333.59RanReal480_140.44/0.58/405.040.53/0.83/419.870.18/0.30/319.140.27/0.47/352.070.15/0.56/-0.00/0.13/340.90RanReal480_150.38/0.61/384.960.58/0.80/418.770.11/0.27/313.910.27/0.50/387.020.00/0.41/-0.05/0.25/282.23RanReal480_160.23/0.40/345.110.26/0.62/419.820.12/0.22/301.160.17/0.37/392.780.00/0.25/-0.03/0.11/294.16RanReal480_170.28/0.48/386.160.43/0.74/411.520.14/0.22/320.590.15/0.37/360.930.08/0.36/-0.00/0.17/336.43RanReal480_180.19/0.37/368.200.35/0.68/431.300.02/0.19/278.260.12/0.33/320.600.00/0.48/-0.03/0.15/330.79RanReal480_190.18/0.34/400.780.30/0.67/435.580.09/0.19/306.800.17/0.37/380.690.00/0.21/-0.05/0.16/343.32RanReal480_200.20/0.49/385.300.58/0.78/420.080.12/0.25/339.090.22/0.40/353.520.00/0.20/-0.04/0.19/345.87Average0.17/0.35/280.010.35/0.63/296.660.08/0.19/226.890.09/0.27/249.390.03/0.25/-0.02/0.13/217.25Note. In Table 7, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution. The symbol “-” denotes the cases when the result is not reported in the literature.The experimental statistical results on the dataset of large-scale instances (RanReal960) are shown in Table8. The detailed results are given in Tables 9 and 10. According to Table 8, HA-CCP has obvious advantages in average results. It obtained 20 best average results out of 30 instances and 11 best results. HA-CCP surpasses other comparison algorithms in terms of the average percent deviation of average result from best-found solutions (AvgeDevavg=0.19). The pvaluebest/pvalueavg row shows a statistically significant difference in performance between HA-CCP and all the reference algorithms except NDVNS.Table 8
Experimental statistical results on RanReal960.
IVNSGVNSSGVNSFITSNDVNSHA-CPP#Best/Avg0/00/00/01/218/1011/18p valuebest/p valueavg4.32E − 08/4.32E − 084.32E − 08/4.32E − 084.32E − 08/4.32E − 081.18E − 05/1.18E − 050.14/0.07Avg Devbest/Devavg (%)0.81/1.020.81/1.120.19/0.390.52/0.620.04/0.240.04/0.19AvgTime (s)843.9862.2840.91893.11—723.82Note. In Table 8, the symbol “—” denotes the cases when the result is not reported in the literature.Table 9
Comparative results of different algorithms on RanReal960.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPRanReal960_01.301331323.28/1329095.101331996.73/1328415.401337853.23/1335679.541333878.00/1332712.781340369.47/1338452.931339904.73/1337999.56RanReal960_02.301426870.24/1423903.721427037.60/1422960.001433071.63/1430808.901434529.49/1433886.301435819.84/1433258.341435087.46/1433503.63RanReal960_03.301390084.19/1387508.881390367.98/1386753.981395846.80/1394012.261392101.18/1390924.211398554.78/1397154.111397520.91/1396135.59RanReal960_04.301407607.65/1405972.041406916.02/1403198.731413478.82/1410438.071414344.67/1412460.011414919.86/1412464.181413878.60/1411928.57RanReal960_05.301363405.33/1360883.591362240.30/1359314.241370560.76/1367959.841365975.96/1365612.741372686.88/1370958.721371391.13/1369452.03RanReal960_06.301413074.62/1409803.61410969.99/1408670.371417338.38/1415708.821413476.58/1412750.081420632.38/1419467.401420942.81/1418222.26RanReal960_07.301332205.25/1329503.041332748.04/1329170.211339735.87/1337029.011334504.35/1334263.931341829.68/1340275.061341640.99/1340054.65RanReal960_08.301462280.35/1458524.761460407.11/1457531.521466738.95/1464441.531463737.39/1462602.721469545.99/1466830.821467330.75/1465505.59RanReal960_09.301378445.37/1376305.911380206.02/1374713.941385287.77/1382960.301381577.32/1379280.981387514.11/1385397.311385795.46/1384258.20RanReal960_10.301377646.33/1374311.231377009.66/1373790.241384154.95/1381870.761379905.83/1378772.671386801.94/1384724.791384935.52/1383811.91RanReal960_01.401034548.05/1031462.281032872.42/1030512.991041148.42/1038487.541035642.67/1034626.821042735.72/1040717.991042362.60/1041082.27RanReal960_02.401108588.66/1106671.471109086.02/1106469.641115789.54/1113937.771110547.59/1110074.361117471.02/1115602.031117552.44/1115723.68RanReal960_03.401081509.08/1079553.821080281.13/1077244.611086488.77/1085060.191083240.15/1082948.771089012.05/1087325.531088964.98/1087568.20RanReal960_04.401096347.39/1092785.741096438.26/1091633.051100866.71/1098759.101103897.12/1101073.371102222.98/1100256.111101734.58/1100608.60RanReal960_05.401056103.80/1054445.691057478.73/1054478.201063682.56/1062213.711059158.09/1058478.461066415.88/1064390.341066157.77/1065037.50RanReal960_06.401096895.36/1095721.541099861.44/1093932.851104590.22/1102651.281100368.74/1100064.661107955.38/1105069.061107485.89/1105353.87RanReal960_07.401034299.55/1032667.931035241.97/1031362.331041064.58/1038879.341043376.95/1039933.231043921.14/1041464.081043176.75/1042209.24RanReal960_08.401137464.75/1136002.241136567.63/1133556.701142282.86/1141171.701139865.05/1138054.461144615.34/1141877.821143818.84/1142790.55RanReal960_09.401068288.24/1066496.301068892.92/1066427.061076229.18/1073798.911072116.14/1071426.071076786.59/1075606.231076536.88/1074554.12RanReal960_10.401069556.59/1067889.461069985.94/1067548.971077400.98/1074400.361072919.65/1071480.211079212.31/1077123.001078818.14/1077728.42RanReal960_01.60726465.37/724244.42725912.84/723156.84732096.63/730601.10727690.58/727222.73733900.43/731787.78733960.17/732785.75RanReal960_02.60770060.9/768413.74770477.46/768062.71776289.95/775060.74773921.97/772572.49776085.50/774619.17777733.23/776084.26RanReal960_03.60753090.65/751419.9753094.36/750898.37760248.25/758432.10756677.95/755442.64760728.09/758924.49761312.30/760046.12RanReal960_04.60762952.42/761387.83763837.98/760835.94769112.25/767780.08765253.27/764696.30770170.61/768057.59769559.96/768476.28RanReal960_05.60741248.79/739443.77741932.85/738830.28748581.43/746014.20743715.56/743165.17748244.40/747006.91749316.68/747647.96RanReal960_06.60761947.94/760369.56762260.95/759048.94767679.61/765628.88763029.06/761957.51768180.66/765223.34769233.87/767971.96RanReal960_07.60723439.86/721167.69723786.02/720360.15728827.33/727427.19725993.23/725733.17731064.84/728984.94732249.82/730484.07RanReal960_08.60789552.19/786344.58787775.07/785553.15794363.93/792538.90791334.42/790285.98794354.56/791262.07795313.86/793390.82RanReal960_09.60747509.96/745313.38746710.78/744341.99753943.93/751871.94750858.18/749209.83754578.20/753033.20754811.24/753473.44RanReal960_10.60748812.21/746701.78747565.74/745004.51754666.01/752583.88749883.45/748985.05755076.90/753154.35756020.38/754733.58#Best0/00/00/01/218/1011/18p value4.32E − 08/4.32E − 084.32E − 08/4.32E − 084.32E − 08/4.32E − 081.18E − 05/1.18E − 050.14/0.07Note. In Table 9, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 10
Devbest, Devavg, and average time of different algorithms on RanReal960.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPRanReal960_01.300.67/0.84/918.260.62/0.89/811.540.19/0.35/856.210.48/0.57/915.530/0.14/-0.03/0.18/720.64RanReal960_02.300.62/0.83/797.610.61/0.90/842.950.19/0.35/835.980.09/0.13/904.230/0.18/-0.05/0.16/731.68RanReal960_03.300.61/0.79/883.410.59/0.84/860.630.19/0.32/829.850.46/0.55/836.810/0.1/-0.07/0.17/673.02RanReal960_04.300.52/0.63/919.960.57/0.83/832.990.10/0.32/822.400.04/0.17/929.490/0.17/-0.07/0.21/780.14RanReal960_05.300.68/0.86/804.130.76/0.97/883.850.15/0.34/840.420.49/0.52/957.250/0.13/-0.09/0.24/686.23RanReal960_06.300.55/0.78/857.850.70/0.86/801.300.25/0.37/834.760.53/0.58/935.810.02/0.1/-0.00/0.19/777.19RanReal960_07.300.72/0.92/875.580.68/0.94/850.220.16/0.36/816.600.55/0.56/894.980/0.12/-0.01/0.13/769.18RanReal960_08.300.49/0.75/804.150.62/0.82/822.220.19/0.35/831.190.40/0.47/948.470/0.18/-0.15/0.27/686.39RanReal960_09.300.65/0.81/815.060.53/0.92/863.400.16/0.33/812.810.43/0.59/884.890/0.15/-0.12/0.23/641.61RanReal960_10.300.66/0.9/878.660.71/0.94/850.020.19/0.36/792.140.50/0.58/897.680/0.15/-0.13/0.22/775.20RanReal960_01.400.79/1.08/877.730.95/1.17/847.870.15/0.41/832.620.68/0.78/913.510/0.19/-0.04/0.16/724.70RanReal960_02.400.8/0.97/824.060.76/0.99/876.230.16/0.32/830.260.63/0.67/938.570.01/0.17/-0.00/0.16/689.19RanReal960_03.400.69/0.87/905.640.80/1.08/850.330.23/0.36/816.430.53/0.56/829.180/0.15/-0.00/0.13/726.02RanReal960_04.400.68/1.01/800.470.68/1.11/904.060.27/0.47/761.940.00/0.26/931.930.15/0.33/-0.20/0.30/737.53RanReal960_05.400.97/1.12/826.350.84/1.12/857.740.26/0.39/803.470.68/0.74/882.950/0.19/-0.02/0.13/737.69RanReal960_06.401.00/1.10/876.400.73/1.27/835.260.30/0.48/840.430.68/0.71/795.610/0.26/-0.04/0.23/764.48RanReal960_07.400.92/1.08/882.220.83/1.20/884.530.27/0.48/871.150.05/0.38/891.650/0.24/-0.07/0.16/796.50RanReal960_08.400.62/0.75/807.240.70/0.97/851.960.20/0.30/827.890.42/0.57/884.170/0.24/-0.07/0.16/711.17RanReal960_09.400.79/0.96/818.160.73/0.96/878.540.05/0.28/847.560.43/0.50/873.440/0.11/-0.02/0.21/716.20RanReal960_10.400.89/1.05/872.900.85/1.08/863.940.17/0.45/860.780.58/0.72/943.530/0.19/-0.04/0.14/689.14RanReal960_01.601.02/1.32/789.021.10/1.47/901.120.25/0.46/907.890.85/0.92/901.040.01/0.3/-0.00/0.16/751.24RanReal960_02.600.99/1.20/826.250.93/1.24/874.070.19/0.34/873.060.49/0.66/887.610.21/0.4/-0.00/0.21/687.37RanReal960_03.601.08/1.30/808.811.08/1.37/852.820.14/0.38/873.260.61/0.77/923.810.08/0.31/-0.00/0.17/658.15RanReal960_04.600.94/1.14/853.850.82/1.21/830.990.14/0.31/839.140.64/0.71/819.90/0.27/-0.08/0.22/723.40RanReal960_05.601.08/1.32/831.310.99/1.40/895.340.10/0.44/868.220.75/0.82/889.580.14/0.31/-0.00/0.22/691.55RanReal960_06.600.95/1.15/766.030.91/1.32/872.940.20/0.47/836.760.81/0.95/864.120.14/0.52/-0.00/0.16/727.95RanReal960_07.601.20/1.51/918.061.16/1.62/909.030.47/0.66/878.590.85/0.89/875.950.16/0.45/-0.00/0.24/680.08RanReal960_08.600.72/1.13/851.600.95/1.23/911.420.12/0.35/859.760.50/0.63/870.010.12/0.51/-0.00/0.24/761.94RanReal960_09.600.97/1.26/770.731.07/1.39/849.730.11/0.39/868.300.52/0.74/900.640.03/0.24/-0.00/0.18/740.51RanReal960_10.600.95/1.23/855.351.12/1.46/898.950.18/0.45/857.380.81/0.93/870.890.12/0.38/-0.00/0.17/758.65Average0.81/1.02/843.90.81/1.12/862.20.19/0.39/840.910.52/0.62/893.110.04/0.24/-0.04/0.19/723.82Note. In Table 10, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution. The symbol “-” denotes the cases when the result is not reported in the literature.The experimental statistical results on the dataset of large-scale instances (MDG-a) are presented in Table11. Tables 12 and 13 give detailed results. It can be seen from Table 7 that NDVNS has obvious advantages in solution quality, but HA-CCP is better than other algorithms (such as IVNS, GVNS, SGVNS, and FITS), which is also proved by the results of statistical testing.Table 11
Experimental statistical results on the MDG-a.
IVNSGVNSSGVNSFITSNDVNSHA-CPP#Best/Avg0/00/00/00/020/160/4p valuebest/p valueavg7.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/0.01AvgDevbest/Devavg (%)2.63/3.40.99/1.010.43/0.572.12/2.430.00/0.160.1/0.21AvgTime (s)1862.551712.931839.951867.01-1757.32Note. In Table 11, the symbol “-” denotes the cases when the result is not reported in the literature.Table 12
Comparative results of different algorithms on the MDG-a.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPMDG-a_21379241.00/376249.80388647.00/387189.20389269.00/389208.15383164.00/382387.05391259.00/390647.15390987.00/390660.00MDG-a_22380665.00/377418.75384487.00/384018.35386354.00/386007.50380817.00/380489.60388476.00/387718.60387838.00/387393.10MDG-a_23375697.00/374941.20386154.00/385489.20387267.00/387019.40380630.00/379334.85389363.00/388908.60389071.00/388611.10MDG-a_24378258.00/376540.75387095.00/386473.15388423.00/388008.45381783.00/380560.55390269.00/389655.40390051.00/389525.40MDG-a_25389242.00/384685.70387121.00/395749.55398108.00/397471.50390623.00/386346.05399478.00/399002.40399215.00/398869.20MDG-a_26392407.00/389113.50396756.00/400015.60402135.00/401471.95393222.00/392916.10403457.00/402740.95403425.00/402759.75MDG-a_27375566.00/373113.95380243.00/379248.65381896.00/381208.70377617.00/376721.60383780.00/382951.05383246.00/382731.55MDG-a_28378486.00/375546.50386018.00/385207.20387594.00/387004.55380748.00/379732.95389025.00/388516.50388553.00/388208.60MDG-a_29377175.00/372663.75382108.00/381301.50383937.00/383008.55378239.00/377540.40385316.00/384816.05384933.00/384588.45MDG-a_30389615.00/386318.15394817.00/394281.50396678.00/396041.70389452.00/389254.10398211.00/397776.80398004.00/397503.15MDG-a_31376920.00/374627.70384718.00/384018.25386587.00/385749.40379407.00/378922.70388375.00/387562.05387609.00/387276.55MDG-a_32382405.00/379790.40391693.00/391004.60393098.00/392578.60383333.00/382737.35394611.00/394031.35394290.00/393941.40MDG-a_33377689.00/373096.60382576.00/381876.80384291.00/383273.45379047.00/376641.80385806.00/385212.70385583.00/385036.20MDG-a_34384412.00/381472.65393135.00/392409.55394676.00/394176.80386544.00/385459.25396725.00/395823.10396214.00/395706.85MDG-a_35385251.00/383302.15393384.00/392174.20394687.00/394059.40386347.00/385302.60396054.00/395455.20395848.00/395472.25MDG-a_36394867.00/389332.30400271.00/400019.40402087.00/401287.65396368.00/394103.05403604.00/403111.10402998.00/402698.45MDG-a_37384811.00/380906.40387006.00/386276.45388411.00/387875.60386195.00/385797.30390289.00/389612.25389769.00/389349.00MDG-a_38387472.00/384752.55394264.00/393879.15395865.00/395287.90388712.00/387807.15397407.00/396710.05397249.00/396775.25MDG-a_39381738.00/378840.90390008.00/389147.50391415.00/391074.95385975.00/383036.10393415.00/392799.15392913.00/392506.70MDG-a_40392751.00/391517.70403662.00/403108.90405184.00/405008.90396321.00/395505.80407084.00/406615.75406672.00/406245.60#Best0/00/00/00/020/160/4p Value7.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74E − 067.74E − 06/7.74e-067.74E-06/0.01Note. In Table 12, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 13
Devbest, Devavg, and average time of different algorithms on the MDG-a.
Instance nameIVNSGVNSSGVNSFITSNDVNSHA-CCPMDG-a_213.07/3.84/1938.050.67/1.04/1518.30.51/0.52/1867.832.07/2.27/1872.280.00/0.16/-0.07/0.15/1765.62MDG-a_222.01/2.85/1840.871.03/1.15/1806.640.55/0.64/1801.351.97/2.06/1931.750.00/0.19/-0.16/0.28/1719.05MDG-a_233.51/3.7/1868.530.82/0.99/1741.740.54/0.60/1839.262.24/2.58/1937.180.00/0.12/-0.07/0.19/1773.65MDG-a_243.08/3.52/1892.930.81/0.97/1697.710.47/0.58/1830.542.17/2.49/1903.310.00/0.16/-0.06/0.19/1807.82MDG-a_252.56/3.7/1829.423.09/0.93/1663.950.34/0.50/1870.122.22/3.29/1824.790.00/0.12/-0.07/0.15/1731.29MDG-a_262.74/3.56/1923.601.66/0.85/1665.890.33/0.49/1790.92.54/2.61/1926.980.00/0.18/-0.01/0.17/1701.12MDG-a_272.14/2.78/1790.230.92/1.18/1635.810.49/0.67/1890.331.61/1.84/1837.590.00/0.22/-0.14/0.27/1630.26MDG-a_282.71/3.46/1920.760.77/0.98/1681.610.37/0.52/1879.052.13/2.39/1733.960.00/0.13/-0.12/0.21/1849.73MDG-a_292.11/3.28/1903.370.83/1.04/1835.420.36/0.60/1859.381.84/2.02/1913.920.00/0.13/-0.10/0.19/1780.88MDG-a_302.16/2.99/1820.660.85/0.99/1692.740.38/0.54/1793.72.20/2.25/1867.390.00/0.11/-0.05/0.18/1801.66MDG-a_312.95/3.54/1912.220.94/1.12/1691.170.46/0.68/1789.282.31/2.43/1703.240.00/0.21/-0.20/0.28/1637.96MDG-a_323.09/3.76/1888.870.74/0.91/1663.50.38/0.52/1853.432.86/3.01/1913.130.00/0.15/-0.08/0.17/1739.88MDG-a_332.10/3.29/1908.540.84/1.02/1816.250.39/0.66/1908.271.75/2.38/1960.620.00/0.15/-0.06/0.2/1788.08MDG-a_343.10/3.84/1812.310.90/1.09/1759.610.52/0.64/1840.432.57/2.84/1820.160.00/0.23/-0.13/0.26/1721.00MDG-a_352.73/3.22/1810.680.67/0.98/1661.620.35/0.50/1797.992.45/2.71/1895.510.00/0.15/-0.05/0.15/1827.95MDG-a_362.16/3.54/1838.150.83/0.89/1700.470.38/0.57/1842.451.79/2.35/1715.110.00/0.12/-0.15/0.22/1731.4MDG-a_371.40/2.40/1851.540.84/1.03/1752.650.48/0.62/1833.761.05/1.15/1935.180.00/0.17/-0.13/0.24/1746.95MDG-a_382.50/3.18/1863.120.79/0.89/1769.980.39/0.53/1804.212.19/2.42/1909.010.00/0.18/-0.04/0.16/1806.92MDG-a_392.97/3.7/1901.770.87/1.08/1732.950.51/0.59/1887.261.89/2.64/1874.830.00/0.16/-0.13/0.23/1763.7MDG-a_403.52/3.82/1735.430.84/0.98/1770.490.47/0.51/1819.482.64/2.84/1864.350.00/0.12/-0.10/0.21/1821.44Average2.63/3.4/1862.550.99/1.01/1712.930.43/0.57/1839.952.12/2.43/1867.010.00/0.16/-0.1/0.21/1757.32Note. In Table 13, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution. The symbol “-” denotes the cases when the result is not reported in the literature.From the above experimental results, it can be seen that (1) the average solving efficiency of HA-CCP on all instances is better than all comparison algorithms except NDVNS (because NDVNS does not give the solution time). (2) In terms of solution quality, HA-CCP obtained 58 best average solutions and 30 best solutions on 90 instances, which is better than all comparison algorithms in average results. This shows that HA-CCP has better solution stability. (3) The solution quality of HA-CCP on MDG-a instances is inferior to NDVNS. Therefore, the improvement of HA-CCP combined with NDVNS deserves further study.


## 4.3. Time-to-Target Analysis

To further evaluate the efficiency of the HA-CCP algorithm, we apply the time-to-target (TTT) analysis [37], which identifies the empirical probability distribution of the time required to reach a given objective function value. In this experiment, we choose algorithms with known good performance to compare with HA-CCP: VNS, GVNS, and SGVNS. We used the source code of IVNS (http://www.info.univ-angers.fr/pub/hao/ccp.html), GVNS, and SGVNS (http://www.mi.sanu.ac.rs/∼nenad/ccp/), which can be found online. The instance we chose in the experiment is the same as the test instance in [32], and the objective function value recommended in [32] is used. We carried out TTT experiments under the calculation conditions described in Section 4.2 by executing 100 times on each instance for each algorithm. For each instance/target pair, the running time is sorted in ascending order, and the probability associated with the ith sorted running time ti is pi=i−0.5/100, and the points ti,pi are drawn. Figure 1 shows the experimental results. The abscissa of the figure represents the time-to-target value in seconds (s). The maximum coordinate value of the abscissa is set to a different value to make the comparisons clearer. It can be seen from Figure 1 that in Figures 1(a)–1(f), HA-CCP and SGVNS have similar performance. HA-CCP has the shortest calculation time in the remaining instances.Figure 1
Probability distribution of the time required to reach the value of the objective function. (a) Instance: RanReal240_05 and target:193000. (b) Instance: RanReal240_09 and target: 207700. (c) Instance: RanReal240_16 and target: 202000. (d) Instance: RanReal480_05 and target: 473000. (e) Instance: RanReal480_14 and target: 500. (f) Instance: RanReal480_18 and target: 515000. (g) Instance: RanReal960_02.30 and target: 1380000. (h) Instance: RanReal960_06.30 and target: 1370000. (i) Instance: RanReal960_07.40 and target: 1000000. (j) Instance: RanReal960_05.60 and target: 710000. (k) Instance: MDG-a_23 and target: 360000. (l) Instance: MDG-a_35 and target: 330000.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)


## 5. Analysis of the Main Components of HA-CCP

In this section, we have studied the contribution of the main components of HA-CCP to performance. We give experimental results from four aspects: “construct solution,” “destruct partial solution,” “destruct and reconstruct partial solution,” and “acceptance criterion for skew” to show that the method used in HA-CCP is better. All experiments in this section were performed under the experimental conditions described in Section 4.1.


### 5.1. Benefit of CM2

In HA-CCP, CM2 is first used to construct the initial feasible solution (Algorithm 2, line 2) and then reconstruct the solution in the iterative process (Algorithm 2, line 9). Different from CM [26] and random construction method (RCM, used in [29, 31, 32]), CM2 can increase the probability of constructing a feasible solution when the upper and lower bounds are tighter and improve the performance of HA-CCP. Therefore, we conducted comparative experiments in the following two aspects.First, we compared the success rate of constructing the initial feasible solution between RCM and CM2 under different upper and lower bound constraints on 10 RanReal960 instances withp=60. In the experiment, the upper and lower bounds Ug and Lg of the instance are adjusted to Ug′=s2×Ug and Lg′=s1×Lg, respectively. Obviously, s2<1 and s1>1 will tighten the constraints of CCP. For each instance, RCM and CM2 are run 100 times under the new upper and lower bound constraints, respectively, and the success rate of obtaining the initial solution is shown in Table 14. The “average” row indicates the average value of the construction success rate of all the test instances.Table 14
Success rate of RCM and CM2 in constructing initial feasible solution on RanReal960 instances withp=60.
Instance name(1.30, 1)(1.28, 1)(1.27, 1)(1, 1)(1, 0.94)(1, 0.93)(1, 0.92)RanReal960_01.60100%/100%100%/100%100%/100%100%/100%85%/100%0%/100%0%/100%RanReal960_02.6097%/100%100%/100%100%/100%100%/100%100%/100%100%/100%90%/100%RanReal960_03.60100%/100%100%/100%100%/100%100%/100%100%/100%100%/100%20%/100%RanReal960_04.601%/14%100%/100%100%/100%100%/100%100%/100%100%/100%100%/100%RanReal960_05.60100%/100%100%/100%100%/100%100%/100%100%/100%64%/100%0%/100%RanReal960_06.60100%/100%100%/100%100%/100%100%/100%34%/100%0%/100%0%/0%RanReal960_07.60100%/100%100%/100%100%/100%100%/100%0%/100%0%/0%0%/0%RanReal960_08.600%/0%71%/95%79%/98%100%/100%100%/100%100%/100%100%/100%RanReal960_09.60100%/100%100%/100%100%/100%100%/100%100%/100%100%/100%89%/100%RanReal960_10.60100%/100%100%/100%100%/100%100%/100%64%/100%0%/100%0%/100%Average79.8%/81.4%97.1%/99.5%97.9%/99.8%100%/100%78.3%/100%56.4%/90%39.9%/80%Note. In Table 14, s1 and s2 in s1,s2, respectively, denote the scaling ratios of the lower and upper bounds of the cluster capacity. A and B in A/B, respectively, represent the initial solution construction success rate obtained using RCM and CM2.We can see from Table 14 that if the upper and lower bounds of the cluster capacity become stricter, the success rate of RCM and CM2 in constructing the initial solution decreases, but the success rate of CM2 is higher than that of RCM. From the average point of view, the success rate of CM2 in the experiment is higher than that of RCM, even as high as 2 times (the last column of Table14). Therefore, CM2 has better usability than RCM, and it can construct feasible solutions in tighter constrained CCPs.Secondly, we use RCM to replace CM2 in HA-CCP (denoted as HA-CCP-RCM) for comparison experiments with HA-CCP. The experiment was conducted on the same 10 instances as Section4.3, and each instance was run 20 times. Table 15 summarizes the comparison results, and Tables 16 and 17 give detailed results. It can be seen from Table 15 that when the average calculation time is almost the same, HA-CCP with CM2 can obtain more best solution and best average solution. Therefore, CM2 can effectively improve the CCP solution quality.Table 15
Statistical comparison results of HA-CCP-RCM and HA-CCP.
HA-CCP-RCMHA-CCP#Best/Avg4/48/8p valuebest/p valueavg0.39/0.39Avg Devbest/Devavg (%)0.04/0.140.01/0.13AvgTime (s)650.18659.04Table 16
Comparative results of HA-CCP-RCM and HA-CCP.
Instance nameHA-CCP-RCMHA-CCPRanReal240_05195558.15/195472.31195540.41/195469.00RanReal240_09209186.90/208970.18209057.64/208897.23RanReal240_16204063.69/203943.95204072.57/203961.38RanReal480_05484845.80/484337.08485138.44/484092.59RanReal480_14515313.22/514565.40515476.42/514801.49RanReal480_18526331.30/525686.10526314.82/525702.47RanReal960_02.301434083.69/1432684.791435087.46/1433503.63RanReal960_05.60748689.45/747833.47749316.68/747647.96RanReal960_06.301419623.57/1418217.771420942.81/1418222.26RanReal960_07.401043459.88/1041763.791043176.75/1042209.24MDG-a_23388753.00/388437.80389071.00/388611.10MDG-a_35395692.00/395378.35395848.00/395472.25#Best4/48/8p Value0.39/0.39Note. In Table 16, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 17
Devbest, Devavg, and average time of HA-CCP-RCM and HA-CCP.
Instance nameHA-CCP-RCMHA-CCPRanReal240_050.00/0.04/119.450.01/0.05/135.27RanReal240_090.00/0.10/93.850.06/0.14/98.89RanReal240_160.00/0.06/120.730.00/0.05/102.24RanReal480_050.06/0.17/305.230.00/0.22/301.91RanReal480_140.03/0.18/342.130.00/0.13/340.90RanReal480_180.00/0.12/319.680.00/0.12/330.79RanReal960_02.300.07/0.17/773.080.00/0.11/731.68RanReal960_05.600.08/0.20/754.650.00/0.22/691.55RanReal960_06.300.09/0.19/733.070.00/0.19/777.19RanReal960_07.400.00/0.16/736.560.03/0.12/796.50MDG-a_230.08/0.16/1766.010.00/0.12/1773.65MDG-a_350.04/0.12/1737.760.00/0.09/1827.95Average0.04/0.14/650.180.01/0.13/659.04Note. In Table 17, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.


### 5.2. Benefit of DM3

DM2 [26] is the destruction method used in IG-GRASP [26] to partial destruction solution. To verify the superiority of DM3 used in HA-CCP, we replaced the DM3 in HA-CCP with DM2 and compared the results of HA-CCP using different destruction methods (DM2 and DM3) on the results of the RanReal960 dataset. Table 18 summarizes the statistical comparison results, and Tables 19 and 20 give detailed results.Table 18
Statistical comparison results of DM2 and DM3 on RanReal960.
DM2DM3#Best/Avg1/029/30p valuebest/p valueavg5.77E − 08/1.86E − 09Avg Devbest/Devavg (%)0.19/0.330.02/0.17AvgTime (s)697.94705.36Table 19
Comparative results of DM2 and DM3 on RanReal960.
Instance nameDM2DM3RanReal960_01.301339422.76/1337439.231339783.24/1338150.82RanReal960_02.301433976.41/1432620.511434814.15/1433364.47RanReal960_03.301397391.88/1395414.881397392.10/1395893.73RanReal960_04.301413805.22/1411624.301414298.90/1412090.36RanReal960_05.301369728.30/1368811.021370975.25/1369468.75RanReal960_06.301419316.66/1417731.231418984.70/1417747.24RanReal960_07.301340663.25/1339585.271340800.86/1339709.55RanReal960_08.301466312.51/1465036.051467896.40/1465355.37RanReal960_09.301385370.30/1383667.641386030.28/1384583.74RanReal960_10.301384748.37/1383091.101385179.70/1383692.23RanReal960_01.401041414.82/1040042.651042465.91/1041298.30RanReal960_02.401115375.82/1113835.011117118.83/1115382.72RanReal960_03.401087242.79/1086124.891089455.26/1087348.95RanReal960_04.401100870.73/1099218.541101967.82/1100620.80RanReal960_05.401065983.91/1064140.381066146.84/1064752.74RanReal960_06.401104907.29/1103838.171106596.78/1105105.35RanReal960_07.401041902.02/1040549.031043198.47/1041876.18RanReal960_08.401143170.88/1141692.091144718.73/1142826.31RanReal960_09.401075078.06/1073881.611076824.82/1075395.86RanReal960_10.401077549.54/1076250.331078910.90/1077636.68RanReal960_01.60731791.05/730574.72734308.41/732725.73RanReal960_02.60775695.34/773599.78778535.60/776393.83RanReal960_03.60758983.07/757547.47761525.30/760142.69RanReal960_04.60766615.64/765530.39770670.09/768853.66RanReal960_05.60746350.92/745399.89749120.37/747789.87RanReal960_06.60766117.84/765444.75768842.79/767568.44RanReal960_07.60728688.71/727719.25732517.17/730460.65RanReal960_08.60793341.85/790820.80795271.66/793741.94RanReal960_09.60752529.87/751033.08754767.54/753712.19RanReal960_10.60753818.27/752479.66755877.96/754823.36#Best1/029/30p value5.77E − 08/1.86E − 09Note. In Table 19, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 20
Devbest, Devavg, and average time of DM2 and DM3 on RanReal960.
Instance nameDM2DM3RanReal960_01.300.04/0.18/657.100.01/0.13/701.09RanReal960_02.300.08/0.17/764.820.02/0.12/797.04RanReal960_03.300.01/0.15/710.610.01/0.12/720.84RanReal960_04.300.03/0.19/763.000.00/0.16/667.80RanReal960_05.300.12/0.19/798.160.03/0.14/676.75RanReal960_06.300.11/0.23/714.990.14/0.22/647.17RanReal960_07.300.07/0.15/745.900.06/0.14/749.34RanReal960_08.300.11/0.19/754.810.00/0.17/676.06RanReal960_09.300.05/0.17/725.250.00/0.10/721.36RanReal960_10.300.03/0.15/645.770.00/0.11/725.62RanReal960_01.400.10/0.23/636.560.00/0.11/669.23RanReal960_02.400.19/0.33/662.330.04/0.19/678.43RanReal960_03.400.20/0.31/730.120.00/0.19/748.76RanReal960_04.400.10/0.25/658.970.00/0.12/732.29RanReal960_05.400.02/0.19/707.520.00/0.13/701.30RanReal960_06.400.23/0.33/703.430.08/0.21/654.20RanReal960_07.400.12/0.25/667.780.00/0.13/684.48RanReal960_08.400.14/0.26/702.860.00/0.17/689.27RanReal960_09.400.16/0.27/719.460.00/0.13/719.93RanReal960_10.400.13/0.25/717.190.00/0.12/706.70RanReal960_01.600.34/0.51/693.500.00/0.22/732.69RanReal960_02.600.36/0.63/734.580.00/0.28/718.58RanReal960_03.600.33/0.52/710.390.00/0.18/761.03RanReal960_04.600.53/0.67/707.520.00/0.24/707.68RanReal960_05.600.40/0.52/632.370.03/0.20/666.28RanReal960_06.600.41/0.49/607.120.05/0.22/667.62RanReal960_07.600.52/0.65/701.640.00/0.28/642.39RanReal960_08.600.25/0.56/604.620.01/0.20/707.20RanReal960_09.600.30/0.50/621.110.01/0.15/747.19RanReal960_10.600.29/0.47/738.650.02/0.16/742.39Average0.19/0.33/697.940.02/0.17/705.36Note. In Table 20, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.As shown in Table 18, DM3 has obtained 29 best solutions and 30 best average objective function value and has a smaller value ofAverageDevbest/Devavg. The Wilcoxon statistical test shows that the best performance and average performance of DM2 and DM3 on RanReal960 are statistically significantly different. Therefore, we can conclude that DM3 is superior to DM2 on RanReal960.


### 5.3. Benefit of the Destruct and Reconstruct Partial Solution

Algorithms IVNS, GVNS, SGVNS, and FITS for CCP used a completely random shaking procedure to shake the current solution, but HA-CCP uses the method of destroying and reconstructing partial solutions. To verify the advantage of the destruct and reconstruct partial solution, we combined HA-CCP with the random shaking procedure used in SGVNS [30], called HA-CCP-RS. We compared the result of HA-CCP with HA-CCP-RS on the MDG-a dataset. Table 21 describes the statistical comparison results, and Tables 22 and 23 give detailed results. According to Table 21, HA-CCP has a better performance than HA-CCP-RS in all indicators.Table 21
Statistical comparison results of HA-CCP-RS and HA-CCP on the MDG-a.
HA-CCP-RSHA-CCP#Best/Avg0/020/20p valuebest/p valueavg1.91E − 06/1.91E − 06Avg Devbest/Devavg (%)0.12/0.240.00/0.11AvgTime (s)1843.111757.32Table 22
Comparative results of HA-CCP-RS and HA-CCP on the MDG-a.
Instance nameHA-CCP-RSHA-CCPMDG-a_21390621.00/390145.80390987.00/390660.00MDG-a_22387550.00/387010.65387838.00/387393.10MDG-a_23388466.00/387984.40389071.00/388611.10MDG-a_24389555.00/389016.65390051.00/389525.40MDG-a_25398779.00/398257.00399215.00/398869.20MDG-a_26402852.00/402381.40403425.00/402759.75MDG-a_27382574.00/382245.40383246.00/382731.55MDG-a_28388264.00/387758.55388553.00/388208.60MDG-a_29384292.00/383914.05384933.00/384588.45MDG-a_30397474.00/397111.05398004.00/397503.15MDG-a_31387298.00/386716.30387609.00/387276.55MDG-a_32393730.00/393350.75394290.00/393941.40MDG-a_33385030.00/384564.15385583.00/385036.20MDG-a_34395459.00/394970.90396214.00/395706.85MDG-a_35395459.00/394970.90395848.00/395472.25MDG-a_36402659.00/402316.25402998.00/402698.45MDG-a_37389236.00/388922.00389769.00/389349.00MDG-a_38396689.00/396276.55397249.00/396775.25MDG-a_39392441.00/392042.25392913.00/392506.70MDG-a_40406367.00/405899.70406672.00/406245.60#Best0/020/20p value1.91E − 06/1.91E − 06Note. In Table 22, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 23
Devbest, Devavg, and average time of HA-CCP-RS and HA-CCP on the MDG-a.
Instance nameHA-CCP-RSHA-CCPMDG-a_210.09/0.22/1827.800.00/0.08/1765.62MDG-a_220.07/0.21/1854.630.00/0.11/1719.05MDG-a_230.16/0.28/1760.080.00/0.12/1773.65MDG-a_240.13/0.27/1876.730.00/0.13/1807.82MDG-a_250.11/0.24/1854.490.00/0.09/1731.29MDG-a_260.14/0.26/1854.900.00/0.16/1701.12MDG-a_270.18/0.26/1770.480.00/0.13/1630.26MDG-a_280.07/0.20/1842.330.00/0.09/1849.73MDG-a_290.17/0.26/1856.950.00/0.09/1780.88MDG-a_300.13/0.22/1888.560.00/0.13/1801.66MDG-a_310.08/0.23/1833.460.00/0.09/1637.96MDG-a_320.14/0.24/1811.640.00/0.09/1739.88MDG-a_330.14/0.26/1827.210.00/0.14/1788.08MDG-a_340.19/0.31/1822.350.00/0.13/1721.00MDG-a_350.10/0.22/1822.350.00/0.09/1827.95MDG-a_360.08/0.17/1839.010.00/0.07/1731.40MDG-a_370.14/0.22/1849.990.00/0.11/1746.95MDG-a_380.14/0.24/1904.830.00/0.12/1806.92MDG-a_390.12/0.22/1894.740.00/0.10/1763.70MDG-a_400.07/0.19/1869.640.00/0.10/1821.44Average0.12/0.24/1843.110.00/0.11/1757.32Note. In Table 23, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.


### 5.4. Benefit of Acceptance Criterion for Skew

HA-CCP added an acceptance criterion for skewing the search to other promising areas of the solution space. To verify the performance of acceptance criterion for skew to the performance, we compared the result of HA-CCP with the HA-CCP without acceptance criterion for skew (HA-CCP-NAC for short) on RanReal240 and RanReal480 datasets. Table24 shows the statistical comparison results, and detailed results are given in Tables 25 and 26. As shown in Table 24, HA-CCP has a better performance than HA-CCP-NAC in best results and average results.Table 24
Statistical comparison results of HA-CCP-NAC and HA-CCP on RanReal240 and RanReal480.
HA-CCP-NACHA-CCP#Best/Avg0/040/40p valuebest/p valueavg1.82E − 12/1.82E − 12Avg Devbest/Devavg (%)0.17/0.260.00/0.11AvgTime (s)190.29217.25Table 25
Comparative results of HA-CCP-NAC and HA-CCP on RanReal240 and RanReal480.
Instance nameHA-CCP-NACHA-CCPRanReal240_01224727.06/224616.93225003.70/224897.01RanReal240_02204435.05/204256.39204624.36/204515.06RanReal240_03198819.54/198592.41199079.37/198915.84RanReal240_04225102.36/224814.97225683.17/225346.54RanReal240_05195307.90/195203.22195540.41/195469.00RanReal240_06216477.84/216312.91216730.26/216613.93RanReal240_07208949.52/208789.41209282.88/209150.41RanReal240_08205040.86/204835.75205246.82/205110.51RanReal240_09208588.26/208475.27209057.64/208897.23RanReal240_10192868.91/192706.85193044.16/192954.72RanReal240_11204549.74/204455.01204722.75/204638.07RanReal240_12200951.37/200791.23201117.11/201006.45RanReal240_13202170.78/201988.4202345.48/202285.83RanReal240_14228594.33/228434.38228971.03/228740.72RanReal240_15191160.90/190978.45191243.76/191117.60RanReal240_16203796.06/203691.26204072.57/203961.38RanReal240_17194915.27/194730.53195393.97/195278.93RanReal240_18195012.27/194868.93195167.14/195069.80RanReal240_19199135.59/198980.50199307.33/199204.90RanReal240_20211956.00/211831.11212229.46/212111.19RanReal480_01555335.92/554734.67556126.86/555338.06RanReal480_02510361.31/509822.51511566.55/510924.27RanReal480_03496848.36/496025.80498028.54/497109.59RanReal480_04521736.02/521332.69522790.22/521999.31RanReal480_05483933.52/483612.70485138.44/484092.59RanReal480_06533914.73/533474.70534961.79/534114.47RanReal480_07545679.18/545247.24546503.90/545582.87RanReal480_08531790.95/531213.90532891.23/532161.08RanReal480_09555943.11/555557.53557120.25/556265.26RanReal480_10519486.75/519083.16520492.06/519891.18RanReal480_11523048.09/522469.89524669.99/523760.48RanReal480_12501724.17/500933.49503359.96/502069.60RanReal480_13534164.65/533751.60535251.73/534707.51RanReal480_14513914.91/513549.56515476.42/514801.49RanReal480_15517055.94/516347.68518370.90/517283.29RanReal480_16549618.65/549232.56550317.71/549881.85RanReal480_17537155.63/536696.66538745.70/537826.26RanReal480_18525517.30/524655.46526314.82/525702.47RanReal480_19522191.15/521731.11522958.23/522365.10RanReal480_20518068.63/517724.40519277.92/518518.27#Best0/040/40p value1.82E − 12/1.82E − 12Note. In Table 25, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 26
Devbest, Devavg, and average time of HA-CCP-NAC and HA-CCP on RanReal240 and RanReal480.
Instance nameHA-CCP-NACHA-CCPRanReal240_010.12/0.17/93.820.00/0.05/127.88RanReal240_020.09/0.18/127.360.00/0.05/111.58RanReal240_030.13/0.24/130.940.00/0.08/135.66RanReal240_040.26/0.38/122.880.00/0.15/124.67RanReal240_050.12/0.17/110.230.00/0.04/135.27RanReal240_060.12/0.19/109.100.00/0.05/129.28RanReal240_070.16/0.24/123.430.00/0.06/127.25RanReal240_080.10/0.20/100.100.00/0.07/112.98RanReal240_090.22/0.28/114.320.00/0.08/98.89RanReal240_100.09/0.17/116.080.00/0.05/111.58RanReal240_110.08/0.13/122.570.00/0.04/125.15RanReal240_120.08/0.16/131.990.00/0.06/108.32RanReal240_130.09/0.18/135.130.00/0.03/139.97RanReal240_140.16/0.23/129.750.00/0.1/122.04RanReal240_150.04/0.14/118.750.00/0.07/101.57RanReal240_160.14/0.19/145.530.00/0.05/102.24RanReal240_170.24/0.34/132.890.00/0.06/132.10RanReal240_180.08/0.15/122.700.00/0.05/110.87RanReal240_190.09/0.16/80.490.00/0.05/121.71RanReal240_200.13/0.19/103.680.00/0.06/99.55RanReal480_010.14/0.25/197.770.00/0.14/349.71RanReal480_020.24/0.34/284.810.00/0.13/330.24RanReal480_030.24/0.40/295.480.00/0.18/332.28RanReal480_040.20/0.28/267.300.00/0.15/329.59RanReal480_050.25/0.31/258.950.00/0.22/301.91RanReal480_060.20/0.28/251.780.00/0.16/280.00RanReal480_070.15/0.23/303.630.00/0.17/285.02RanReal480_080.21/0.31/275.770.00/0.14/283.23RanReal480_090.21/0.28/208.490.00/0.15/255.35RanReal480_100.19/0.27/257.740.00/0.12/307.38RanReal480_110.31/0.42/214.080.00/0.17/299.74RanReal480_120.32/0.48/277.580.00/0.26/349.86RanReal480_130.20/0.28/271.160.00/0.10/333.59RanReal480_140.30/0.37/293.640.00/0.13/340.90RanReal480_150.25/0.39/279.550.00/0.21/282.23RanReal480_160.13/0.20/243.760.00/0.08/294.16RanReal480_170.30/0.38/251.440.00/0.17/336.43RanReal480_180.15/0.32/297.750.00/0.12/330.79RanReal480_190.15/0.23/268.870.00/0.11/343.32RanReal480_200.23/0.30/240.170.00/0.15/345.87Average0.17/0.26/190.290.00/0.11/217.25Note. In Table 26, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.In summary, from the experimental results of the four aspects of “the construction of solution,” “the destruction of the partial solution,” “the destruction and reconstruction of the partial solution,” “the acceptance criteria,” no matter which component is replaced, the overall performance of the algorithm decreases significantly. Therefore, we believe that the combination of these components has obtained good experimental results. The effective combination of these components helps the algorithm jump out of the local optimum and obtains a better balance between intensification and diversification levels.


## 5.1. Benefit of CM2

In HA-CCP, CM2 is first used to construct the initial feasible solution (Algorithm 2, line 2) and then reconstruct the solution in the iterative process (Algorithm 2, line 9). Different from CM [26] and random construction method (RCM, used in [29, 31, 32]), CM2 can increase the probability of constructing a feasible solution when the upper and lower bounds are tighter and improve the performance of HA-CCP. Therefore, we conducted comparative experiments in the following two aspects.First, we compared the success rate of constructing the initial feasible solution between RCM and CM2 under different upper and lower bound constraints on 10 RanReal960 instances withp=60. In the experiment, the upper and lower bounds Ug and Lg of the instance are adjusted to Ug′=s2×Ug and Lg′=s1×Lg, respectively. Obviously, s2<1 and s1>1 will tighten the constraints of CCP. For each instance, RCM and CM2 are run 100 times under the new upper and lower bound constraints, respectively, and the success rate of obtaining the initial solution is shown in Table 14. The “average” row indicates the average value of the construction success rate of all the test instances.Table 14
Success rate of RCM and CM2 in constructing initial feasible solution on RanReal960 instances withp=60.
Instance name(1.30, 1)(1.28, 1)(1.27, 1)(1, 1)(1, 0.94)(1, 0.93)(1, 0.92)RanReal960_01.60100%/100%100%/100%100%/100%100%/100%85%/100%0%/100%0%/100%RanReal960_02.6097%/100%100%/100%100%/100%100%/100%100%/100%100%/100%90%/100%RanReal960_03.60100%/100%100%/100%100%/100%100%/100%100%/100%100%/100%20%/100%RanReal960_04.601%/14%100%/100%100%/100%100%/100%100%/100%100%/100%100%/100%RanReal960_05.60100%/100%100%/100%100%/100%100%/100%100%/100%64%/100%0%/100%RanReal960_06.60100%/100%100%/100%100%/100%100%/100%34%/100%0%/100%0%/0%RanReal960_07.60100%/100%100%/100%100%/100%100%/100%0%/100%0%/0%0%/0%RanReal960_08.600%/0%71%/95%79%/98%100%/100%100%/100%100%/100%100%/100%RanReal960_09.60100%/100%100%/100%100%/100%100%/100%100%/100%100%/100%89%/100%RanReal960_10.60100%/100%100%/100%100%/100%100%/100%64%/100%0%/100%0%/100%Average79.8%/81.4%97.1%/99.5%97.9%/99.8%100%/100%78.3%/100%56.4%/90%39.9%/80%Note. In Table 14, s1 and s2 in s1,s2, respectively, denote the scaling ratios of the lower and upper bounds of the cluster capacity. A and B in A/B, respectively, represent the initial solution construction success rate obtained using RCM and CM2.We can see from Table 14 that if the upper and lower bounds of the cluster capacity become stricter, the success rate of RCM and CM2 in constructing the initial solution decreases, but the success rate of CM2 is higher than that of RCM. From the average point of view, the success rate of CM2 in the experiment is higher than that of RCM, even as high as 2 times (the last column of Table14). Therefore, CM2 has better usability than RCM, and it can construct feasible solutions in tighter constrained CCPs.Secondly, we use RCM to replace CM2 in HA-CCP (denoted as HA-CCP-RCM) for comparison experiments with HA-CCP. The experiment was conducted on the same 10 instances as Section4.3, and each instance was run 20 times. Table 15 summarizes the comparison results, and Tables 16 and 17 give detailed results. It can be seen from Table 15 that when the average calculation time is almost the same, HA-CCP with CM2 can obtain more best solution and best average solution. Therefore, CM2 can effectively improve the CCP solution quality.Table 15
Statistical comparison results of HA-CCP-RCM and HA-CCP.
HA-CCP-RCMHA-CCP#Best/Avg4/48/8p valuebest/p valueavg0.39/0.39Avg Devbest/Devavg (%)0.04/0.140.01/0.13AvgTime (s)650.18659.04Table 16
Comparative results of HA-CCP-RCM and HA-CCP.
Instance nameHA-CCP-RCMHA-CCPRanReal240_05195558.15/195472.31195540.41/195469.00RanReal240_09209186.90/208970.18209057.64/208897.23RanReal240_16204063.69/203943.95204072.57/203961.38RanReal480_05484845.80/484337.08485138.44/484092.59RanReal480_14515313.22/514565.40515476.42/514801.49RanReal480_18526331.30/525686.10526314.82/525702.47RanReal960_02.301434083.69/1432684.791435087.46/1433503.63RanReal960_05.60748689.45/747833.47749316.68/747647.96RanReal960_06.301419623.57/1418217.771420942.81/1418222.26RanReal960_07.401043459.88/1041763.791043176.75/1042209.24MDG-a_23388753.00/388437.80389071.00/388611.10MDG-a_35395692.00/395378.35395848.00/395472.25#Best4/48/8p Value0.39/0.39Note. In Table 16, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 17
Devbest, Devavg, and average time of HA-CCP-RCM and HA-CCP.
Instance nameHA-CCP-RCMHA-CCPRanReal240_050.00/0.04/119.450.01/0.05/135.27RanReal240_090.00/0.10/93.850.06/0.14/98.89RanReal240_160.00/0.06/120.730.00/0.05/102.24RanReal480_050.06/0.17/305.230.00/0.22/301.91RanReal480_140.03/0.18/342.130.00/0.13/340.90RanReal480_180.00/0.12/319.680.00/0.12/330.79RanReal960_02.300.07/0.17/773.080.00/0.11/731.68RanReal960_05.600.08/0.20/754.650.00/0.22/691.55RanReal960_06.300.09/0.19/733.070.00/0.19/777.19RanReal960_07.400.00/0.16/736.560.03/0.12/796.50MDG-a_230.08/0.16/1766.010.00/0.12/1773.65MDG-a_350.04/0.12/1737.760.00/0.09/1827.95Average0.04/0.14/650.180.01/0.13/659.04Note. In Table 17, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.


## 5.2. Benefit of DM3

DM2 [26] is the destruction method used in IG-GRASP [26] to partial destruction solution. To verify the superiority of DM3 used in HA-CCP, we replaced the DM3 in HA-CCP with DM2 and compared the results of HA-CCP using different destruction methods (DM2 and DM3) on the results of the RanReal960 dataset. Table 18 summarizes the statistical comparison results, and Tables 19 and 20 give detailed results.Table 18
Statistical comparison results of DM2 and DM3 on RanReal960.
DM2DM3#Best/Avg1/029/30p valuebest/p valueavg5.77E − 08/1.86E − 09Avg Devbest/Devavg (%)0.19/0.330.02/0.17AvgTime (s)697.94705.36Table 19
Comparative results of DM2 and DM3 on RanReal960.
Instance nameDM2DM3RanReal960_01.301339422.76/1337439.231339783.24/1338150.82RanReal960_02.301433976.41/1432620.511434814.15/1433364.47RanReal960_03.301397391.88/1395414.881397392.10/1395893.73RanReal960_04.301413805.22/1411624.301414298.90/1412090.36RanReal960_05.301369728.30/1368811.021370975.25/1369468.75RanReal960_06.301419316.66/1417731.231418984.70/1417747.24RanReal960_07.301340663.25/1339585.271340800.86/1339709.55RanReal960_08.301466312.51/1465036.051467896.40/1465355.37RanReal960_09.301385370.30/1383667.641386030.28/1384583.74RanReal960_10.301384748.37/1383091.101385179.70/1383692.23RanReal960_01.401041414.82/1040042.651042465.91/1041298.30RanReal960_02.401115375.82/1113835.011117118.83/1115382.72RanReal960_03.401087242.79/1086124.891089455.26/1087348.95RanReal960_04.401100870.73/1099218.541101967.82/1100620.80RanReal960_05.401065983.91/1064140.381066146.84/1064752.74RanReal960_06.401104907.29/1103838.171106596.78/1105105.35RanReal960_07.401041902.02/1040549.031043198.47/1041876.18RanReal960_08.401143170.88/1141692.091144718.73/1142826.31RanReal960_09.401075078.06/1073881.611076824.82/1075395.86RanReal960_10.401077549.54/1076250.331078910.90/1077636.68RanReal960_01.60731791.05/730574.72734308.41/732725.73RanReal960_02.60775695.34/773599.78778535.60/776393.83RanReal960_03.60758983.07/757547.47761525.30/760142.69RanReal960_04.60766615.64/765530.39770670.09/768853.66RanReal960_05.60746350.92/745399.89749120.37/747789.87RanReal960_06.60766117.84/765444.75768842.79/767568.44RanReal960_07.60728688.71/727719.25732517.17/730460.65RanReal960_08.60793341.85/790820.80795271.66/793741.94RanReal960_09.60752529.87/751033.08754767.54/753712.19RanReal960_10.60753818.27/752479.66755877.96/754823.36#Best1/029/30p value5.77E − 08/1.86E − 09Note. In Table 19, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 20
Devbest, Devavg, and average time of DM2 and DM3 on RanReal960.
Instance nameDM2DM3RanReal960_01.300.04/0.18/657.100.01/0.13/701.09RanReal960_02.300.08/0.17/764.820.02/0.12/797.04RanReal960_03.300.01/0.15/710.610.01/0.12/720.84RanReal960_04.300.03/0.19/763.000.00/0.16/667.80RanReal960_05.300.12/0.19/798.160.03/0.14/676.75RanReal960_06.300.11/0.23/714.990.14/0.22/647.17RanReal960_07.300.07/0.15/745.900.06/0.14/749.34RanReal960_08.300.11/0.19/754.810.00/0.17/676.06RanReal960_09.300.05/0.17/725.250.00/0.10/721.36RanReal960_10.300.03/0.15/645.770.00/0.11/725.62RanReal960_01.400.10/0.23/636.560.00/0.11/669.23RanReal960_02.400.19/0.33/662.330.04/0.19/678.43RanReal960_03.400.20/0.31/730.120.00/0.19/748.76RanReal960_04.400.10/0.25/658.970.00/0.12/732.29RanReal960_05.400.02/0.19/707.520.00/0.13/701.30RanReal960_06.400.23/0.33/703.430.08/0.21/654.20RanReal960_07.400.12/0.25/667.780.00/0.13/684.48RanReal960_08.400.14/0.26/702.860.00/0.17/689.27RanReal960_09.400.16/0.27/719.460.00/0.13/719.93RanReal960_10.400.13/0.25/717.190.00/0.12/706.70RanReal960_01.600.34/0.51/693.500.00/0.22/732.69RanReal960_02.600.36/0.63/734.580.00/0.28/718.58RanReal960_03.600.33/0.52/710.390.00/0.18/761.03RanReal960_04.600.53/0.67/707.520.00/0.24/707.68RanReal960_05.600.40/0.52/632.370.03/0.20/666.28RanReal960_06.600.41/0.49/607.120.05/0.22/667.62RanReal960_07.600.52/0.65/701.640.00/0.28/642.39RanReal960_08.600.25/0.56/604.620.01/0.20/707.20RanReal960_09.600.30/0.50/621.110.01/0.15/747.19RanReal960_10.600.29/0.47/738.650.02/0.16/742.39Average0.19/0.33/697.940.02/0.17/705.36Note. In Table 20, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.As shown in Table 18, DM3 has obtained 29 best solutions and 30 best average objective function value and has a smaller value ofAverageDevbest/Devavg. The Wilcoxon statistical test shows that the best performance and average performance of DM2 and DM3 on RanReal960 are statistically significantly different. Therefore, we can conclude that DM3 is superior to DM2 on RanReal960.


## 5.3. Benefit of the Destruct and Reconstruct Partial Solution

Algorithms IVNS, GVNS, SGVNS, and FITS for CCP used a completely random shaking procedure to shake the current solution, but HA-CCP uses the method of destroying and reconstructing partial solutions. To verify the advantage of the destruct and reconstruct partial solution, we combined HA-CCP with the random shaking procedure used in SGVNS [30], called HA-CCP-RS. We compared the result of HA-CCP with HA-CCP-RS on the MDG-a dataset. Table 21 describes the statistical comparison results, and Tables 22 and 23 give detailed results. According to Table 21, HA-CCP has a better performance than HA-CCP-RS in all indicators.Table 21
Statistical comparison results of HA-CCP-RS and HA-CCP on the MDG-a.
HA-CCP-RSHA-CCP#Best/Avg0/020/20p valuebest/p valueavg1.91E − 06/1.91E − 06Avg Devbest/Devavg (%)0.12/0.240.00/0.11AvgTime (s)1843.111757.32Table 22
Comparative results of HA-CCP-RS and HA-CCP on the MDG-a.
Instance nameHA-CCP-RSHA-CCPMDG-a_21390621.00/390145.80390987.00/390660.00MDG-a_22387550.00/387010.65387838.00/387393.10MDG-a_23388466.00/387984.40389071.00/388611.10MDG-a_24389555.00/389016.65390051.00/389525.40MDG-a_25398779.00/398257.00399215.00/398869.20MDG-a_26402852.00/402381.40403425.00/402759.75MDG-a_27382574.00/382245.40383246.00/382731.55MDG-a_28388264.00/387758.55388553.00/388208.60MDG-a_29384292.00/383914.05384933.00/384588.45MDG-a_30397474.00/397111.05398004.00/397503.15MDG-a_31387298.00/386716.30387609.00/387276.55MDG-a_32393730.00/393350.75394290.00/393941.40MDG-a_33385030.00/384564.15385583.00/385036.20MDG-a_34395459.00/394970.90396214.00/395706.85MDG-a_35395459.00/394970.90395848.00/395472.25MDG-a_36402659.00/402316.25402998.00/402698.45MDG-a_37389236.00/388922.00389769.00/389349.00MDG-a_38396689.00/396276.55397249.00/396775.25MDG-a_39392441.00/392042.25392913.00/392506.70MDG-a_40406367.00/405899.70406672.00/406245.60#Best0/020/20p value1.91E − 06/1.91E − 06Note. In Table 22, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 23
Devbest, Devavg, and average time of HA-CCP-RS and HA-CCP on the MDG-a.
Instance nameHA-CCP-RSHA-CCPMDG-a_210.09/0.22/1827.800.00/0.08/1765.62MDG-a_220.07/0.21/1854.630.00/0.11/1719.05MDG-a_230.16/0.28/1760.080.00/0.12/1773.65MDG-a_240.13/0.27/1876.730.00/0.13/1807.82MDG-a_250.11/0.24/1854.490.00/0.09/1731.29MDG-a_260.14/0.26/1854.900.00/0.16/1701.12MDG-a_270.18/0.26/1770.480.00/0.13/1630.26MDG-a_280.07/0.20/1842.330.00/0.09/1849.73MDG-a_290.17/0.26/1856.950.00/0.09/1780.88MDG-a_300.13/0.22/1888.560.00/0.13/1801.66MDG-a_310.08/0.23/1833.460.00/0.09/1637.96MDG-a_320.14/0.24/1811.640.00/0.09/1739.88MDG-a_330.14/0.26/1827.210.00/0.14/1788.08MDG-a_340.19/0.31/1822.350.00/0.13/1721.00MDG-a_350.10/0.22/1822.350.00/0.09/1827.95MDG-a_360.08/0.17/1839.010.00/0.07/1731.40MDG-a_370.14/0.22/1849.990.00/0.11/1746.95MDG-a_380.14/0.24/1904.830.00/0.12/1806.92MDG-a_390.12/0.22/1894.740.00/0.10/1763.70MDG-a_400.07/0.19/1869.640.00/0.10/1821.44Average0.12/0.24/1843.110.00/0.11/1757.32Note. In Table 23, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.


## 5.4. Benefit of Acceptance Criterion for Skew

HA-CCP added an acceptance criterion for skewing the search to other promising areas of the solution space. To verify the performance of acceptance criterion for skew to the performance, we compared the result of HA-CCP with the HA-CCP without acceptance criterion for skew (HA-CCP-NAC for short) on RanReal240 and RanReal480 datasets. Table24 shows the statistical comparison results, and detailed results are given in Tables 25 and 26. As shown in Table 24, HA-CCP has a better performance than HA-CCP-NAC in best results and average results.Table 24
Statistical comparison results of HA-CCP-NAC and HA-CCP on RanReal240 and RanReal480.
HA-CCP-NACHA-CCP#Best/Avg0/040/40p valuebest/p valueavg1.82E − 12/1.82E − 12Avg Devbest/Devavg (%)0.17/0.260.00/0.11AvgTime (s)190.29217.25Table 25
Comparative results of HA-CCP-NAC and HA-CCP on RanReal240 and RanReal480.
Instance nameHA-CCP-NACHA-CCPRanReal240_01224727.06/224616.93225003.70/224897.01RanReal240_02204435.05/204256.39204624.36/204515.06RanReal240_03198819.54/198592.41199079.37/198915.84RanReal240_04225102.36/224814.97225683.17/225346.54RanReal240_05195307.90/195203.22195540.41/195469.00RanReal240_06216477.84/216312.91216730.26/216613.93RanReal240_07208949.52/208789.41209282.88/209150.41RanReal240_08205040.86/204835.75205246.82/205110.51RanReal240_09208588.26/208475.27209057.64/208897.23RanReal240_10192868.91/192706.85193044.16/192954.72RanReal240_11204549.74/204455.01204722.75/204638.07RanReal240_12200951.37/200791.23201117.11/201006.45RanReal240_13202170.78/201988.4202345.48/202285.83RanReal240_14228594.33/228434.38228971.03/228740.72RanReal240_15191160.90/190978.45191243.76/191117.60RanReal240_16203796.06/203691.26204072.57/203961.38RanReal240_17194915.27/194730.53195393.97/195278.93RanReal240_18195012.27/194868.93195167.14/195069.80RanReal240_19199135.59/198980.50199307.33/199204.90RanReal240_20211956.00/211831.11212229.46/212111.19RanReal480_01555335.92/554734.67556126.86/555338.06RanReal480_02510361.31/509822.51511566.55/510924.27RanReal480_03496848.36/496025.80498028.54/497109.59RanReal480_04521736.02/521332.69522790.22/521999.31RanReal480_05483933.52/483612.70485138.44/484092.59RanReal480_06533914.73/533474.70534961.79/534114.47RanReal480_07545679.18/545247.24546503.90/545582.87RanReal480_08531790.95/531213.90532891.23/532161.08RanReal480_09555943.11/555557.53557120.25/556265.26RanReal480_10519486.75/519083.16520492.06/519891.18RanReal480_11523048.09/522469.89524669.99/523760.48RanReal480_12501724.17/500933.49503359.96/502069.60RanReal480_13534164.65/533751.60535251.73/534707.51RanReal480_14513914.91/513549.56515476.42/514801.49RanReal480_15517055.94/516347.68518370.90/517283.29RanReal480_16549618.65/549232.56550317.71/549881.85RanReal480_17537155.63/536696.66538745.70/537826.26RanReal480_18525517.30/524655.46526314.82/525702.47RanReal480_19522191.15/521731.11522958.23/522365.10RanReal480_20518068.63/517724.40519277.92/518518.27#Best0/040/40p value1.82E − 12/1.82E − 12Note. In Table 25, data A/B denote the best objective value and the average objective value of the instance found by the algorithm.Table 26
Devbest, Devavg, and average time of HA-CCP-NAC and HA-CCP on RanReal240 and RanReal480.
Instance nameHA-CCP-NACHA-CCPRanReal240_010.12/0.17/93.820.00/0.05/127.88RanReal240_020.09/0.18/127.360.00/0.05/111.58RanReal240_030.13/0.24/130.940.00/0.08/135.66RanReal240_040.26/0.38/122.880.00/0.15/124.67RanReal240_050.12/0.17/110.230.00/0.04/135.27RanReal240_060.12/0.19/109.100.00/0.05/129.28RanReal240_070.16/0.24/123.430.00/0.06/127.25RanReal240_080.10/0.20/100.100.00/0.07/112.98RanReal240_090.22/0.28/114.320.00/0.08/98.89RanReal240_100.09/0.17/116.080.00/0.05/111.58RanReal240_110.08/0.13/122.570.00/0.04/125.15RanReal240_120.08/0.16/131.990.00/0.06/108.32RanReal240_130.09/0.18/135.130.00/0.03/139.97RanReal240_140.16/0.23/129.750.00/0.1/122.04RanReal240_150.04/0.14/118.750.00/0.07/101.57RanReal240_160.14/0.19/145.530.00/0.05/102.24RanReal240_170.24/0.34/132.890.00/0.06/132.10RanReal240_180.08/0.15/122.700.00/0.05/110.87RanReal240_190.09/0.16/80.490.00/0.05/121.71RanReal240_200.13/0.19/103.680.00/0.06/99.55RanReal480_010.14/0.25/197.770.00/0.14/349.71RanReal480_020.24/0.34/284.810.00/0.13/330.24RanReal480_030.24/0.40/295.480.00/0.18/332.28RanReal480_040.20/0.28/267.300.00/0.15/329.59RanReal480_050.25/0.31/258.950.00/0.22/301.91RanReal480_060.20/0.28/251.780.00/0.16/280.00RanReal480_070.15/0.23/303.630.00/0.17/285.02RanReal480_080.21/0.31/275.770.00/0.14/283.23RanReal480_090.21/0.28/208.490.00/0.15/255.35RanReal480_100.19/0.27/257.740.00/0.12/307.38RanReal480_110.31/0.42/214.080.00/0.17/299.74RanReal480_120.32/0.48/277.580.00/0.26/349.86RanReal480_130.20/0.28/271.160.00/0.10/333.59RanReal480_140.30/0.37/293.640.00/0.13/340.90RanReal480_150.25/0.39/279.550.00/0.21/282.23RanReal480_160.13/0.20/243.760.00/0.08/294.16RanReal480_170.30/0.38/251.440.00/0.17/336.43RanReal480_180.15/0.32/297.750.00/0.12/330.79RanReal480_190.15/0.23/268.870.00/0.11/343.32RanReal480_200.23/0.30/240.170.00/0.15/345.87Average0.17/0.26/190.290.00/0.11/217.25Note. In Table 26, data A/B/C denote the value of Devbest, the value of Devavg, and the algorithm’s average time to find a final solution.In summary, from the experimental results of the four aspects of “the construction of solution,” “the destruction of the partial solution,” “the destruction and reconstruction of the partial solution,” “the acceptance criteria,” no matter which component is replaced, the overall performance of the algorithm decreases significantly. Therefore, we believe that the combination of these components has obtained good experimental results. The effective combination of these components helps the algorithm jump out of the local optimum and obtains a better balance between intensification and diversification levels.


## 6. Conclusion

The capacitated clustering problem (CCP) has a wide range of applications. In this study, we propose a hybrid heuristic algorithm HA-CCP for CCP. After constructing the initial solution, HA-CCP partially destructs and reconstructs the current solution through a combination of greediness and randomness to obtain a new solution. On this basis, an acceptance criterion is added, which allows the current solution to be skewed to move to inferior solutions so that more promising solutions can be explored in the solution space.The competitive experiments on the benchmark instances show that HA-CCP is superior to all comparison algorithms except NVSD in terms of average solving efficiency for all instances (because the solution time is not given). The result of the time-to-target analysis also verifies the efficiency of HA-CCP. Moreover, HA-CCP is better than all comparison algorithms because the best average solution of 58 instances is obtained on all 90 instances, which shows that HA-CCP has better solution stability. However, the solution quality of HA-CCP on MDG-a instances is obviously inferior to NDVNS.As future work, we believe that the following research is worthwhile. First, the automatic parameter adjustment tool irace is used [38] to adjust the HA-CCP parameters to find a better parameter configuration. Second, the improved solution construction strategy enables the algorithm to solve the more restrictive CCP. Third, NDVNS is combined to improve HA-CCP, so that it has better solution quality on CCP including MDG-a.



---

*Source: 6400318-2022-01-21.xml*