<figure><img src="image_1.png" /></figure>

HAL
open science

# Heuristic search to the capacitated clustering problem

Qing Zhou, Una Benlic, Qinghua Wu, Jin-Kao Hao

► To cite this version:

Qing Zhou, Una Benlic, Qinghua Wu, Jin-Kao Hao. Heuristic search to the capacitated clustering problem. European Journal of Operational Research, 2019, 273 (2), pp.464-487. 10.1016/j.ejor.2018.08.043. hal-02310000

HAL Id: hal-02310000

https://hal.science/hal-02310000

Submitted on 23 Sep 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Heuristic search to the capacitated clustering problem

Qing Zhou<sup>a</sup>, Una Benlic<sup>b</sup>, Qinghua Wu<sup>a,*</sup>, Jin-Kao Hao<sup>c,d</sup>

<sup>a</sup>School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China, email: qingzhou@hust.edu.cn; qinghuawu1005@gmail.com

<sup>b</sup>SATALIA, 40 High Street, Islington High Street, London, United Kingdom, N1 8XB, email: una@satalia.com

<sup>c</sup>LERIA, Université d'Angers, 2 bd Lavoisier, 49045 Angers Cedex 01, France, email: jin-kao.hao@univ-angers.fr

<sup>d</sup>Institut Universitaire de France, 1 rue Descartes, 75231 Paris, France

## Abstract

Given a weighted graph, the capacitated clustering problem (CCP) is to partition a set of nodes into a given number of distinct clusters (or groups) with restricted capacities, while maximizing the sum of edge weights corresponding to two nodes from the same cluster. CCP is an NP-hard problem with many relevant applications. This paper proposes two effective algorithms for CCP: a Tabu Search (denoted as FITS) that alternates between exploration in feasible and infeasible search space regions, and a Memetic Algorithm (MA) that combines FITS with a dedicated cluster-based crossover. Extensive computational results on five sets of 183 benchmark instances from the literature indicate that the proposed FITS competes favorably with the state-of-the-art algorithms. Additionally, an experimental comparison between FITS and MA under an extended time limit demonstrates that further improvements in terms of the solution quality can be achieved with MA in most cases. We also analyze several essential components of the proposed algorithms to understand their importance to the success of these approaches.

Keywords: Tabu search; memetic algorithm; infeasible local search; capacitated clustering.

<footnote>* Corresponding author.</footnote>
# 1 Introduction

Given a weighted graph $G = (V, E)$ where $V$ is a set of $n$ nodes and $E$ is a set of edges, let $w_i \ge 0$ be the weight of node $i \in V$ and let $c_{ij}$ ($\{i, j\} \in E$) be the edge weight between nodes $i$ and $j$ ($c_{ij} = 0$, if $\{i, j\} \notin E$). The Capacitated Clustering Problem (CCP) is to partition $V$ into a given number $p$ ($p \le n$) of disjoint clusters or groups such that the sum of node weights in each cluster is constrained by an upper and a lower capacity limit, while maximizing the sum of edge weights whose two associated endpoints belong to the same cluster.

Formally, let the binary variable $X_{ig}$ take the value 1 if node $i$ is assigned to group $g$ ($g \in \{1, 2, ..., p\}$), and 0 otherwise. CCP can then be expressed as the following quadratic program [7,10]:

$$ \textbf{maximize} \quad \sum_{g=1}^{p} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} c_{ij} X_{ig} X_{jg} \qquad (1) $$

$$ \textbf{subject to} \quad \sum_{g=1}^{p} X_{ig} = 1, \quad \forall i \in V \qquad (2) $$

$$ L_g \le \sum_{i=1}^{n} w_i X_{ig} \le U_g, \quad \forall g \in \{1, 2, ..., p\} \qquad (3) $$

$$ X_{ig} \in \{0, 1\}, \quad \forall i \in V, g \in \{1, 2, ..., p\} \qquad (4) $$

Constraint (2) guarantees that every node is assigned to exactly one cluster, while constraint (3) ensures that the minimum capacity ($L_g$) and the maximum capacity ($U_g$) requirements of each cluster are satisfied.

Note that CCP is closely related to the Graph Partitioning Problem (GPP) [4,5,16] where the lower and the upper capacity limits of the clusters are respectively set to 0 and a predetermined imbalance parameter. Moreover, the Maximally Diverse Grouping Problem (MDGP) [6,17,22,25,34,37,38] is a special case of CCP, when $G$ is a complete graph with unit cost node weights. Consequently, CCP is an NP-hard problem as MDGP is known to be NP-hard. Furthermore, CCP is equivalent to the Handover Minimization Problem (HMP) in mobility networks [29] where the objective is to minimize the sum of weights of the edges with endpoints in different clusters. In addition to its application in mobility networks, CCP arises in several different contexts including mail delivery [2], VLSI design [38] and vehicle routing [14,23].

Since it was first defined in 1984 by Mulvey and Beck [33], a variety of solution approaches have been proposed for CCP given its practical importance and NP-hard nature. State-of-the-art approaches include a Greedy Randomized
Adaptive Search Procedure with Path Relinking (GRASP-PR) by Deng and Bard [10]. In 2013, Morán-Mirabal et al. [31] proposed three algorithms for the equivalent handover minimization problem: a GRASP with path-relinking (denoted as GQAP in the corresponding paper), a GRASP with evolutionary path-relinking (GevPR-HMP) and a population-based biased random-key genetic algorithm (BRKGA). According to their computational results, GevPR-HMP exhibits the best performance among those three algorithms. In 2015, Martínez-Gavara et al. [29] presented several approaches which may be considered as state-of-the-art methods for CCP, including a Greedy Randomized Adaptive Search Procedure (GRASP), a Tabu Search method (TS), a hybrid method combining GRASP with TS (GRASP+TS), and a Tabu Search with Strategic Oscillation (TSONO). In 2016, Lai and Hao [24] proposed a highly effective Iterated Variable Neighborhood Search (IVNS) for CCP. More recently, Martínez-Gavara et al. [30] applied several methods to CCP including a GRASP algorithm (denoted as GRASP2-1) and an Iterated Greedy (IG) algorithm, while Brimberg et al. [7] presented two highly effective VNS-based heuristics denoted as GVNS and SGVNS. A comprehensive review on the most representative approaches for CCP prior to 2011 can be found in [10].

CCP is a constrained problem that imposes a lower and an upper capacity limit to the size of the clusters. One notices that most of the existing approaches for CCP restrict their search to the feasible region only, while only few approaches including GRASP-PR [10], GevPR-HMP [31], GQAP [31], and TSONO [29] are allowed to visit infeasible solutions. In this work, we are interested in search algorithms that examine both the feasible and the infeasible space in search of improved solutions. For this purpose, we introduce a highly effective tabu search (denoted as FITS) that alternates between feasible and infeasible regions, bringing more flexibility into the search process. In addition, we propose the first population-based memetic algorithm (MA) for CCP. It uses FITS as the local optimization mechanism, and incorporates a dedicated cluster-based crossover to transfer pertinent properties ("building blocks") from parents to offspring. Experimental results on five sets of 183 benchmark instances indicate a highly competitive performance of FITS with respect to the existing state-of-the-art algorithms. Given a longer time limit, a computational comparison between FITS and MA reveals that MA is able to further improve on the performance of its underlying FITS in terms of solution quality.

The remainder of the paper is organized as follows. Section 2 presents FITS, followed by a detailed description of the proposed memetic approach in Section 3. Experimental results on a widely-used benchmark are provided in Section 4. Section 5 analyzes the contribution of the key algorithmic ingredient to the performance of the proposed algorithms. Furthermore, we motivate the choice for the crossover used by MA, prior to conclusions drawn in the last section.
## 2 Feasible and infeasible exploration with tabu search

### 2.1 Main framework

<caption>**Algorithm 1** Main scheme of FITS</caption>

Require: Graph $G = (V, E)$
Ensure: Best found solution $S^*$
1: $S \leftarrow InitialSolution(G) / *Section 2.2*/$
2: Initialize tabu_list
3: $S^* \leftarrow S / *S$ is a feasible solution*/
4: **while** stopping condition is not verified **do**
5: / *feasible local search phase*/
6: ($S, S_{local\_best}$) $\leftarrow$ feasible_local_search($S$) / *Section 2.3*/
7: **if** $f(S_{local\_best}) > f(S^*)$ **then**
8: $S^* \leftarrow S_{local\_best}$
9: **end if**
10: / *infeasible local search phase*/
11: ($S, S_{local\_best}$) $\leftarrow$ infeasible_local_search($S$) / *Section 2.4*/
12: **if** $f(S_{local\_best}) > f(S^*)$ **then**
13: $S^* \leftarrow S_{local\_best}$
14: **end if**
15: **end while**

Instead of confining the search process to feasible regions, a number of studies on highly constrained problems [9,12,21,26,35] have shown that the consideration of infeasible solutions during the search may help to better explore the search space. Based on this observation, the proposed tabu search alternates between a feasible local search phase (FLS for short) that only examines feasible solutions, and an infeasible local search phase (InfLS for short) where the capacity constraint is relaxed in a controlled manner. The two phases play different roles in the search process - FLS ensures an intensified exploitation in a relevant search region, while InfLS is used to introduce more freedom (diversification) into the search. By alternating between these two complementary phases, FITS is expected to explore various zones of the search space without being easily trapped in a local optimum.

Algorithm 1 summarizes the general framework of FITS. Starting from a feasible solution generated with a construction procedure (Section 2.2), FITS first enters the FLS phase that is based on the best-improvement strategy with a joint use of three types of move operators (Section 2.3.2). This phase terminates as soon as the search is deemed to be trapped in a deep local optimum, i.e., if the best found solution cannot be improved for $N_{cons}$ consecutive iterations. The algorithm then switches to InfLS that relies on a penalty-based evaluation function to guide the search to move towards new search regions. The stopping condition is typically a time limit or a fixed number of iterations.
## 2.2 Initial solution

The starting point for the search is a feasible solution generated by means of two randomized construction methods similar to those used in [17,24]. The first method consists in two stages, where the first stage performs the following steps: (i) randomly select a node $v$ from the set of unassigned nodes, and randomly choose a cluster $g$ from the set of clusters whose lower capacity constraint is not satisfied; (ii) allocate $v$ to cluster $g$. The two steps are repeated until all clusters satisfy the lower capacity constraint. Once the first stage is completed, the proposed construction method enters the second stage that: (i) randomly picks an unassigned node $v$ and a cluster $g$ such that $size[g] + w_v \le U_g$, where $size[g]$ and $w_v$ represent respectively the current weight of cluster $g$ and the weight of node $v$; (ii) assign $v$ to $g$. The second stage of this procedure terminates as soon as all the nodes have been assigned.

As observed in our preliminary experiments, the above described method often fails to find a feasible assignment of all the nodes when the upper capacity limit of clusters is very tight. Consequently, we propose the second construction method which constitutes a slight modification of the first method. Instead of randomly choosing a node $v$ in both stages of the first construction method, an unassigned node $v$ is selected such that $v$ has the largest weight (ties broken randomly). The other steps are kept unchanged.

The time complexity of the construction method is $O(n * p)$.

## 2.3 Feasible local search (FLS)

FLS searches for the most promising solutions in the feasible space of candidate solutions, thus ensuring that the capacity constraint is verified. It is based on the general tabu search framework [18] and a combined use of three complementary move operators as described in the following subsections.

### 2.3.1 Feasible search space and evaluation function

A candidate solution to CCP is any partition of the node set $V$ into $p$ subsets $C_1, C_2, ..., C_p$, also called clusters. The search space, including both feasible and infeasible solutions, is then formally defined as:

$$ \Omega = \{ \{C_1, C_2, ..., C_p\} : \bigcup_{i=1}^{p} C_i = V, C_i \cap C_j = \emptyset \} \quad (5) $$

where $i \neq j$, $1 \le i, j \le p$. Notice that an infeasible solution may contain one
or more empty clusters.

The feasible search space includes the set of all the candidate solutions $\Omega_f \subset \Omega$ satisfying the capacity constraints:

$$ \Omega_f = \{ \{C_1, C_2, \dots, C_p\} : L_i \le |C_i| \le U_i, \cup_{i=1}^p C_i = V, C_i \cap C_j = \emptyset \} \quad (6) $$

where $i \neq j$, $1 \le i, j \le p$ and $|C_i|$ represents the total weight of the nodes in cluster $i$ (i.e., $|C_i| = \sum_{u \in C_i} w_u$).

To evaluate the quality of each candidate solution $s = \{C_1, C_2, \dots, C_p\}$ in $\Omega_f$, the evaluation function is equivalent to the objective function which sums up the edge weights associated to endpoints in the same cluster:

$$ f(s) = \sum_{g=1}^{p} \sum_{i,j \in C_g, i < j} c_{ij} \quad (7) $$

### 2.3.2 Neighborhood Structures

As previously mentioned, the neighborhood exploited by FLS is defined by a joint use of three basic move operators, which have previously been employed in [7,10,24,29,30]. These operators are briefly described as follows:

**OneMove operator:** Given a solution $s = \{C_1, C_2, \dots, C_p\}$, OneMove transfers a node $v$ from its original cluster $i$ to another cluster $j$ such that the capacity constraint is respected, i.e., $|C_i| - w_v \ge L_i$ and $|C_j| + w_v \le U_j$. To rapidly evaluate the gain value for each candidate move, our algorithm employs a fast incremental evaluation technique similar to that used in [6,24,34,37]. The main idea is to maintain an incremental matrix $\gamma$, where each element $\gamma[v][g]$ represents the sum of the edge weights between $v$ and other nodes located in cluster $g$ of the current solution, i.e., $\gamma[v][g] = \sum_{u \in C_g} c_{uv}$. Let OneMove($v, i, j$) denote a move that consists in transferring a node $v$ from cluster $i$ to cluster $j$, the corresponding gain value can be conveniently calculated as:

$$ \Delta_f(OneMove(v, i, j)) = \gamma[v][j] - \gamma[v][i] $$

After each OneMove operation, a subset of values in $\gamma$ affected by the move is updated as follows: $\gamma[u][i] = \gamma[u][i] - c_{uv}$, $\gamma[u][j] = \gamma[u][j] + c_{uv}$, $\forall u \in V$. The complexity to update $\gamma$ after a OneMove operation is $O(n)$.
**SwapMove operator:** This move operator swaps two nodes v and u from two different clusters i and j, such that the capacity constraint is maintained. Let SwapMove(v, u) denote a swap move, the associated move gain can be efficiently obtained as:

$$ \Delta_f(\text{SwapMove}(v, u)) = (\gamma[v][j] - \gamma[v][i]) + (\gamma[u][i] - \gamma[u][j]) - 2c_{vu} $$

Since a *SwapMove* can be decomposed into two consecutive *OneMove* operations, $\gamma$ is updated in two steps as for the corresponding *OneMove* moves. Clearly, updating $\gamma$ after a *SwapMove* operation can also be achieved in $O(n)$ time.

**2-1 Exchange operator:** Let v, u and z be three nodes where v and u are located in the same cluster i, while z belongs to another cluster j. The 2-1 Exchange transfers v and u from cluster i to cluster j and simultaneously moves z from j to i, while respecting the capacity restriction of i and j. Let Exchange(v, u, z) denote such a move, the resulting move gain can be computed as:

$$ \Delta_f(\text{Exchange}(v, u, z)) = (\gamma[v][j] - \gamma[v][i]) + (\gamma[u][j] - \gamma[u][i]) + (\gamma[z][i] - \gamma[z][j]) + 2(c_{vu} - c_{vz} - c_{uz}) $$

Since a 2-1 *Exchange* move can be decomposed into three consecutive *OneMove* operations, the matrix $\gamma$ is consecutively updated three times according to the corresponding *OneMove* moves.

### 2.3.3 Exploration of the feasible search space

The general scheme of FLS is summarized in Algorithm 2. Starting from a feasible solution, FLS selects at each iteration the best non-prohibited move (i.e., non-tabu move of the highest gain) from the union of *OneMove*, *SwapMove* and 2-1 *Exchange* moves, where ties are broken at random. Obviously, such a combined neighborhood ensures an intensified examination of the feasible search space, and thus enhances the capacity of finding improved feasible solutions. To avoid short-term cycling, each time a node v is moved from its original cluster C, it is forbidden to move v back to C for the next tt iterations (tt is called the *tabu tenure*). Along with this rule, an aspiration criterion is applied to allow a move, regardless of its tabu status, if it leads to an improved best found solution. The exploration of the feasible search space terminates if no improvement is achieved in the consecutive $N_{cons}$ iterations ($N_{cons}$ is called the *search depth*). At this stage, the algorithm switches to the Infeasible Local Search (InfLS) phase that introduces a greater diversity, as the search is deemed to be trapped in a deep local optimum.
Aside from the diversification incurred during InfLS, FLS additionally incorporates a shake procedure similar to that used in [24]. The shake procedure is applied periodically, and consists in performing a random move from the combined feasible *OneMove* and *SwapMove* neighborhoods. This operation is repeated $\eta$ times, where $\eta$ is the shake strength.

## 2.4 Infeasible local search (InfLS)

The basic idea of InfLS is to relax the capacity constraint so as to allow the algorithm to visit some intermediate infeasible solutions. In this way, a larger number of moves become available, enabling transitions between structurally different high-quality feasible solutions.

<caption>**Algorithm 2 Feasible Local Search**</caption>

**Require:** Initial solution $s$
**Ensure:** Final solution $s$, best solution $s_{local\_best}$ found during this phase
1: $s_{local\_best} \leftarrow s$
2: $NI \leftarrow 0$ /*number of consecutive iterations without improvement of $s_{local\_best}$*/
3: $Iter1 \leftarrow 0$ /*iteration counter*/
4: Initialize *tabu\_list*
5: **while** $NI < N_{cons}$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;Choose the best allowed move $m \in \{OneMove \cup SwapMove \cup 2-1\}$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s \leftarrow s \oplus m$ /*Perform the best move*/
8: &nbsp;&nbsp;&nbsp;&nbsp;Update *tabu\_list*
9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $f(s) > f(s_{local\_best})$ **then**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_{local\_best} \leftarrow s$
11: &nbsp;&nbsp;&nbsp;&nbsp;**else**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$NI \leftarrow 0$
13: &nbsp;&nbsp;&nbsp;&nbsp;**else**
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$NI \leftarrow NI + 1$
15: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
16: &nbsp;&nbsp;&nbsp;&nbsp;**if** $(Iter1 + 1)\%\delta==0$ **then**
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Shake()
18: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
19: **end while**
20: **return** $(s, s_{local\_best})$
**Algorithm 3** Infeasible Local Search (InfLS)

**Require:** Feasible solution *s* returned by FLS

**Ensure:** Best feasible solution found during InfLS $s_{local\_best}$, final feasible solution $s_{final}$

1: $s_{tmp} \leftarrow s$ /*$s_{tmp}$ is a duplicate of the **starting** feasible solution $s$*/

2: flag\_fs $\leftarrow$ false /*flag\_fs is a boolean variable that indicates whether a feasible solution was encountered during InfLS*/

3: $s_{local\_best} \leftarrow s$

4: penalty\_count $\leftarrow$ 0

5: penalty\_factor $\leftarrow$ 2

6: $MI \leftarrow 0$

7: Initialize tabu\_list

8: **while** $MI \le M$ **do**

9: Choose the best allowed move $m \in \{\text{OneMove} \cup \text{SwapMove} \cup \text{2-1 Exchange}\}$

10: $s \leftarrow s \oplus m$ /*Perform the best move*/

11: Update tabu\_list

12: **if** *s* is a feasible solution **then**

13: **if** $f(s) > f(s_{local\_best})$ **then**

14: $s_{local\_best} \leftarrow s$

15: **end if**

16: **else**

17: penalty\_count $\leftarrow$ penalty\_count + 1

18: **end if**

19: $MI \leftarrow MI + 1$

20: **if** $(MI + 1)\%\lambda==0$ **then**

21: **if** penalty\_count > $\mu_1$ **then**

22: penalty\_factor $\leftarrow$ penalty\_factor * $\tau$

23: **else if** penalty\_count < $\mu_2$ **then**

24: penalty\_factor $\leftarrow$ penalty\_factor/$\tau$

25: **end if**

26: penalty\_count $\leftarrow$ 0

27: **end if**

28: **if** *s* is a feasible solution **then**

29: $s_{final} \leftarrow s$

30: flag\_fs $\leftarrow$ true

31: **end if**

32: **end while**

33: **if** flag\_fs == false **then**

34: $s_{tmp} \leftarrow \text{Shake()}$ /*apply the shake procedure to $s_{tmp}$, Section 2.3.3*/

35: $s_{final} \leftarrow s_{tmp}$

36: **end if**

37: **return** ($s_{final}$, $s_{local\_best}$)

2.4.1 *Evaluation function and neighborhood structures*

To evaluate the quality of a solution $s \in \Omega$ during InfLS, we employ a penalty-
based evaluation function $f_p$ which is a linear combination of the basic eval-
uation function f (Equation. 7) and a penalty function associated with the
degree of solution infeasibility:

$$
f_p(s) = \sum_{g=1}^{p} \sum_{i,j \in C_g, i < j} c_{ij} - \beta \times EX(s) \quad (8)
$$

where $\beta$ is a self-adjustment penalty parameter that controls the degree of in-
feasibility introduced into the search. $EX(s)$ is the total degree of infeasibility
of $s$ defined as $EX(s) = \sum_{g=1}^{p} o_g$, where

$$
o_g = \begin{cases} L_g - |C_g|, & \text{if } |C_g| < L_g \\ |C_g| - U_g, & \text{if } |C_g| > U_g \\ 0, & \text{otherwise} \end{cases} \tag{9}
$$

The InfLS phase employs the same three basic move operators (*OneMove*, *SwapMove* and 2-1 *Exchange*) defined in Section 2.3.2, but without any capacity restriction. We further use a fast incremental evaluation technique to effectively calculate the move gain that corresponds to the change in the penalty-based evaluation function $f_p$. Specifically, for a given move denoted as *mv* (*mv* = *OneMove*, *SwapMove* or 2-1 *Exchange*), the move gain of *mv* can be defined as $\Delta_f(\textit{mv}) = \Delta_f(\textit{mv}) - \beta \times \Delta_{EX}(\textit{mv})$. In addition to the incremental matrix $\gamma$ (see Section 2.3.2), another vector $\omega$ is maintained where each element $\omega_g$ represents the total weight of nodes contained in cluster $g$. Since all moves induced by *OneMove*, *SwapMove* and 2-1 *Exchange* operators only involve two clusters, the weight of these two clusters after each move can be directly calculated by adding or subtracting the weight of the added or removed nodes. Furthermore, the move gain associated to this change can easily be updated as described in Equation. 9. The complexity of the above gain update procedure is $O(1)$.

2.4.2 Exploration with InfLS

While both InfLS and FLS rely on the tabu search strategy, the main difference between these procedures lies in the previously described evaluation functions. The main scheme of InfLS is summarized in Algorithm 3.

During the search process, the variable $\beta$ of the evaluation function (see Equation. (8)) is periodically updated depending on the penalty counter (*penalty_count*) which records the number of times a feasible solution has been found during $\lambda$ consecutive iterations ($\lambda$ is a parameter). Recall that $\beta$ controls the degree
of infeasibility introduced into the search. More precisely, $\beta$ is increased by a multiple of $\tau$ if $penalty\_count > \mu_1$, and is divided by $\tau$ if $penalty\_count < \mu_2$ ($\tau$, $\mu_1$ and $\mu_2$ are parameters). Furthermore, the best found feasible solution $s_{local\_best}$ is updated with the current solution $s$ if an improved feasible solution has been found. InfLS terminates after $M$ iterations ($M$ is a parameter), followed by the FLS phase. The starting point for the next round of the FLS search is the most recently encountered feasible solution $s_{final}$ returned by InfLS.

Finally, if no feasible solution is found during the InfLS process, the starting feasible solution $s$ returned by FLS is **perturbed** with the shake procedure (Section 2.3.3) and is then returned as the output of InfLS. Note that the shake procedure explores feasible solutions only thus resulting in a feasible solution. Algorithm 3 summarizes the general procedure of the InfLS phase, in which we use a boolean variable $flag\_fs$ to indicate whether a feasible solution is encountered during the InfLS phase. It is important to mention that FLS and InfLS use two separate tabu lists, which are critical to the performance of the two local search phases as they prevent the search from short-term cycling. When switching back to FLS, the tabu list is re-initialized before entering the main loop.

### 3 Memetic algorithm

**Algorithm 4** Main scheme of MA

**Require:** Graph $G = (V, E)$

**Ensure:** Best solution $S^*$ found so far

1: Initialize population $P = \{S_1, S_2, ..., S_{|P|}\}$

2: $S^* \leftarrow Best(P)$

3: **while** Time does not exceed $t_{max}$ **do**

4: Randomly select two parent solutions $S_i \in P$ and $S_j \in P$

5: $S_c \leftarrow Crossover(S_i, S_j) /*Section 3.1*/$

6: $S_c \leftarrow FITS(S_c) /*Section 2.1*/$

7: **if** $f(S_c) > f(S^*)$ **then**

8: $S^* \leftarrow S_c$

9: **end if**

10: $POP \leftarrow Pool\_Updating(S_c, P) /*Section 3.2*/$

11: **end while**

Relying on the combined exploitation power of local optimization and exploration capacity of population-based search, Memetic Algorithm (MA) [32] is an effective hybrid framework for tackling a variety of difficult combinatorial problems.

The main scheme of our MA for CCP is given in Algorithm 4. The algo-
rithm consists of four basic components: a population initializing procedure, a crossover operator, the FITS procedure for local improvement and a population updating rule. Each solution from the initial population is obtained with the two randomized construction methods described in Section 2.2, and then further improved with our FITS method presented in Section 2. At each cycle (generation) of MA, two parent solutions are randomly selected from the population, and then recombined by means of the crossover operator to generate an offspring solution (Section 3.1). This new offspring is then improved by applying a fixed number of iterations of our FITS algorithm (Section 2.1). Finally, the population updating rule decides whether the improved offspring should be inserted into the population and which existing solution should be replaced (Section 3.2). This process is repeated until a predefined stopping condition (usually a fixed number of generations or time limit) is reached.

## 3.1 Cluster-based crossover

<caption>**Algorithm 5 Cluster-based crossover**</caption>

**Require:** Two randomly selected parents $s^1 = \{C_1^1, C_2^1, \dots, C_p^1\}, s^2 = \{C_1^2, C_2^2, \dots, C_p^2\}$
**Ensure:** Offspring $s^o = \{C_1^o, C_2^o, \dots, C_p^o\}$
1: $l \leftarrow 1$
2: **while** $l \le p$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** $l \% 2 == 0$ **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Select a cluster $C_* \in s^1$ with the maximum sum of edge weights
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$C_l^o \leftarrow C_*$
6: &nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Select a cluster $C_* \in s^2$ with the maximum sum of edge weights
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$C_l^o \leftarrow C_*$
9: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: Remove the subset $C_l^o$ of nodes from $s^1$ and $s^2$
11: $l \leftarrow l + 1$
12: **end while**
13: Assign in a greedy manner the unassigned nodes $V - \{C_1^o \cup C_2^o \cup \dots \cup C_p^o\}$

Crossover operator is one of the key elements of a population-based algorithm. It is well-known that a crossover's efficiency on a given optimization problem crucially depends on its ability to preserve pertinent properties ("building blocks") from parents to offspring [19]. In the context of CCP, a building block may be defined as a cluster (i.e., group or subset of a graph partition), where the aim is to maximize the sum of edge weights whose two associated endpoints belong to the given cluster. As CCP can be classified as a grouping problem [13], it is more natural and straightforward to manipulate groups of objects (i.e., clusters) rather than individual objects. Furthermore,
an analysis on a sample of locally optimal CCP solutions (see Section 5.3.1) discloses a high percentage of nodes that are always grouped together across high quality solutions, which provides a strong motivation for preserving the grouped nodes (i.e., cluster) from parent individuals to offspring solution. The proposed cluster-based crossover (CBX) is further inspired by the Greedy Partition Crossover (GPX) used for the classic graph coloring problem [15].

Given two parent solutions, CBX generates an offspring $s^o = \{C_1^o, C_2^o, ..., C_p^o\}$ in two sequential stages as summarized in Algorithm 5. The first stage performs $p$ iterations (i.e., one iteration per cluster), where each iteration $l$ consists in selecting a cluster $C_*$ from a reference parent such that the weighted sum of edges with both endpoints in $C_*$ is maximized. Cluster $C_*$ then becomes the $l^{th}$ building block of $s^o$, followed by the removal of all the nodes contained in $C_*$ from both parent individuals. The reference parent is selected between $s^1$ and $s^2$ in an alternating manner. Note that the first crossover stage may result in a partial solution as some nodes may have been left unassigned. The second stage of the crossover process is a greedy construction method that consists in selecting an unassigned node $v$ and inserting it into cluster $g$ of the offspring solution, such that $L_g \le w_v + |C_g^o| \le U_g$ while maximizing the objective function value defined in Equation. 7. This process is repeated until all the nodes are assigned.

## 3.2 Population updating strategy

Population update strategy is another key element of a MA algorithm whose main role is to maintain a healthily diversified population throughout the search. To avoid premature convergence, we employ a quality-and-distance pool updating strategy which takes into account both the solution quality and the distance between individuals in the population to decide whether a new offspring should be introduced into the population. For this purpose, the distance $Dist(S_a, S_b)$ between two solutions $S_a$ and $S_b$ is defined as the minimum number of one-move steps required to transform $S_b$ to $S_a$ [28]. Given a population $P = \{S_1, S_2, ..., S_{|P|}\}$, the distance between a solution $S_i$ ($i \in 1, 2, ..., |P|$) and $P$ is computed as:

$$D_{S_i,P} = \min\{Dist(S_i, S_j) | S_j \in P, S_j \neq S_i\} \qquad (10)$$

The main scheme of the population update procedure, which is similar to that used in [28,39], is provided in Algorithm 6.

First, offspring $S_0$ is tentatively added to $P$ resulting in $P' = P \cup \{S_0\}$. The quality-and-distance score function $R$ is then applied to rank each solution
$S_i \in P'$:

$$R(S_i, P') = \alpha \mathcal{X}(f(S_i)) + (1 - \alpha) \mathcal{X}(D_{S_i, P'}) \quad (11)$$

where $\alpha$ is a parameter set to 0.6 according to [28], and $f(S_i)$ is the objective value of $S_i$. $\mathcal{X}(\cdot)$ is a function defined as:

$$\mathcal{X}(y) = \frac{y - y_{min}}{y_{max} - y_{min} + 1}$$

where $y_{max}$ and $y_{min}$ are the maximum and the minimum possible values of $y$ respectively. Finally, the solution $S_w$ with the smallest score is removed from the population to make space for offspring $S_0$.

# 4 Computational experiments

This section provides an extensive assessment of the proposed algorithms on a well-known set of 133 benchmark instances from CCPLIB, as well as on two new groups of 50 large instances recently generated in [7]. To evaluate the effectiveness of the proposed approaches, we perform comparisons with several state-of-the-art algorithms from the literature. For the ease of reading and for the sake of clarity, Table 1 shows the list of the proposed and the reference algorithms from the CCP literature.

<caption>**Algorithm 6** Population update strategy</caption>

Require: Offspring $S_0$, population $P = \{S_1, S_2, ..., S_{|P|}\}$
Ensure: Updated population $P = \{S_1, S_2, ..., S_{|P|}\}$
1: Tentatively add $S_0$ to $P$: $P' = P \cup \{S_0\}$
2: **for** $i = 0, 1, ..., |P|$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;Calculate the distance between $S_i$ and $P'$ according to Eq.(10)
4: &nbsp;&nbsp;&nbsp;&nbsp;Calculate the goodness score $R(S_i, P')$ of $S_i$ according to Eq.(11)
5: **end for**
6: Identify the solution $S_w$ with the smallest goodness score in $P'$: $S_w = \min\{R(S_i, P') | i = 0, ..., |P|\}$
7: **if** $S_w \neq S_0$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;Replace $S_w$ with $S_0$: $P = P \cup \{S_0\} \setminus \{S_w\}$
9: **end if**
## 4.1 Benchmark instances

The instances from CCPLIB<fnref n="1" /> can be grouped into three sets:

* DB (10 instances): This set was introduced by Deng and Bard [10] for the Maximally Diverse Grouping Problem (MDGP), and adapted for CCP in [29] by generating node weights with a uniform distribution in the range [0, 10]. These instances are characterized by $n = 82, p = 8, L_g = 25, U_g = 75$.

* RanReal (40 instances): This set was originally proposed in [17] and first adapted for CCP in [29] by generating node weights with a uniform distribution in the range [0, 10]. It includes 20 instances with $n = 240, p = 12, L_g = 75, U_g = 125$, and another 20 instances with $n = 480, p = 20, L_g = 100, U_g = 150$. The edge weights are real numbers randomly generated in the range [0, 100].

* MM (83 instances): This set was introduced by Morán-Mirabal et al. [31] with $n \in \{20, 30, 40, 100, 200, 400\}$ and $p \in \{5, 10, 15, 25, 50\}$. The edge weights are real numbers, while $L_g$ and $U_g$ are respectively set to 0 and a real number that differs for each instance. The set is widely used in the literature for the handover minimization problem.

Additionally, we perform experiments on the following two groups of 50 large instances<fnref n="2" /> from [7]:

* RanReal960 (30 instances): This set consists of 3 subsets. Each subset contains 10 instances characterized as follows:

* $n = 960, p = 30, L_g = 120, U_g = 180$;

* $n = 960, p = 40, L_g = 90, U_g = 135$;

* $n = 960, p = 60, L_g = 60, U_g = 90$;

* MDG (20 instances): This set includes 20 instances with $n = 2000, p = 50, L_g = 200, U_g = 300$. The edge weights and the node weights are generated using the same method as in [11].

## 4.2 Experimental protocol

The proposed FITS algorithm requires eight parameters: tabu tenure ($tt$), search depth of FLS ($N_{cons}$), shake frequency ($\delta$) and shake strength ($\eta$) of FLS, update frequency ($\lambda$) of the self-adjustment penalty $\beta$ in InfLS, update coefficients of $\beta$ ($\tau, \mu_1, \mu_2$) in InfLS, and the maximum number of InfLS iterations ($M$). MA requires two additional parameters: the population size ($|P|$) and the number of FITS iterations ($Iter$). To determine the appropriate

<footnote n="1">¹ http://www.optsicom.es/ccp/</footnote>

<footnote n="2">² http://www.mi.sanu.ac.rs/~nenad/ccp/</footnote>
<table><caption>Table 1
List of the reference algorithms for CCP and its equivalent HMP.</caption><thead><tr><th>Algorithm name</th><th>Reference</th><th>Search strategy</th></tr></thead><tbody><tr><td>FITS</td><td>-</td><td>A tabu search alternating between exploration in feasible and infeasible search space</td></tr><tr><td>MA</td><td>-</td><td>A memetic algorithm that extends FITS with a dedicated cluster-based crossover operator</td></tr><tr><td>GRASP-PR</td><td>[10](2011)</td><td>A reactive GRASP</td></tr><tr><td>GevPR-HMP</td><td>[31](2013)</td><td>A GRASP combined with an evolutionary path-relinking algorithm in which a repair procedure is applied to achieve feasibility</td></tr><tr><td>GQAP</td><td>[31](2013)</td><td>A GRASP method with a new variant of path-relinking dealing with infeasibilities</td></tr><tr><td>BRKGA</td><td>[31](2013)</td><td>A biased random-key genetic algorithm using a parameterized uniform crossover</td></tr><tr><td>GRASP</td><td>[29](2015)</td><td>A simplified GRASP</td></tr><tr><td>TS</td><td>[29](2015)</td><td>A tabu search algorithm exploiting the 2-1 exchange neighborhood</td></tr><tr><td>GRASP+TS</td><td>[29](2015)</td><td>A hybrid combining GRASP with tabu search</td></tr><tr><td>TS.SO</td><td>[29](2015)</td><td>A tabu search with strategic oscillation that considers infeasible solutions</td></tr><tr><td>IVNS</td><td>[24](2016)</td><td>An iterated variable neighborhood search combining an extended variable neighborhood descent with a randomized shake procedure</td></tr><tr><td>GRASP2-1</td><td>[30](2017)</td><td>A new GRASP method in which the improvement procedure performs 2-1 exchanges</td></tr><tr><td>IG</td><td>[30](2017)</td><td>An iterated greedy method alternating between destructive and constructive phases</td></tr><tr><td>IG-GRASP</td><td>[30](2017)</td><td>A hybrid between GRASP2-1 and iterated greedy method</td></tr><tr><td>GVNS</td><td>[7](2017)</td><td>A general variable neighborhood search that follows the standard VNS approach including more levels of shaking</td></tr><tr><td>SGVNS</td><td>[7](2017)</td><td>A skewed general variable neighborhood search that allows moves to inferior solutions</td></tr></tbody></table>

<table><caption>Table 2
Settings of the parameters.</caption><thead><tr><th>Parameter</th><th>Section</th><th>Description</th><th>Considered values</th><th>Final value</th></tr></thead><tbody><tr><td>N<sub>cons</sub></td><td>2.3</td><td>search depth of each FLS phase</td><td>{500, 700, 1000, 1500, 2000}</td><td>1000</td></tr><tr><td>M</td><td>2.4</td><td>maximum number of iterations of each InfLS phase</td><td>{100, 150, 200, 250, 300}</td><td>200</td></tr><tr><td>tt</td><td>2.3,2.4</td><td>tabu tenure</td><td>{5, 7, 10, 12, 15}</td><td>10</td></tr><tr><td>δ</td><td>2.3</td><td>frequency of shake</td><td>{300, 400, 500, 600, 700}</td><td>500</td></tr><tr><td>η</td><td>2.3</td><td>shake strength</td><td>{0.06*n, 0.08*n, 0.10*n, 0.12*n, 0.14*n}</td><td>0.10*n</td></tr><tr><td>Iter</td><td>3</td><td>number of iterations of FITS in MA</td><td>{5000, 8000, 10000, 12000, 15000}</td><td>10000</td></tr><tr><td>|P|</td><td>3</td><td>size of population</td><td>{5, 7, 10, 13, 15}</td><td>5</td></tr><tr><td>λ</td><td>2.4</td><td>update frequency of β in InfLS</td><td>-</td><td>5</td></tr><tr><td>τ</td><td>2.4</td><td>update coefficients of β in InfLS</td><td>-</td><td>2</td></tr><tr><td>μ<sub>1</sub></td><td>2.4</td><td>update coefficients of β in InfLS</td><td>-</td><td>4</td></tr><tr><td>μ<sub>2</sub></td><td>2.4</td><td>update coefficients of β in InfLS</td><td>-</td><td>1</td></tr></tbody></table>

parameter settings for FITS and MA, we run the Iterated F-race (IFR) method [3], implemented within the IRACE package [27], on a selection of 20 RanReal instances with $n = 240$ and $n = 480$. The tuning budgets of FITS and MA are set to 500 runs with the time limit of $1.0 * n$ seconds for each run. Table 2 shows the tested and the final values obtained in the tuning process. For $\lambda$, $\tau$, $\mu_1$ and $\mu_2$, we simply adopt the values recommended in [9,20].

The proposed algorithms are coded in C++, compiled with the g++ compiler using option "-O3", and executed on an Intel E5-2670 processor (2.8GHz) with 2GB RAM running under Linux. For time scaling purposes, the execution time of the DIMACS machine benchmark<fnref n="3" /> on our system is 0.19s for graph r300.5, 1.17s for graph r400.5 and 4.54s for graph r500.5.

<footnote n="3">³ ftp://dimacs.rutgers.edu/pub/dsj/clique/</footnote>
<caption>Table 3</caption>

Statistical results for FITS and six state-of-the-art algorithms on two sets of CCP instances: DB and RanReal. The best performance is indicated in bold.

<table><thead><tr><th>Instance set</th><th>GRASP</th><th>TS</th><th>GRASP+TS</th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th></tr></thead><tbody><tr><td>DB &amp; RanReal</td><td>#Best/Avg.</td><td>8/2</td><td>4/0</td><td>9/2</td><td>14/10</td><td>10/10</td><td><b>32/40</b></td><td>29/20</td></tr><tr><td></td><td>p-value<sub>best</sub>/p-value<sub>avg</sub></td><td>7.75e-11/1.54e-12</td><td>7.75e-11/1.54e-12</td><td>2.86e-9/1.54e-10</td><td>1.25e-7/7.70e-8</td><td>1.87e-9/2.54e-10</td><td>0.88/0.02</td><td></td></tr><tr><td></td><td>Average Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td>6.66/7.56</td><td>1.33/2.42</td><td>1.35/2.00</td><td>0.26/0.40</td><td>0.22/0.63</td><td>0.20/0.36</td><td><b>0.19/0.33</b></td></tr><tr><td></td><td>AvgTime(s)</td><td>149.25</td><td><b>50.68</b></td><td>187.26</td><td>224.24</td><td>243.04</td><td>187.33</td><td>201.35</td></tr></tbody></table>

### 4.3 Comparison between FITS and the state-of-the-art algorithms on the general CCP instances

To evaluate the performance of FITS on the first two sets of instances (DB and RanReal), we provide comparisons with several state-of-the-art algorithms including GRASP [29], TS [29], GRASP+TS [29], IVNS [24], GVNS [7] and SGVNS [7]. For a fair comparison with these state-of-the-art algorithms, we use their corresponding source codes and run them on our computing platform under the same computing conditions as described in Section 4.2. GRASP, TS, GRASP+TS, IVNS were previously re-implemented by Lai et al. [24] and their source codes are available at http://www.info.univ-angers.fr/pub/hao/ccp.html. The source codes of GVNS and SGVNS were shared by the corresponding author and are available at http://www.mi.sanu.ac.rs/~nenad/ccp/. All the codes were compiled using g++ compiler with the '-O3' option. For all the algorithms in this experiment, the stopping condition is a fixed cutoff time limit $t_{max}$ set to 1.0 * n seconds, where n is the number of nodes in the given graph. Due to the stochastic nature of the algorithms, we perform 20 independent runs of each algorithm per instance.

Table 3 summarizes the statistical results for each algorithm on the instances of the DB and RanReal sets. Row '#Best/Avg.' indicates the number of cases that each algorithm outperforms the remaining approaches in terms of the best and the average objective value. The average percent deviation of the best/average result from the best solution obtained within this experiment is provided in row 'Average Dev<sub>best</sub>/Dev<sub>avg</sub>', while the average computing time (in seconds) required by each algorithm to reach its final objective value is provided in row 'AvgTime'. For each instance, we calculate the best and the average deviation (Dev<sub>best</sub> and Dev<sub>avg</sub>) as $(f^* - f)/f^* \times 100$, where f is the best or the average result and $f^*$ is the best solution obtained with all the compared algorithms. Finally, to determine whether there exists a statistically significant difference in performance between FITS and the six reference algorithms, row 'p-value<sub>best</sub>/p-value<sub>avg</sub>' provides the p-values obtained with the pairwise Wilcoxon statistical test on the best/average results. Detailed results on the DB and the RanReal benchmarks are given in the Appendix (Tables
<caption>Table 4</caption>

Statistical results of FITS and six state-of-the-art algorithms on two large instance sets: RanReal960 and MDG. The best performance is given in bold.

<table><thead><tr><th>Instance set</th><th>GRASP</th><th>TS</th><th>GRASP+TS</th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th></tr></thead><tbody><tr><td>RanReal960 #Best/Avg. &amp; MDG</td><td>0/0</td><td>0/0</td><td>0/0</td><td>0/0</td><td>0/0</td><td><b>46/46</b></td><td>4/4</td></tr><tr><td>p-value<sub>best</sub>/p-value<sub>avg</sub></td><td>1.54e-12/1.54e-12</td><td>1.54e-12/1.54e-12</td><td>1.54e-12/1.54e-12</td><td>1.14e-11/1.54e-12</td><td>0.09/0.16</td><td>2.86e-9/2.86e-9</td><td></td></tr><tr><td>Average Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td>16.94/17.44</td><td>6.60/7.36</td><td>3.77/4.47</td><td>1.27/1.70</td><td>0.61/0.80</td><td><b>0.01/0.61</b></td><td>0.89/1.07</td></tr><tr><td>AvgTime(s)</td><td><b>694.09</b></td><td>1115.02</td><td>1221.46</td><td>1251.36</td><td>1202.49</td><td>1240.53</td><td>1282.67</td></tr></tbody></table>

11, 12).

From Table 3, we observe that GRASP, TS, GRASP+TS, IVNS, GVNS, SGVNS and FITS respectively outperform the other algorithms on 8, 4, 9, 14, 10, 32 and 29 instances in terms of the best objective value. In terms of the average results, FITS achieves better performance on 20 instances, while GRASP, TS, GRASP+TS, IVNS, GVNS and SGVNS outperform the other methods on 2, 0, 2, 10, 10 and 40 instances respectively. In terms of the average percent deviation (Average $Dev_{best}/Dev_{avg}$), FITS reports the smallest deviation from the best solutions obtained within this experiment (0.19%/0.33%). Except for the comparison with SGVNS, the statistical test reveals a significant difference in performance between each of the reference algorithms ($p$-value $\le 0.05$), demonstrating the efficiency of FITS on the DB and the RanReal instances.

### 4.4 Comparison between FITS and the state-of-the-art algorithms on the large CCP instances

RanReal960 and MDG benchmarks consist of large instances recently used to assess the performance of the algorithms for CCP in [7]. A summary of the statistical results for these instances, obtained with FITS and the reference algorithms, are shown in Table 4. Detailed results are given in Tables 13 and 14 of the Appendix.

Row $p-value_{best}/p-value_{avg}$ reveals a statistically significant difference in performance between FITS and all the reference algorithms except GVNS. When considering the average percent deviation from the best-found solutions within the experiments, SGVNS outperforms all the algorithms with $Dev_{best} = 0.01\%$ and $Dev_{avg} = 0.61\%$, while FITS exhibits a better performance than GRASP, TS, GRASP+TS and IVNS.
<caption>Table 5</caption>

Statistical results of FITS and the six state-of-the-art algorithms on handover minimization instances with $n \ge 100$. The best performance is indicated in bold.

<table><thead><tr><th>Instance set</th><th></th><th>GevPR-HMP</th><th>GQAP</th><th>BRKGA</th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th></tr></thead><tbody><tr><td>MM<br/>(n<br/>100) ≥</td><td>#Best/Avg.</td><td>9/4</td><td>11/0</td><td>2/0</td><td>37/18</td><td>23/15</td><td>24/25</td><td><b>43/30</b></td></tr><tr><td></td><td>p-value<sub>best</sub>/p-value<sub>avg</sub></td><td>1.97e-8<br/>9/1.68e-8</td><td>5.51e-11<br/>9/1.97e-11</td><td>5.47e-11<br/>11/1.97e-11</td><td>0.00/0.02</td><td>1.19e-5<br/>5/0.08</td><td>7.44e-5<br/>5/0.38</td><td></td></tr><tr><td></td><td>Average<br/>Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td>1.32/1.74</td><td>8.37/10.15</td><td>3.19/3.94</td><td>0.01/0.28</td><td>0.20/1.53</td><td>0.19/0.33</td><td><b>0.00/0.20</b></td></tr><tr><td></td><td>AvgTime(s)</td><td>-</td><td>-</td><td>-</td><td>97.82</td><td><b>66.18</b></td><td>75.77</td><td>120.48</td></tr></tbody></table>

## 4.5 Comparison between FITS and the state-of-the-art algorithms on the handover minimization instances

Table 5 summarizes the statistical results reported with FITS and the six state-of-the-art algorithms on the handover minimization instances with $n \ge 100$. These reference algorithms include IVNS [24], GVNS [7], SGVNS [7] and three algorithms proposed in [31]: GevPR-HMP, GQAP and BRKGA. The handover minimization instances with $n \in \{20, 30, 40\}$ do not appear to be challenging as all the considered algorithms are able to attain the best-known solution within a very short computing time for each case. For completeness, the computational results for these instances are provided in Appendix (Table 22). In Table 5, the results reported with GevPR-HMP, GQAP and BRKGA are directly compiled from [31], and were obtained over 5 independent runs with a cutoff time set to 24 hours. This is significantly longer than the time limit used for IVNS, GVNS, SGVNS and FITS, which is set to $1.0 * n$ seconds (24 hours vs. $n \le 400$ seconds). The results for IVNS, GVNS, SGVNS and FITS were obtained across 20 independent runs under the same computing conditions as described in Section 4.2. When handling the handover minimization instances, we use the results in the form of minimization for a direct comparison. The following relation is used to transform the CCP objective function into the equivalent objective for handover minimization: $f_{min} = 2(\sum_{i<j} c_{ij} - f_{max})$, where $f_{min}$ and $f_{max}$ represent the objective values of handover minimization and CCP respectively. The symbol “-” denotes the cases when the result is not reported in the literature. Detailed results are given in Tables 15 and 16 of the Appendix.

From Table 5, we observe that GevPR-HMP, GQAP, BRKGA, IVNS, GVNS, SGVNS and FITS outperform the other reference algorithms on 9, 11, 2, 37, 23, 24 and 43 instances respectively in terms of the best objective value. In terms of the average results, FITS achieves a better performance on 30 instances, while GevPR-HMP, GQAP, BRKGA, IVNS, GVNS and SGVNS outperform the other methods on 4, 0, 0, 18, 15, 25 instances respectively. Notice that if we sum up the number of times each algorithm performed best,
we get 149 for Best and 92 Avg respectively. This is because several algorithms obtain the same best objective value and the same average objective value on some instances. In terms of the average percent deviation of the best/average results from the best solutions obtained within this experiment, FITS shows the best performance with $Dev_{best} = 0.00\%$ and $Dev_{avg} = 0.20\%$. Finally, the p-values of the Wilcoxon pairwise test (row 'p-value_{best}/p-value_{avg}') show a statistically significant difference in the best performance between FITS and the six reference approaches with $p-value \le 0.05$, which shows the benefit of FITS on the handover minimization instances with $n \ge 100$.

## 4.6 Time-to-target analysis

To further compare the performance between FITS and the reference algorithms, we apply the time-to-target (TTT) analysis which identifies the empirical probability distribution of the time required to achieve a given target value [1]. We conduct this TTT experiment by executing 100 independent runs of GRASP, TS, GRASP+TS, IVNS, GVNS, SGVNS and FITS on each instance. For each instance/target pair, the running times are sorted in an increasing order. We associate with the *i*-th sorted running time $t_i$ a probability $p_i = (i-0.5)/100$, and plot the points $(t_i, p_i)$. In this experiment, in order to allow all the algorithms to reach the target in all runs, the target value is set to be a value slightly smaller than the best obtained objective value. Fig. 1 illustrates the results for the compared algorithms on instances RanReal240_05, RanReal240_09, RanReal240_16, RanReal480_05, RanReal480_14, RanReal480_18, RanReal960_02.30, RanReal960_06.30, RanReal960_07.40, RanReal960_05.60, MDG-a_23 and MDG-a_35 which are randomly selected from three groups of the largest benchmark instances (RanReal, RanReal960 and MDG). From Fig. 1, we observe that FITS has the highest probability of reaching the target result with the shortest computing time on instances RanReal240_05, RanReal240_09, RanReal240_16, RanReal480_05, RanReal960_02.30 and RanReal960_07.40, and is the third best performing algorithm (after SGVNS and GVNS) on instances RanReal480_18, RanReal960_06.30, RanReal960_05.60, MDG-a_23 and MDG-a_35. We conducted the TTT experiments on other instances and observed similar behavior. Therefore, this experiment confirms that FITS competes very favorably with the reference algorithms GRASP, TS, GRASP+TS, IVNS, GVNS and SGVNS.

## 4.7 Comparison between FITS and MA

In this section, we additionally compare FITS and MA on the first two sets (DB and RanReal) of CCP instances and the handover minimization instances with $n \ge 100$. For this comparison, each algorithm is executed 20 times per
<figure><img src="image_3.png" /><figcaption>(a) RanReal240_05</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) RanReal240_09</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) RanReal240_16</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(d) RanReal480_05</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(e) RanReal480_14</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(f) RanReal480_18</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(g) RanReal960_02.30</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(h) RanReal960_06.30</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(i) RanReal960_07.40</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(j) RanReal960_05.60</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(k) MDG-a_23</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(l) MDG-a_35</figcaption></figure>

<caption>Fig. 1. Probability distribution of the time required to achieve a target value.</caption>

Table 6

Comparative statistical results between FITS and MA on the first two sets (DB and RanReal) of CCP instances and the handover minimization instances with $n \ge 100$. The better performances are indicated in bold.

<table><thead><tr><th>Instance set</th><th></th><th>FITS</th><th>MA</th></tr></thead><tbody><tr><td rowspan="2">DB & RanReal</td><td>#Better1/Better2</td><td>3/7</td><td><b>25/33</b></td></tr><tr><td>Average Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td>0.03/0.11</td><td><b>0.00/0.10</b></td></tr><tr><td rowspan="2">MM ($n \ge 100$)</td><td>#Better1/Better2</td><td>0/8</td><td><b>3/19</b></td></tr><tr><td>Average Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td><b>0.00/0.15</b></td><td><b>0.00/0.05</b></td></tr></tbody></table>
Table 7

Summary of statistical results obtained with FITS and its two underlying components FLS and InfLS for the RanReal benchmark set. The best performance is indicated in bold.

<table><thead><tr><th>Instance set</th><th></th><th>FITS</th><th>FLS</th><th>InfLS</th></tr></thead><tbody><tr><td rowspan="3">RanReal</td><td>#Best/Avg.</td><td><b>35/36</b></td><td>12/4</td><td>0/0</td></tr><tr><td>p-value<sub>best</sub>/p-value<sub>avg</sub></td><td></td><td>6.23e-5/4.20e-7</td><td>2.54e-10/2.54e-10</td></tr><tr><td>Average Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td><b>0.01/0.18</b></td><td>0.03/0.21</td><td>0.33/0.53</td></tr></tbody></table>

instance with a prolonged computing time of 15.0 * n seconds. The reason behind an extended cutoff time is due to our experiences and observations from previous studies [19] indicating a slower convergence pace of an MA compared to a local search algorithm.

Table 6 summarizes the statistical comparative results between FITS and MA, while detailed results are given in Tables 17 and 18 in the Appendix. In a nutshell, MA improves on the best result reported by FITS for 28 instances, and fails to match the best solution obtained with FITS for only three instances. In terms of the average performance, MA outperforms FITS on 52 instances, and is outperformed by FITS on 15 instances. When considering the average percent deviation of the best/average results from the best solutions found within this experiment (Average *Dev<sub>best</sub>/Dev<sub>avg</sub>*), MA achieves a better performance than FITS on all the three sets of instances. Finally, for all the three sets of instances, the Wilcoxon test indicates a statistically significant difference in the best and the average performances with *p*-value = 6.437e-4 and *p*-value = 0.049 respectively. Thus, we can conclude that MA should be considered over FITS given a longer time limit.

## 5 Analysis

This section evaluates the importance of the key elements of the proposed FITS and MA algorithms: (i) the joint exploitation of feasible and infeasible search space, (ii) the best improvement strategy vs. the first improvement strategy, and (iii) the cluster-based crossover operator. The experiments presented below are carried out on a set of 40 instances from the RanReal benchmark with 20 independent executions per instance under the same computing platform as described in Section 4.2.
<figure><img src="image_15.png" /><figcaption>Fig. 2. Percentage deviation of the average result reported with FITS, FLS and ILS from the best solutions found in this experiment for the 40 RanReal instances.</figcaption></figure>

## 5.1 Analysis of the combined exploitation of feasible and infeasible search space

While a number of existing heuristics for CCP including TS [29], IVNS [24], GVNS [7] and SGVNS [7] restrict their search to the feasible regions only, a key feature of FITS and several other heuristics like GRASP-PR [10], TS_SO [6], GevPR-HMP [31] and GQAP [31] is the consideration of infeasible solutions. By alternating between feasible and infeasible local searches, FITS is able to visit various zones of the search space without being easily trapped in a local optimum. To evaluate the effectiveness of this hybrid scheme, we compare FITS with its two underlying components, namely the feasible local search (FLS) and the infeasible local search (InfLS).

Table 7 summarizes the statistical results of this analysis, while detailed results are given in the Appendix (Table 19). As observed in Table 7, it is evident that FITS outperforms both FLS and InfLS. More precisely, in terms of the best and the average performance, FITS respectively reports matching or better results than both algorithms on 35 and 36 out of the 40 instances with *p*-values of 6.23e-5/4.20e-7 and 2.54e-10/2.54e-10. We further observe that InfLS alone appears to be the weakest of the three versions on all of the tested instances. To complement this comparison, Fig. 2 plots the performances of the three algorithms on these 40 instances. For each instance and each algorithm, the y-axis shows the percent deviation of the average result from the best
Table 8

Summary of statistical results obtained with FITS and its variant FITS_FI on the 40 RanReal instances. The best performance is indicated in bold.

<table><thead><tr><th>Instance set</th><th></th><th>FITS</th><th>FITS_FI</th></tr></thead><tbody><tr><td rowspan="4">RanReal</td><td>#Best/Avg.</td><td><b>40/40</b></td><td>0/0</td></tr><tr><td>p-value<sub>best</sub>/p-value<sub>avg</sub></td><td></td><td>2.54e-10/2.54e-10</td></tr><tr><td>Average Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td><b>0.00/0.15</b></td><td>0.56/0.71</td></tr><tr><td>AvgTime(s)</td><td>249.39</td><td><b>157.44</b></td></tr></tbody></table>

solutions found in this experiment. The figure further highlights the benefit of the combined use of the feasible and the infeasible local search.

## 5.2 The best improvement strategy v.s. the first improvement strategy

As described in Section 2.1, FITS applies the best improvement strategy to select a solution from the neighborhoods induced by the three move operators, i.e., *OneMove*, *SwapMove* and 2-1 *Exchange*. To verify the importance of this feature, we create a variant of FITS (denoted by FITS_FI) that uses the first improvement strategy, where the earliest visited neighboring solution of improved quality replaces the current solution. The summary of statistical results of this comparison on the 40 RanReal instances are shown in Table 8, while detailed results are given in Table 20 in the Appendix.

From Table 8, one notices that FITS outperforms FITS_FI on all of the instances both in terms of the best and the average result (#Best/Avg.). In terms of the average percent deviation of the best/average results from the best solutions obtained within this experiment (Average Dev<sub>best</sub>/Dev<sub>avg</sub>), FITS shows a better performance than FITS_FI with p-value = 2.54e-10 and p-value = 2.54e-10 respectively. These observations confirm the usefulness of the best improvement strategy within the proposed tabu search framework. However, as expected, FITS_FI shows to be faster than FITS in terms of the average time required to reach the final solution.

## 5.3 Analysis of the cluster-based crossover

### 5.3.1 Motivation behind the cluster-based crossover

As explained in Section 3.1, the basic idea behind the cluster-based crossover is to preserve building blocks (clusters of nodes) from parent individuals to offspring solution. Such crossovers have shown to be effective when there is a large percentage of nodes that are always grouped together between high-quality local optima (including global optima which are technically speaking
<table><caption>Table 9
Percentage of nodes that are grouped together in local optima of various qualities</caption><thead><tr><th>Instance</th><th>S<sub>hq</sub></th><th>S<sub>all</sub></th><th>S<sub>lo</sub></th><th>Instance</th><th>S<sub>hq</sub></th><th>S<sub>all</sub></th><th>S<sub>lo</sub></th></tr></thead><tbody><tr><td>RanReal240_01</td><td>72</td><td>54</td><td>45</td><td>RanReal480_01</td><td>82</td><td>29</td><td>14</td></tr><tr><td>RanReal240_02</td><td>85</td><td>49</td><td>39</td><td>RanReal480_02</td><td>88</td><td>26</td><td>14</td></tr><tr><td>RanReal240_03</td><td>75</td><td>48</td><td>38</td><td>RanReal480_03</td><td>88</td><td>28</td><td>14</td></tr><tr><td>RanReal240_04</td><td>80</td><td>48</td><td>41</td><td>RanReal480_04</td><td>92</td><td>29</td><td>14</td></tr><tr><td>RanReal240_05</td><td>86</td><td>48</td><td>38</td><td>RanReal480_05</td><td>83</td><td>26</td><td>14</td></tr></tbody></table>

also local optima) [4].

Given two local optima $s^1 = \{C_1^1, C_2^1, ..., C_p^1\}$ and $s^2 = \{C_1^2, C_2^2, ..., C_p^2\}$, let $E' = \{(C_i^1, C_j^2) | i \in \{1, 2, ..., p\}, j \in \{1, 2, ..., p\}\}$ denote the set of all the $p \times p$ cluster combinations of $s^1$ and $s^2$, and let $J$ denote the set of nodes that are grouped together in both $s^1$ and $s^2$. Starting from $J = \emptyset$, we use an iterative procedure that determines the largest percentage of nodes grouped together in $s^1$ and $s^2$ with the following steps: (i) for each cluster combination $(C_i^1, C_j^2) \in E'$, compute the number of identical nodes $k_{C_i^1 C_j^2} = C_i^1 \cap C_j^2$; (ii) select a combination $(C_i^1, C_j^2) \in E'$ with the largest $k_{C_i^1 C_j^2}$ and place the common nodes into $J$ (i.e., $J = J \cup \{C_i^1 \cap C_j^2\}$); (iii) remove from $E'$ all combinations associated with $C_i^1$ and $C_j^2$. This process is repeated until $E'$ becomes empty. The percentage of nodes that are grouped together in both $s^1$ and $s^2$ is then expressed as $100\% * \frac{|J|}{|V|}$.

For this analysis, we employ a selection of 10 hard instances from the Ran-Real set. For each instance, we collect a set $S_{all}$ of local optima of different qualities, obtained after 500 independent runs of MA and FITS with different time limits. We select the top 20% (100) local optima with the largest objective values from $S_{all}$ to form the subset $S_{hq}$ of 'high-quality solutions'. Similarly, we take the bottom 20% (100) with the smallest objective values to form the subset $S_{lo}$ of 'low-quality solutions'. Table 9 shows the percentages of common node groupings across all the local optima in $S_{hq}$, $S_{all}$ and $S_{lo}$ respectively. From these results, we conclude that the percentage of nodes that are grouped together throughout each of the high-quality local optima from $S_{hq}$ is very large, ranging from 72% to 92%. Assuming that high-quality solutions might be close to an optimal solution or could themselves constitute optimal solutions, it is very likely that these clusters might form the building blocks of a global optimum.

### 5.3.2 Comparison with the uniform crossover

To evaluate the benefit of the cluster-based crossover that transfers pertinent properties from parents to offspring, we compare it with a standard uniform crossover where each node is randomly transferred to the same cluster as in one of the two parents. As the resulting offspring may violate the capacity constraint, the uniform crossover proceeds next by moving a randomly selected
<caption>Table 10</caption>

Comparison of the two MA versions using a uniform and a cluster-based crossover respectively on the 40 RanReal instances. The best performance is indicated in bold.

<table><thead><tr><th>Instance set</th><th></th><th>Uniform CX</th><th>Cluster-based CX</th></tr></thead><tbody><tr><td rowspan="4">RanReal</td><td>#Best/Avg.</td><td>2/0</td><td><b>31/40</b></td></tr><tr><td>p-value<sub>best</sub>/p-value<sub>avg</sub></td><td>4.46e-7/2.54e-10</td><td></td></tr><tr><td>Average Dev<sub>best</sub>/Dev<sub>avg</sub>(%)</td><td>0.56/0.71</td><td><b>0.00/0.15</b></td></tr><tr><td>AvgTime(s)</td><td><b>2898.81</b></td><td>3856.70</td></tr></tbody></table>

node from the highest to the lowest weight cluster until the solution feasibility is reached. For this experiment, the other MA components are left unchanged. The time limit is set to 15.0 * n seconds per execution.

Table 10 summarizes the statistical results for each MA version on the 40 RanReal instances, while detailed results are given in Table 21 in the Appendix. Although the cluster-based crossover results in longer computing time than the uniform crossover due to a higher complexity, it clearly outperforms the uniform crossover in terms of both the best and the average results with $p$-value = 4.46e-7 and $p$-value = 2.54e-10 respectively. Indeed, out of the 40 instances, the cluster-based crossover is outperformed by the uniform crossover only on two instances. These observations highlight the importance of preserving important building blocks from parents to children in case of CCP.

# 6 Conclusion

We presented two highly effective heuristics for the Capacitated Clustering Problem (CCP): a tabu search approach (denoted as FITS) that alternates between exploration in feasible and infeasible search space regions, and a Memetic Algorithm (MA) that extends FITS with a dedicated cluster-based crossover and a quality-and-distance pool updating strategy. The computational results on five sets of 183 CCP instances indicate that both FITS and MA compete favorably with the current state-of-the-art algorithms. The investigation of several essential components of the proposed algorithms sheds light on the following points. First, the consideration of both feasible and infeasible search space regions can greatly enhance the neighborhood search for CCP. Second, the best improvement strategy is able to outperform the first improvement strategy within the tabu search framework for CCP. Third, given an extended time limit, MA can further improve upon the performance of FITS which is greatly due to the cluster-based crossover that transfers pertinent properties from parents to offspring. The use of this crossover within MA was motivated by a large degree of similarity between high-quality CCP solutions. Finally, this work demonstrates the effectiveness of exploring both feasible and infeasible spaces for CCP - an idea that certainly deserves to be investigated on other highly constrained problems in the future.
## Acknowledgments

We are grateful to the reviewers for their valuable comments which helped us to improve the paper. We thank the authors of [7,24] for kindly sharing with us their source codes that enabled fair comparisons with the proposed algorithms. This work is partially supported by the National Natural Science Foundation Program of China [Grant No. 71401059, 71771099, 71810107003, 71620107002, 71531009] and the Huazhong University of Science and Technology (5001300001).

## References

[1] Aiex, R. M., Resende, M. G. C., & Ribeiro, C. C. (2007). Ttt plots: a perl program to create time-to-target plots. Optimization Letters, 1(4), 355-366.

[2] Bard, J. F., & Jarrah, A. I. (2009). Large-scale constrained clustering for rationalizing pickup and delivery operations. Transportation Research Part B: Methodological, 43(5), 542-561.

[3] Bartz-Beielstein, T., Chiarandini, M., Paquete, L., & Preuss, M. (2010). Experimental Methods for the Analysis of Optimization Algorithms. Springer Berlin Heidelberg.

[4] Benlic, U., & Hao, J. K. (2011). A multilevel memetic approach for improving graph k-partitions. IEEE Transactions on Evolutionary Computation, 15(5), 624-642.

[5] Benlic, U., & Hao, J. K. (2013). Hybrid Metaheuristics for the Graph Partitioning Problem. Hybrid Metaheuristics, 157-185.

[6] Brimberg, J., Mladenović, N., & Urošević, D. (2015). Solving the maximally diverse grouping problem by skewed general variable neighborhood search. Information Sciences, 295, 650-675.

[7] Brimberg, J., Mladenović, N., Todosijević, R., & Urošević, D. (2017). Solving the capacitated clustering problem with variable neighborhood search. Annals of Operations Research(2), 1-33.

[8] Chen, X., Ong, Y. S., Lim, M. H., & Tan, K. C. (2011). A multi-facet survey on memetic computation. IEEE Transactions on Evolutionary Computation, 15(5), 591-607.

[9] Chen Y.N., Hao J.K., Glover F. (2016). A hybrid metaheuristic approach for the capacitated arc routing problem, European Journal of Operational Research, 253(1): 25-39.

[10] Deng, Y., & Bard, J. F. (2011). A reactive GRASP with path relinking for capacitated clustering. Journal of Heuristics, 17(2), 119-152.
[11] Duarte, A., & Martí, R. (2007). Tabu search and grasp for the maximum diversity problem. European Journal of Operational Research, 178(1), 71-84.

[12] Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & Rousseau, L.M. (2016). A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times, European Journal of Operational Research, 249(1):55-66.

[13] Falkenauer, E. Genetic algorithms and grouping problems. New York: Wiley, 1998.

[14] Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.

[15] Galinier, P., & Hao, J.k. (1999). Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3(4): 379-397.

[16] Galinier, P., Boujbel, Z., & Fernandes, M. C. (2011). An efficient memetic algorithm for the graph partitioning problem. Annals of Operations Research, 191(1), 1-22.

[17] Gallego, M., & Duarte, A. (2013). Tabu search with strategic oscillation for the maximally diverse grouping problem. Journal of the Operational Research Society, 64(5), 724-734.

[18] Laguna, M. & Glover, F. (1997). Tabu Search. Springer.

[19] Hao, J. K. (2012). Memetic Algorithms in Discrete Optimization. In F. Neri, C. Cotta, P. Moscato (Eds.) Handbook of Memetic Algorithms. Studies in Computational Intelligence 379, Chapter 6, pages 73-94, 2012. Springer Berlin Heidelberg.

[20] Hertz, A., Laporte, G., & Mittaz, M. (2000). A tabu search heuristic for the capacitated arc routing problem. Operations Research, 48(1), 129-135.

[21] Higgins, A. J. (2001). A dynamic tabu search for large-scale generalised assignment problems. Computers & Operations Research, 28(10), 1039-1048.

[22] Johnes, J. (2015). Operational research in education. European Journal of Operational Research, 243(3), 683-696.

[23] Koskosidis, Y. A., & Powell, W. B. (1992). Clustering algorithms for consolidation of customer orders into vehicle shipments. Transportation Research Part B Methodological, 26(5), 365-379.

[24] Lai, X., & Hao, J. K. (2016). Iterated variable neighborhood search for the capacitated clustering problem. Engineering Applications of Artificial Intelligence, 56, 102-120.

[25] Lai, X., & Hao, J. K. (2016). Iterated maxima search for the maximally diverse grouping problem. European Journal of Operational Research, 254(3):780-800.

[26] Lapierre, S. D., Ruiz, A., & Soriano, P. (2006). Balancing assembly lines with tabu search. European Journal of Operational Research, 168(3), 826-837.
[27] López-Ibánez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Stützle, T. (2016). The irace package: iterated racing for automatic algorithm configuration. *Operations Research Perspectives*, 3, 43-58.

[28] Lü, Z., Glover, F., & Hao, J. K. (2010). A hybrid metaheuristic approach to solving the ubqp problem. *European Journal of Operational Research*, 207(3), 1254-1262.

[29] Martínez-Gavara, A., Campos, V., Gallego, M., Laguna, M., & Martí, R. (2015). Tabu search and GRASP for the capacitated clustering problem. *Computational Optimization and Applications*, 62(2), 589-607.

[30] Martínez-Gavara, A., Landa-Silva, D., Campos, V., & Martí, R. (2017). Randomized heuristics for the capacitated clustering problem. *Information Sciences*, 417.

[31] Morán-Mirabal, L. F., González-Velarde, J. L., Resende, M. G., & Silva, R. M. (2013). Randomized heuristics for handover minimization in mobility networks. *Journal of Heuristics*, 19(6), 845-880.

[32] Moscato, P., & Cotta, C. (2006). A Gentle Introduction to Memetic Algorithms. *Handbook of Metaheuristics*. Springer US.

[33] Mulvey, J. M., & Beck, M. P. (1984). Solving capacitated clustering problems. *European Journal of Operational Research*, 18(3), 339-348.

[34] Palubeckis, G., Ostreika, A., & Rubliauskas, D. (2015). Maximally diverse grouping: an iterated tabu search approach. *Journal of the Operational Research Society*, 66(4), 579-592.

[35] Paraskevopoulos, D. C., Laporte, G., Repoussis, P. P., & Tarantilis, C. D. (2017). Resource Constrained Routing and Scheduling: Review and Research Prospects. *European Journal of Operational Research*, 263(3):737-754.

[36] Porumbel, D. C., Hao, J. K., & Kuntz, P. (2010). An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. *Computers & Operations Research*, 37(10), 1822-1832.

[37] Rodriguez, F. J., Lozano, M., García-Martínez, C., & González-Barrera, J. D. (2013). An artificial bee colony algorithm for the maximally diverse grouping problem. *Information Sciences*, 230(5), 183-196.

[38] Weitz, R. R., & Lakshminarayanan, S. (1998). An empirical comparison of heuristic methods for creating maximally diverse groups. *Journal of the Operational Research Society*, 25(6), 473-482.

[39] Wu, Q., & Hao, J. K. (2013). A hybrid metaheuristic method for the maximum diversity problem. *European Journal of Operational Research*, 231(2), 452-464.
Appendix

The purpose of this appendix is to show detailed computational results and comparisons between our two proposed algorithms (FITS and MA) and the state-of-the-art algorithms on the complete CCP benchmark consisting of 183 instances (Tables 11-22). For each instance and approach, columns ‘*f*<sub>best</sub>’, ‘*f*<sub>avg</sub>’ and ‘*t*<sub>avg</sub>’ show respectively the best objective value, the average objective value and the average computing time in seconds required to reach the final solution (see Section 4.2 for the used experimental protocol). Column ‘*Dev*<sub>best</sub>/*Dev*<sub>avg</sub>’ indicates the percent deviation between the best or the average result and the best solutions obtained within each experiment. Row ‘#Best’ gives the number of cases when each algorithm outperforms the remaining approaches, while row ‘Average’ shows the average result for a given subset of instances. Finally, row ‘*p*-value’ indicates the outcome of the non-parametric Friedman tests on the results obtained with FITS and the reference algorithms. The best results are highlighted in bold.
<table><caption>Table 12. Comparison between FITS and six state-of-the-art algorithms on the first two sets of CCP instances (RanReal and DB).</caption><thead><tr><th rowspan="2">Name</th><th colspan="10">Devbest/Devavg(%)</th></tr><tr><th>GRASP</th><th>TS</th><th>GRASP+TS</th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th><th>GRASP</th><th>TS</th><th>t<sub>avg</sub></th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th></tr></thead><tbody><tr><td>Sparse82.01</td><td>0.00/0.00</td><td>0.45/1.67</td><td>0.00/0.01</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>32.67</td><td>5.82</td><td>25.73</td><td>0.32</td><td>30.83</td><td>31.25</td><td>12.51</td></tr><tr><td>Sparse82.02</td><td>0.00/0.12</td><td>0.20/1.90</td><td>0.00/0.06</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>41.34</td><td>4.71</td><td>32.60</td><td>1.32</td><td>25.10</td><td>22.08</td><td>20.30</td></tr><tr><td>Sparse82.03</td><td>0.10/0.34</td><td>0.00/0.97</td><td>0.00/0.15</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>27.53</td><td>5.30</td><td>40.18</td><td>0.18</td><td>24.29</td><td>30.60</td><td>4.28</td></tr><tr><td>Sparse82.04</td><td>0.14/0.35</td><td>0.11/1.23</td><td>0.00/0.34</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>36.28</td><td>11.28</td><td>30.47</td><td>6.89</td><td>25.90</td><td>29.40</td><td>26.75</td></tr><tr><td>Sparse82.05</td><td>0.00/0.00</td><td>0.03/1.88</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>16.31</td><td>6.81</td><td>8.53</td><td>0.11</td><td>42.73</td><td>25.40</td><td>3.95</td></tr><tr><td>Sparse82.06</td><td>0.00/0.47</td><td>0.00/1.15</td><td>0.00/0.01</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>45.16</td><td>5.36</td><td>41.17</td><td>0.14</td><td>34.59</td><td>28.80</td><td>3.57</td></tr><tr><td>Sparse82.07</td><td>0.00/0.04</td><td>0.27/2.10</td><td>0.00/0.04</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>32.73</td><td>3.66</td><td>35.85</td><td>0.64</td><td>31.43</td><td>35.06</td><td>4.27</td></tr><tr><td>Sparse82.08</td><td>0.00/0.00</td><td>0.09/2.59</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.42</td><td>15.25</td><td>0.38</td><td>0.04</td><td>31.41</td><td>26.69</td><td>10.18</td></tr><tr><td>Sparse82.09</td><td>0.00/0.05</td><td>0.00/0.82</td><td>0.06/0.06</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>13.57</td><td>5.79</td><td>16.82</td><td>0.99</td><td>25.39</td><td>31.97</td><td>4.53</td></tr><tr><td>Sparse82.10</td><td>0.00/0.03</td><td>0.00/1.86</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>35.45</td><td>12.64</td><td>41.41</td><td>1.00</td><td>13.99</td><td>29.50</td><td>1.50</td></tr><tr><td>RanReal240.01</td><td>7.53/8.75</td><td>0.61/1.38</td><td>1.07/1.52</td><td>0.07/0.19</td><td>0.18/0.35</td><td>0.00/0.18</td><td>0.02/0.08</td><td>116.19</td><td>24.61</td><td>198.34</td><td>155.57</td><td>155.92</td><td>127.16</td><td>149.09</td></tr><tr><td>RanReal240.02</td><td>14.29/15.12</td><td>9.59/10.29</td><td>9.78/10.44</td><td>8.73/8.89</td><td>0.00/9.15</td><td>8.79/8.85</td><td>8.79/8.85</td><td>95.06</td><td>31.06</td><td>152.77</td><td>184.44</td><td>159.56</td><td>158.20</td><td>150.75</td></tr><tr><td>RanReal240.03</td><td>4.92/7.07</td><td>1.40/2.64</td><td>1.38/2.05</td><td>0.05/0.18</td><td>0.25/0.58</td><td>0.00/0.27</td><td>0.01/0.09</td><td>142.89</td><td>8.67</td><td>127.14</td><td>186.06</td><td>164.11</td><td>139.26</td><td>169.95</td></tr><tr><td>RanReal240.04</td><td>6.10/7.76</td><td>1.27/2.67</td><td>1.16/1.96</td><td>0.10/0.25</td><td>0.21/0.52</td><td>0.04/0.09</td><td>0.01/0.09</td><td>102.72</td><td>22.69</td><td>147.86</td><td>159.70</td><td>175.00</td><td>137.88</td><td>115.58</td></tr><tr><td>RanReal240.05</td><td>5.37/6.59</td><td>1.13/1.91</td><td>1.12/2.12</td><td>0.01/0.19</td><td>0.33/0.61</td><td>0.06/0.31</td><td>0.00/0.12</td><td>112.52</td><td>12.77</td><td>133.26</td><td>155.02</td><td>179.73</td><td>136.48</td><td>132.33</td></tr><tr><td>RanReal240.06</td><td>5.49/6.98</td><td>1.01/1.65</td><td>0.90/1.60</td><td>0.02/0.18</td><td>0.17/0.41</td><td>0.08/0.27</td><td>0.00/0.12</td><td>113.64</td><td>34.23</td><td>146.87</td><td>174.51</td><td>187.59</td><td>126.61</td><td>155.99</td></tr><tr><td>RanReal240.07</td><td>4.80/5.57</td><td>0.68/1.36</td><td>0.79/1.44</td><td>0.09/0.47</td><td>0.02/0.23</td><td>0.00/0.13</td><td>0.00/0.13</td><td>98.82</td><td>48.81</td><td>171.68</td><td>160.67</td><td>195.33</td><td>144.33</td><td>144.96</td></tr><tr><td>RanReal240.08</td><td>6.66/8.10</td><td>0.69/1.68</td><td>1.22/1.96</td><td>0.00/0.20</td><td>0.24/0.54</td><td>0.11/0.35</td><td>0.00/0.14</td><td>114.33</td><td>20.45</td><td>137.72</td><td>145.94</td><td>193.88</td><td>122.79</td><td>124.22</td></tr><tr><td>RanReal240.09</td><td>5.16/6.44</td><td>0.49/1.08</td><td>0.51/1.17</td><td>0.01/0.20</td><td>0.22/0.42</td><td>0.07/0.23</td><td>0.00/0.10</td><td>145.30</td><td>43.70</td><td>168.65</td><td>194.36</td><td>171.09</td><td>136.24</td><td>141.69</td></tr><tr><td>RanReal240.10</td><td>6.84/7.44</td><td>1.39/2.44</td><td>1.55/2.25</td><td>0.05/0.21</td><td>0.33/0.58</td><td>0.02/0.23</td><td>0.00/0.09</td><td>112.01</td><td>12.19</td><td>129.47</td><td>183.49</td><td>145.39</td><td>134.20</td><td>133.20</td></tr><tr><td>RanReal240.11</td><td>6.18/6.80</td><td>0.65/1.53</td><td>1.05/1.61</td><td>0.04/0.17</td><td>0.16/0.40</td><td>0.04/0.18</td><td>0.00/0.08</td><td>122.37</td><td>65.47</td><td>161.82</td><td>157.98</td><td>155.12</td><td>136.25</td><td>129.91</td></tr><tr><td>RanReal240.12</td><td>5.33/6.51</td><td>0.53/1.18</td><td>0.76/1.18</td><td>0.04/0.18</td><td>0.15/0.48</td><td>0.00/0.25</td><td>0.00/0.16</td><td>147.93</td><td>96.77</td><td>163.87</td><td>186.71</td><td>157.43</td><td>123.13</td><td>132.03</td></tr><tr><td>RanReal240.13</td><td>7.00/8.22</td><td>0.98/1.52</td><td>0.81/1.45</td><td>0.00/0.15</td><td>0.18/0.48</td><td>0.10/0.31</td><td>0.00/0.10</td><td>107.97</td><td>30.38</td><td>150.83</td><td>173.46</td><td>171.44</td><td>127.25</td><td>131.34</td></tr><tr><td>RanReal240.14</td><td>8.41/10.12</td><td>0.73/1.40</td><td>0.90/1.54</td><td>0.09/0.15</td><td>0.09/0.36</td><td>0.06/0.23</td><td>0.00/0.14</td><td>104.77</td><td>12.33</td><td>131.31</td><td>147.56</td><td>164.87</td><td>112.27</td><td>135.87</td></tr><tr><td>RanReal240.15</td><td>5.98/7.42</td><td>0.98/2.13</td><td>1.29/2.02</td><td>0.05/0.22</td><td>0.36/0.67</td><td>0.17/0.41</td><td>0.00/0.17</td><td>147.90</td><td>11.13</td><td>135.10</td><td>167.88</td><td>188.75</td><td>154.19</td><td>131.83</td></tr><tr><td>RanReal240.16</td><td>5.62/7.13</td><td>1.28/1.93</td><td>0.88/1.60</td><td>0.00/0.20</td><td>0.13/0.39</td><td>0.07/0.21</td><td>0.01/0.18</td><td>134.19</td><td>20.82</td><td>153.67</td><td>165.22</td><td>181.82</td><td>130.93</td><td>89.11</td></tr><tr><td>RanReal240.17</td><td>4.09/4.83</td><td>0.79/1.80</td><td>0.60/1.77</td><td>0.18/0.31</td><td>0.37/0.59</td><td>0.06/0.31</td><td>0.00/0.16</td><td>97.91</td><td>31.38</td><td>146.50</td><td>171.75</td><td>179.25</td><td>149.01</td><td>171.03</td></tr><tr><td>RanReal240.18</td><td>7.31/8.16</td><td>0.77/2.02</td><td>1.14/2.02</td><td>0.09/0.20</td><td>0.09/0.51</td><td>0.04/0.20</td><td>0.00/0.12</td><td>134.95</td><td>20.60</td><td>133.33</td><td>154.60</td><td>179.59</td><td>140.21</td><td>98.08</td></tr><tr><td>RanReal240.19</td><td>5.44/6.51</td><td>1.24/2.31</td><td>1.48/2.06</td><td>0.01/0.16</td><td>0.20/0.56</td><td>0.11/0.30</td><td>0.00/0.09</td><td>118.97</td><td>10.95</td><td>192.71</td><td>173.65</td><td>179.52</td><td>169.52</td><td>152.83</td></tr><tr><td>RanReal240.20</td><td>4.93/5.85</td><td>0.99/1.62</td><td>0.89/1.69</td><td>0.02/0.20</td><td>0.15/0.39</td><td>0.00/0.18</td><td>0.01/0.11</td><td>139.71</td><td>33.98</td><td>151.07</td><td>188.64</td><td>175.52</td><td>112.33</td><td>115.38</td></tr><tr><td>RanReal480.01</td><td>11.83/13.04</td><td>1.91/3.00</td><td>1.62/2.69</td><td>0.25/0.35</td><td>0.45/0.61</td><td>0.00/0.26</td><td>0.04/0.24</td><td>269.94</td><td>91.12</td><td>333.56</td><td>391.12</td><td>419.98</td><td>301.25</td><td>340.60</td></tr><tr><td>RanReal480.02</td><td>9.23/9.88</td><td>2.20/3.24</td><td>1.65/2.69</td><td>0.24/0.43</td><td>0.50/0.73</td><td>0.05/0.20</td><td>0.00/0.30</td><td>264.17</td><td>78.83</td><td>289.46</td><td>403.38</td><td>414.24</td><td>293.36</td><td>355.59</td></tr><tr><td>RanReal480.03</td><td>9.72/10.24</td><td>2.23/3.36</td><td>2.14/3.03</td><td>0.25/0.43</td><td>0.49/0.77</td><td>0.00/0.18</td><td>0.05/0.30</td><td>202.03</td><td>53.59</td><td>290.70</td><td>420.24</td><td>427.12</td><td>331.81</td><td>352.06</td></tr><tr><td>RanReal480.04</td><td>9.54/10.28</td><td>1.86/3.45</td><td>2.33/3.21</td><td>0.17/0.48</td><td>0.36/0.67</td><td>0.00/0.21</td><td>0.04/0.20</td><td>221.32</td><td>93.30</td><td>302.04</td><td>383.19</td><td>428.09</td><td>332.13</td><td>399.51</td></tr><tr><td>RanReal480.05</td><td>10.27/11.39</td><td>2.69/3.51</td><td>2.13/3.04</td><td>0.09/0.35</td><td>0.47/0.74</td><td>0.10/0.24</td><td>0.00/0.25</td><td>235.49</td><td>57.96</td><td>288.63</td><td>417.55</td><td>448.15</td><td>325.05</td><td>335.84</td></tr><tr><td>RanReal480.06</td><td>10.26/10.97</td><td>2.11/3.03</td><td>2.02/2.79</td><td>0.24/0.45</td><td>0.41/0.61</td><td>0.00/0.22</td><td>0.17/0.35</td><td>222.09</td><td>103.33</td><td>310.30</td><td>393.37</td><td>428.17</td><td>300.77</td><td>390.06</td></tr><tr><td>RanReal480.07</td><td>11.28/12.49</td><td>1.89/2.71</td><td>2.18/2.60</td><td>0.08/0.31</td><td>0.24/0.63</td><td>0.00/0.18</td><td>0.06/0.21</td><td>282.40</td><td>101.60</td><td>312.15</td><td>395.01</td><td>423.31</td><td>342.07</td><td>390.23</td></tr><tr><td>RanReal480.08</td><td>9.56/10.42</td><td>2.16/3.20</td><td>2.19/2.95</td><td>0.22/0.40</td><td>0.35/0.68</td><td>0.00/0.21</td><td>0.14/0.28</td><td>239.63</td><td>88.35</td><td>328.43</td><td>388.45</td><td>398.32</td><td>356.39</td><td>380.64</td></tr><tr><td>RanReal480.09</td><td>11.59/13.53</td><td>1.87/3.25</td><td>2.07/2.86</td><td>0.29/0.43</td><td>0.37/0.69</td><td>0.00/0.26</td><td>0.07/0.29</td><td>237.49</td><td>78.39</td><td>315.08</td><td>376.21</td><td>421.61</td><td>350.35</td><td>383.67</td></tr><tr><td>RanReal480.10</td><td>10.41/11.38</td><td>2.34/3.30</td><td>2.16/3.01</td><td>0.18/0.35</td><td>0.54/0.77</td><td>0.12/0.27</td><td>0.00/0.42</td><td>241.70</td><td>83.45</td><td>290.39</td><td>383.71</td><td>428.06</td><td>300.43</td><td>328.85</td></tr><tr><td>RanReal480.11</td><td>9.62/10.78</td><td>1.37/3.00</td><td>1.84/2.61</td><td>0.17/0.41</td><td>0.33/0.59</td><td>0.00/0.17</td><td>0.07/0.29</td><td>227.89</td><td>94.12</td><td>312.81</td><td>383.91</td><td>421.15</td><td>320.08</td><td>383.65</td></tr><tr><td>RanReal480.12</td><td>10.04/10.63</td><td>1.79/2.61</td><td>1.87/2.72</td><td>0.15/0.43</td><td>0.46/0.72</td><td>0.00/0.19</td><td>0.06/0.29</td><td>271.59</td><td>88.29</td><td>309.44</td><td>397.43</td><td>409.11</td><td>270.86</td><td>347.32</td></tr><tr><td>RanReal480.13</td><td>8.87/9.86</td><td>1.37/2.85</td><td>2.02/2.70</td><td>0.18/0.33</td><td>0.30/0.55</td><td>0.00/0.18</td><td>0.05/0.27</td><td>208.64</td><td>138.35</td><td>317.13</td><td>404.23</td><td>390.76</td><td>330.84</td><td>330.84</td></tr><tr><td>RanReal480.14</td><td>12.10/13.49</td><td>2.00/3.39</td><td>2.00/3.33</td><td>0.20/0.33</td><td>0.28/0.58</td><td>0.00/0.18</td><td>0.02/0.23</td><td>276.22</td><td>75.53</td><td>311.36</td><td>405.04</td><td>419.87</td><td>319.14</td><td>352.07</td></tr><tr><td>RanReal480.15</td><td>9.99/10.91</td><td>1.51/2.68</td><td>1.97/2.82</td><td>0.18/0.42</td><td>0.38/0.60</td><td>0.00/0.17</td><td>0.07/0.30</td><td>235.52</td><td>118.86</td><td>319.34</td><td>384.96</td><td>418.77</td><td>313.91</td><td>387.02</td></tr><tr><td>RanReal480.16</td><td>11.34/12.08</td><td>1.76/2.98</td><td>1.60/2.51</td><td>0.12/0.29</td><td>0.15/0.51</td><td>0.00/0.14</td><td>0.06/0.26</td><td>227.75</td><td>104.65</td><td>322.10</td><td>345.11</td><td>419.82</td><td>301.16</td><td>392.78</td></tr><tr><td>RanReal480.17</td><td>10.32/11.43</td><td>1.46/2.47</td><td>1.65/2.62</td><td>0.14/0.33</td><td>0.29/0.59</td><td>0.00/0.18</td><td>0.06/0.22</td><td>229.01</td><td>109.71</td><td>287.42</td><td>386.16</td><td>411.52</td><td>320.59</td><td>360.93</td></tr><tr><td>RanReal480.18</td><td>8.98/9.73</td><td>1.43/2.98</td><td>1.66/2.96</td><td>0.06/0.25</td><td>0.23/0.55</td><td>0.02/0.18</td><td>0.00/0.21</td><td>227.34</td><td>106.08</td><td>292.13</td><td>368.20</td><td>431.30</td><td>278.26</td><td>320.60</td></tr><tr><td>RanReal480.19</td><td>9.20/10.10</td><td>1.92/2.75</td><td>1.81/2.55</td><td>0.07/0.23</td><td>0.18/0.55</td><td>0.00/0.17</td><td>0.06/0.26</td><td>249.78</td><td>75.37</td><td>303.77</td><td>400.78</td><td>435.58</td><td>306.80</td><td>380.69</td></tr><tr><td>RanReal480.20</td><td>11.03/11.90</td><td>2.05/2.70</td><td>1.46/2.47</td><td>0.05/0.34</td><td>0.43/0.63</td><td>0.00/0.19</td><td>0.07/0.25</td><td>201.47</td><td>124.30</td><td>344.80</td><td>385.30</td><td>420.08</td><td>339.09</td><td>353.52</td></tr><tr><td>Average</td><td>6.66/7.56</td><td>1.33/2.42</td><td>1.35/2.00</td><td>0.26/0.40</td><td>0.22/0.63</td><td>0.20/0.36</td><td>0.19/0.33</td><td>149.25</td><td>50.68</td><td>187.26</td><td>224.24</td><td>243.04</td><td>187.33</td><td>201.35</td></tr></tbody></table>
<table><caption>Table 13. Comparison of FITS with six state-of-the-art algorithms on the large CCP instances (RanReal960 and MDG).</caption><thead><tr><th rowspan="2">Name</th><th colspan="4">f<sub>best</sub></th><th colspan="4">f<sub>avg</sub></th><th rowspan="2">FITS</th></tr><tr><th>GRASP</th><th>TS</th><th>GRASP+TS</th><th>IVS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th><th>GRASP</th><th>TS</th><th>GRASP+TS</th><th>IVS</th><th>GVNS</th><th>SGVNS</th></tr></thead><tbody><tr><td>RanReal960_01.30</td><td>1160656.62</td><td>1293137.12</td><td>1295744.06</td><td>1331323.28</td><td>1331996.73</td><td>1337853.23</td><td>1333878.00</td><td>1151895.17</td><td>1283288.50</td><td>1290241.93</td><td>1329095.10</td><td>1328415.40</td><td>1335679.54</td><td>1332712.78</td></tr><tr><td>RanReal960_02.30</td><td>1216485.40</td><td>1389456.81</td><td>1392709.68</td><td>12427037.60</td><td>1343307.61</td><td>1434352.49</td><td>1338787.00</td><td>1202250.66</td><td>1384368.44</td><td>1388067.85</td><td>1242930.72</td><td>1242960.00</td><td>1340808.90</td><td>1433886.30</td></tr><tr><td>RanReal960_03.30</td><td>1189286.33</td><td>1351873.72</td><td>1351870.43</td><td>13900870.24</td><td>13426870.84</td><td>1390363.98</td><td>1398486.80</td><td>1182522.35</td><td>1344235.06</td><td>1351792.20</td><td>1387508.88</td><td>1387653.72</td><td>1394012.26</td><td>1390924.21</td></tr><tr><td>RanReal960_04.30</td><td>1219509.95</td><td>1370623.88</td><td>1371234.23</td><td>1407607.65</td><td>1406916.02</td><td>1413478.82</td><td>1414344.67</td><td>1212573.34</td><td>1362351.05</td><td>1368276.84</td><td>1405972.04</td><td>1403198.73</td><td>1410438.07</td><td>1412460.01</td></tr><tr><td>RanReal960_05.30</td><td>1188052.95</td><td>1325522.71</td><td>1329439.01</td><td>1363405.35</td><td>1362240.30</td><td>1370560.76</td><td>1360579.56</td><td>1182095.82</td><td>1319156.72</td><td>1324437.32</td><td>1360883.59</td><td>1359314.24</td><td>1367959.84</td><td>1365612.74</td></tr><tr><td>RanReal960_07.30</td><td>1137446.74</td><td>1300578.66</td><td>1298460.40</td><td>1406916.02</td><td>1413478.82</td><td>1413478.82</td><td>1176910.55</td><td>1369015.75</td><td>1341056.52</td><td>1340567.83</td><td>1360503.60</td><td>1340670.74</td><td>1341715.60</td><td>1412750.21</td></tr><tr><td>RanReal960_08.30</td><td>1257726.73</td><td>1425314.30</td><td>1429319.26</td><td>1426280.45</td><td>1460407.11</td><td>1466738.95</td><td>1463737.39</td><td>1129944.15</td><td>129454.26</td><td>129502.06</td><td>1329503.04</td><td>1329170.21</td><td>13337029.82</td><td>1334263.93</td></tr><tr><td>RanReal960_09.30</td><td>1208989.95</td><td>1357670.23</td><td>1358430.61</td><td>1378445.26</td><td>1382060.22</td><td>1382338.77</td><td>1381742.32</td><td>1166762.04</td><td>1338126.23</td><td>1339495.54</td><td>1374311.23</td><td>1373790.24</td><td>1381870.76</td><td>1387782.67</td></tr><tr><td>RanReal960_10.30</td><td>1177285.83</td><td>1343535.01</td><td>1343597.60</td><td>1377646.33</td><td>1377009.66</td><td>1384154.95</td><td>1379905.83</td><td>86664.65</td><td>993064.32</td><td>998694.36</td><td>1031462.28</td><td>1030512.99</td><td>1038487.54</td><td>1034626.82</td></tr><tr><td>RanReal960_10.40</td><td>891572.56</td><td>1004227.73</td><td>1004270.26</td><td>1034548.05</td><td>1032872.42</td><td>1041148.42</td><td>103564.26</td><td>86664.65</td><td>993064.32</td><td>998694.36</td><td>1031462.28</td><td>1030512.99</td><td>1038487.54</td><td>1034626.82</td></tr><tr><td>RanReal960_02.40</td><td>935401.94</td><td>1058305.47</td><td>1058232.96</td><td>1108588.66</td><td>1109086.02</td><td>11157589.54</td><td>11015758.71</td><td>928159.94</td><td>1077230.13</td><td>1080504.37</td><td>106617.47</td><td>106469.64</td><td>1113937.71</td><td>1110074.36</td></tr><tr><td>RanReal960_03.40</td><td>921042.44</td><td>1044295.09</td><td>1052879.25</td><td>1052879.25</td><td>1051509.08</td><td>1080281.13</td><td>1086488.77</td><td>915374.21</td><td>1038465.67</td><td>1048423.28</td><td>1079553.82</td><td>1077244.61</td><td>1085060.19</td><td>1082948.77</td></tr><tr><td>RanReal960_04.40</td><td>937109.10</td><td>1059684.54</td><td>1070116.28</td><td>1096347.39</td><td>1096438.26</td><td>1100866.71</td><td>1103897.12</td><td>933821.48</td><td>1056026.26</td><td>1061981.40</td><td>1092787.54</td><td>1091633.05</td><td>1098759.10</td><td>1101073.37</td></tr><tr><td>RanReal960_05.40</td><td>906482.91</td><td>1029269.47</td><td>1027437.77</td><td>1056103.80</td><td>1057478.73</td><td>1063682.56</td><td>1059158.09</td><td>903666.87</td><td>1022127.35</td><td>1022735.81</td><td>105445.69</td><td>1054478.20</td><td>1058748.46</td><td>1058748.46</td></tr><tr><td>RanReal960_06.40</td><td>897340.52</td><td>1069823.35</td><td>1074709.94</td><td>1098958.36</td><td>1099861.44</td><td>1104590.22</td><td>1100368.74</td><td>895656.35</td><td>1064068.17</td><td>1069231.66</td><td>1075721.54</td><td>1093932.85</td><td>1102651.28</td><td>1100064.66</td></tr><tr><td>RanReal960_07.40</td><td>867071.23</td><td>1004440.73</td><td>1005791.58</td><td>1034299.55</td><td>1035241.97</td><td>1041064.58</td><td>1043376.95</td><td>955984.19</td><td>1096241.59</td><td>1106224.45</td><td>1136002.24</td><td>1133556.70</td><td>1141717.41</td><td>1138054.46</td></tr><tr><td>RanReal960_08.40</td><td>966280.23</td><td>1102339.42</td><td>1110622.81</td><td>1137464.75</td><td>1136567.63</td><td>1142282.86</td><td>1139386.05</td><td>955984.19</td><td>1096241.59</td><td>1106224.45</td><td>1136002.24</td><td>1133556.70</td><td>1141717.41</td><td>1138054.46</td></tr><tr><td>RanReal960_09.40</td><td>924938.50</td><td>1036368.74</td><td>1042262.50</td><td>1068284.24</td><td>1068299.92</td><td>1076229.18</td><td>1072116.14</td><td>921990.58</td><td>1028766.23</td><td>1034766.78</td><td>1066496.30</td><td>1066427.94</td><td>1071426.07</td><td>1071426.07</td></tr><tr><td>RanReal960_10.40</td><td>904198.86</td><td>1025597.43</td><td>1049773.83</td><td>1069556.59</td><td>1069895.94</td><td>1077400.98</td><td>1072919.65</td><td>899148.57</td><td>1031513.70</td><td>1040754.01</td><td>1067889.46</td><td>1067548.97</td><td>1074400.36</td><td>1071480.21</td></tr><tr><td>RanReal960_01.60</td><td>619038.29</td><td>700687.54</td><td>701813.93</td><td>726465.37</td><td>725912.84</td><td>732096.63</td><td>727690.58</td><td>612713.55</td><td>695227.62</td><td>697743.35</td><td>724244.42</td><td>723156.84</td><td>730601.10</td><td>727222.73</td></tr><tr><td>RanReal960_02.60</td><td>647084.93</td><td>748934.65</td><td>746043.72</td><td>770060.90</td><td>770477.46</td><td>776289.95</td><td>773903.97</td><td>641266.62</td><td>763850.06</td><td>742288.71</td><td>768062.71</td><td>775060.74</td><td>772574.29</td><td>772574.29</td></tr><tr><td>RanReal960_03.60</td><td>632413.61</td><td>724697.78</td><td>726919.69</td><td>753090.36</td><td>753090.36</td><td>760248.25</td><td>756677.97</td><td>628405.90</td><td>720409.22</td><td>723789.32</td><td>761419.90</td><td>760898.37</td><td>758432.10</td><td>754244.64</td></tr><tr><td>RanReal960_04.60</td><td>645023.75</td><td>735689.79</td><td>739337.91</td><td>762952.42</td><td>763838.97</td><td>769112.25</td><td>765253.27</td><td>642799.40</td><td>730470.51</td><td>734819.23</td><td>761387.83</td><td>760835.94</td><td>767780.08</td><td>764696.30</td></tr><tr><td>RanReal960_05.60</td><td>630215.36</td><td>716742.73</td><td>719501.92</td><td>741248.79</td><td>741932.85</td><td>748581.43</td><td>743715.56</td><td>624979.06</td><td>709477.81</td><td>714588.65</td><td>739443.77</td><td>738830.28</td><td>746014.20</td><td>743165.17</td></tr><tr><td>RanReal960_06.60</td><td>6282892.55</td><td>734541.49</td><td>738738.50</td><td>761947.64</td><td>762286.50</td><td>767679.61</td><td>763209.61</td><td>618513.34</td><td>727566.01</td><td>732914.86</td><td>760389.56</td><td>759084.94</td><td>765628.88</td><td>761957.51</td></tr><tr><td>RanReal960_07.60</td><td>600734.82</td><td>700703.94</td><td>701940.30</td><td>723439.86</td><td>723736.02</td><td>728827.33</td><td>725993.23</td><td>597456.58</td><td>693719.70</td><td>697375.56</td><td>721167.69</td><td>720360.15</td><td>727421.19</td><td>725733.17</td></tr><tr><td>RanReal960_08.60</td><td>664742.63</td><td>762712.02</td><td>763064.60</td><td>789552.19</td><td>787775.07</td><td>794363.93</td><td>791394.42</td><td>658736.52</td><td>754557.15</td><td>757767.15</td><td>768334.58</td><td>785553.46</td><td>792538.90</td><td>790285.98</td></tr><tr><td>RanReal960_09.60</td><td>638160.86</td><td>723165.78</td><td>747516.78</td><td>761780.45</td><td>770458.18</td><td>7753943.93</td><td>775193.83</td><td>634884.33</td><td>715058.77</td><td>745313.38</td><td>744341.19</td><td>745187.91</td><td>749190.83</td><td>749190.83</td></tr><tr><td>RanReal960_10.60</td><td>618919.01</td><td>719787.60</td><td>724270.46</td><td>748812.21</td><td>747565.74</td><td>754666.01</td><td>749883.45</td><td>616548.20</td><td>715319.84</td><td>720345.30</td><td>746701.78</td><td>745004.51</td><td>752583.88</td><td>748985.05</td></tr><tr><td>MDG-a.22</td><td>315160.00</td><td>362695.00</td><td>371410.22</td><td>379241.00</td><td>388464.77</td><td>389269.00</td><td>383164.00</td><td>312644.80</td><td>360104.20</td><td>373209.70</td><td>376249.80</td><td>387189.20</td><td>389201.85</td><td>382387.05</td></tr><tr><td>MDG-a.23</td><td>317268.00</td><td>328093.00</td><td>371102.54</td><td>380650.00</td><td>388467.40</td><td>386350.00</td><td>380630.00</td><td>315499.40</td><td>325687.15</td><td>388684.70</td><td>377418.75</td><td>384018.35</td><td>380507.50</td><td>380507.50</td></tr><tr><td>MDG-a.24</td><td>312916.00</td><td>332128.00</td><td>372676.60</td><td>378258.00</td><td>387095.00</td><td>388423.00</td><td>387081.00</td><td>315288.70</td><td>359117.55</td><td>364125.35</td><td>374941.20</td><td>385489.20</td><td>387019.40</td><td>379334.85</td></tr><tr><td>MDG-a.25</td><td>320905.00</td><td>370090.00</td><td>382627.00</td><td>389242.00</td><td>387121.00</td><td>398108.00</td><td>387183.00</td><td>310704.15</td><td>326971.20</td><td>374075.45</td><td>384685.70</td><td>395749.55</td><td>397471.50</td><td>386346.05</td></tr><tr><td>MDG-a.26</td><td>320433.00</td><td>374776.00</td><td>386554.00</td><td>392407.00</td><td>396756.00</td><td>402135.00</td><td>393222.00</td><td>310036.20</td><td>356208.50</td><td>361418.90</td><td>372663.75</td><td>381301.50</td><td>392174.20</td><td>392916.10</td></tr><tr><td>MDG-a.27</td><td>312370.00</td><td>324348.00</td><td>356856.00</td><td>375556.00</td><td>380243.00</td><td>381896.00</td><td>377617.00</td><td>313527.20</td><td>328473.25</td><td>368721.65</td><td>375546.50</td><td>385207.20</td><td>387004.55</td><td>379732.95</td></tr><tr><td>MDG-a.28</td><td>314843.00</td><td>330349.00</td><td>372681.00</td><td>378486.00</td><td>386018.00</td><td>387594.00</td><td>380748.00</td><td>310036.20</td><td>356208.50</td><td>361418.90</td><td>372663.75</td><td>381301.50</td><td>392174.20</td><td>392174.20</td></tr><tr><td>MDG-a.29</td><td>311435.00</td><td>357683.00</td><td>363780.00</td><td>386154.00</td><td>387267.00</td><td>386030.00</td><td>386030.00</td><td>310036.20</td><td>356208.50</td><td>361418.90</td><td>372663.75</td><td>381301.50</td><td>392174.20</td><td>392174.20</td></tr><tr><td>MDG-a.30</td><td>320558.00</td><td>343222.00</td><td>381167.00</td><td>389615.00</td><td>394817.00</td><td>396678.00</td><td>389452.00</td><td>311684.20</td><td>328719.90</td><td>367440.60</td><td>374627.70</td><td>384018.25</td><td>385749.40</td><td>378922.75</td></tr><tr><td>MDG-a.31</td><td>313035.00</td><td>332135.00</td><td>372007.00</td><td>384718.00</td><td>384718.00</td><td>386587.00</td><td>379407.00</td><td>311684.20</td><td>328719.90</td><td>367440.60</td><td>374627.70</td><td>384018.25</td><td>385749.40</td><td>378922.75</td></tr><tr><td>MDG-a.32</td><td>318574.00</td><td>345851.00</td><td>372583.00</td><td>382405.00</td><td>383658.50</td><td>391383.00</td><td>393038.00</td><td>317281.50</td><td>336588.50</td><td>379780.40</td><td>391004.60</td><td>391004.60</td><td>392574.30</td><td>382737.35</td></tr><tr><td>MDG-a.33</td><td>315338.00</td><td>357377.00</td><td>368585.00</td><td>377659.00</td><td>382576.00</td><td>384291.00</td><td>379047.00</td><td>313647.90</td><td>356012.45</td><td>366607.00</td><td>373096.60</td><td>381876.80</td><td>383273.45</td><td>376641.80</td></tr><tr><td>MDG-a.34</td><td>318048.00</td><td>344939.00</td><td>372511.00</td><td>384412.00</td><td>393135.00</td><td>394676.00</td><td>386544.00</td><td>316882.65</td><td>336415.90</td><td>370375.60</td><td>381472.65</td><td>392409.55</td><td>394176.80</td><td>385459.25</td></tr><tr><td>MDG-a.35</td><td>319670.00</td><td>334545.20</td><td>379479.00</td><td>385251.00</td><td>393384.00</td><td>394687.00</td><td>386347.00</td><td>318614.15</td><td>331542.20</td><td>378821.80</td><td>383302.15</td><td>392174.20</td><td>401216.85</td><td>394103.05</td></tr><tr><td>MDG-a.36</td><td>323168.00</td><td>344521.00</td><td>385266.00</td><td>394867.00</td><td>400271.00</td><td>402087.00</td><td>386347.00</td><td>322207.50</td><td>340168.80</td><td>374170.24</td><td>388332.30</td><td>390014.00</td><td>394530.26</td><td>394530.26</td></tr><tr><td>MDG-a.37</td><td>315054.00</td><td>344145.00</td><td>369934.00</td><td>384811.00</td><td>387006.00</td><td>388411.00</td><td>386195.00</td><td>313427.95</td><td>339023.50</td><td>363213.40</td><td>380906.40</td><td>386276.45</td><td>387875.60</td><td>385797.30</td></tr><tr><td>MDG-a.38</td><td>324112.00</td><td>367162.00</td><td>380306.00</td><td>387472.00</td><td>384264.00</td><td>395865.00</td><td>388712.00</td><td>319654.20</td><td>361682.75</td><td>376996.50</td><td>384752.55</td><td>393879.15</td><td>395287.90</td><td>387803.15</td></tr><tr><td>MDG-a.39</td><td>317407.00</td><td>364448.00</td><td>372190.00</td><td>381738.00</td><td>390068.00</td><td>391450.00</td><td>389575.00</td><td>315434.25</td><td>330268.60</td><td>368502.90</td><td>378840.90</td><td>389174.50</td><td>383076.10</td><td>383076.10</td></tr><tr><td>MDG-a.40</td><td>324559.00</td><td>348432.00</td><td>390438.00</td><td>392751.00</td><td>403662.00</td><td>405184.00</td><td>396321.00</td><td>322889.20</td><td>344485.80</td><td>389367.10</td><td>391517.70</td><td>403108.90</td><td>405008.90</td><td>395505.80</td></tr></tbody><tfoot><tr><td>#Best</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>46</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>46</td><td>4</td></tr><tr><td>p-value</td><td>1.54e-12</td><td>1.54e-12</td><td>1.54e-12</td><td>1.54e-11</td><td>0.09</td><td>2.86e-9</td><td>1.54e-12</td><td>1.54e-12</td><td>1.54e-12</td><td>1.54e-12</td><td>0.16</td><td>2.86e-9</td><td>4</td></tr></tfoot></table>
<table><caption>Table 14. Comparison between FITS and the six state-of-the-art algorithms on the large CCP instances (RanReal960 and MDG).</caption><thead><tr><th rowspan="2">Name</th><th colspan="10">Devbest/Devavg(%)</th></tr><tr><th>GRASP</th><th>TS</th><th>GRASP+TS</th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th><th>GRASP</th><th>TS</th><th>GRASP+TS</th><th>t<sub>avg</sub></th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th></tr></thead><tbody><tr><td>RanReal960_01_30</td><td>13.24/13.90</td><td>3.34/4.08</td><td>3.15/3.56</td><td>0.49/0.65</td><td>0.44/0.71</td><td>0.30/0.38</td><td>643.28</td><td>659.97</td><td>746.31</td><td>918.26</td><td>811.54</td><td>856.21</td><td>915.53</td><td></td><td></td></tr><tr><td>RanReal960_02_30</td><td>15.20/16.19</td><td>3.14/3.50</td><td>2.92/3.24</td><td>0.53/0.74</td><td>0.52/0.81</td><td>0.10/0.52</td><td>0.00/0.04</td><td>589.33</td><td>507.99</td><td>730.14</td><td>797.61</td><td>842.95</td><td>835.98</td><td>904.23</td><td></td></tr><tr><td>RanReal960_03_30</td><td>14.80/15.28</td><td>3.19/3.70</td><td>2.78/3.16</td><td>0.41/0.60</td><td>0.39/0.65</td><td>0.00/0.39</td><td>0.27/0.35</td><td>495.00</td><td>716.62</td><td>700.85</td><td>853.41</td><td>860.63</td><td>829.85</td><td>836.81</td><td></td></tr><tr><td>RanReal960_04_30</td><td>13.78/14.27</td><td>3.09/3.68</td><td>3.05/3.26</td><td>0.48/0.59</td><td>0.53/0.79</td><td>0.06/0.53</td><td>0.00/0.13</td><td>634.29</td><td>335.14</td><td>339.39</td><td>919.96</td><td>832.99</td><td>822.40</td><td>929.49</td><td></td></tr><tr><td>RanReal960_05_30</td><td>13.32/13.75</td><td>3.29/3.75</td><td>3.00/3.37</td><td>0.52/0.71</td><td>0.61/0.82</td><td>0.00/0.61</td><td>0.33/0.36</td><td>472.15</td><td>639.50</td><td>738.05</td><td>804.13</td><td>883.85</td><td>840.42</td><td>957.25</td><td></td></tr><tr><td>RanReal960_06_30</td><td>16.54/16.96</td><td>2.87/3.41</td><td>2.53/2.81</td><td>0.30/0.56</td><td>0.45/0.71</td><td>0.00/0.45</td><td>0.27/0.32</td><td>405.17</td><td>678.17</td><td>713.02</td><td>857.85</td><td>801.32</td><td>834.76</td><td>935.81</td><td></td></tr><tr><td>RanReal960_07_30</td><td>15.10/15.66</td><td>2.92/3.37</td><td>3.08/3.34</td><td>0.56/0.76</td><td>0.52/0.79</td><td>0.00/0.52</td><td>0.39/0.41</td><td>475.25</td><td>422.65</td><td>713.50</td><td>875.58</td><td>850.22</td><td>860.66</td><td>894.98</td><td></td></tr><tr><td>RanReal960_08_30</td><td>14.25/15.06</td><td>2.82/3.41</td><td>2.55/2.85</td><td>0.30/0.56</td><td>0.43/0.63</td><td>0.00/0.43</td><td>0.20/0.28</td><td>365.27</td><td>707.84</td><td>796.19</td><td>804.15</td><td>822.22</td><td>831.19</td><td>948.47</td><td></td></tr><tr><td>RanReal960_09_30</td><td>12.73/13.50</td><td>3.44/3.91</td><td>2.81/3.29</td><td>0.49/0.65</td><td>0.37/0.76</td><td>0.00/0.37</td><td>0.27/0.43</td><td>575.87</td><td>602.61</td><td>710.25</td><td>815.06</td><td>863.40</td><td>812.81</td><td>884.89</td><td></td></tr><tr><td>RanReal960_10_30</td><td>14.95/15.71</td><td>2.93/3.33</td><td>2.93/3.23</td><td>0.47/0.71</td><td>0.52/0.75</td><td>0.00/0.52</td><td>0.31/0.39</td><td>355.56</td><td>758.63</td><td>692.78</td><td>878.66</td><td>850.02</td><td>897.68</td><td>894.68</td><td></td></tr><tr><td>RanReal960_11_30</td><td>14.37/14.84</td><td>3.55/4.62</td><td>3.54/4.05</td><td>0.63/0.93</td><td>0.79/1.02</td><td>0.00/0.79</td><td>0.55/0.53</td><td>560.30</td><td>527.60</td><td>735.84</td><td>877.73</td><td>847.87</td><td>832.62</td><td>913.51</td><td></td></tr><tr><td>RanReal960_12_30</td><td>16.17/16.82</td><td>2.73/3.46</td><td>2.69/3.16</td><td>0.65/0.82</td><td>0.60/0.84</td><td>0.00/0.60</td><td>0.47/0.51</td><td>446.57</td><td>450.16</td><td>765.06</td><td>824.06</td><td>876.23</td><td>830.26</td><td>938.57</td><td></td></tr><tr><td>RanReal960_13_30</td><td>15.23/15.75</td><td>3.88/4.42</td><td>3.09/3.50</td><td>0.46/0.64</td><td>0.57/0.85</td><td>0.00/0.57</td><td>0.30/0.33</td><td>455.66</td><td>480.50</td><td>753.60</td><td>905.64</td><td>850.33</td><td>816.43</td><td>829.18</td><td></td></tr><tr><td>RanReal960_14_30</td><td>15.11/15.41</td><td>4.01/4.34</td><td>3.06/3.80</td><td>0.68/1.01</td><td>0.68/1.11</td><td>0.27/0.62</td><td>0.00/0.26</td><td>370.04</td><td>620.19</td><td>729.88</td><td>800.47</td><td>904.36</td><td>761.94</td><td>931.93</td><td></td></tr><tr><td>RanReal960_15_30</td><td>14.78/15.04</td><td>3.24/3.91</td><td>3.41/3.85</td><td>0.71/0.87</td><td>0.58/0.87</td><td>0.00/0.58</td><td>0.43/0.49</td><td>546.96</td><td>599.63</td><td>652.52</td><td>826.35</td><td>857.74</td><td>803.47</td><td>882.95</td><td></td></tr><tr><td>RanReal960_16_30</td><td>18.76/18.92</td><td>3.15/3.67</td><td>2.71/3.20</td><td>0.70/0.80</td><td>0.43/0.96</td><td>0.00/0.43</td><td>0.38/0.41</td><td>463.89</td><td>638.37</td><td>701.67</td><td>876.40</td><td>835.26</td><td>840.43</td><td>795.61</td><td></td></tr><tr><td>RanReal960_17_30</td><td>16.90/17.20</td><td>3.73/4.19</td><td>3.60/4.05</td><td>0.78/1.03</td><td>0.78/1.15</td><td>0.22/0.78</td><td>0.00/0.33</td><td>415.17</td><td>567.45</td><td>774.42</td><td>882.22</td><td>884.53</td><td>871.15</td><td>891.65</td><td></td></tr><tr><td>RanReal960_18_30</td><td>15.41/16.31</td><td>3.50/4.03</td><td>2.77/3.16</td><td>0.42/0.55</td><td>0.50/0.76</td><td>0.00/0.50</td><td>0.21/0.37</td><td>693.30</td><td>562.11</td><td>680.24</td><td>807.24</td><td>851.96</td><td>827.89</td><td>884.17</td><td></td></tr><tr><td>RanReal960_19_30</td><td>14.06/14.33</td><td>3.70/4.41</td><td>3.16/3.85</td><td>0.74/0.90</td><td>0.68/0.91</td><td>0.00/0.68</td><td>0.32/0.45</td><td>524.53</td><td>586.74</td><td>712.38</td><td>818.16</td><td>878.54</td><td>847.56</td><td>873.44</td><td></td></tr><tr><td>RanReal960_20_30</td><td>16.08/16.54</td><td>3.88/4.26</td><td>2.56/3.40</td><td>0.73/0.88</td><td>0.69/0.91</td><td>0.00/0.69</td><td>0.45/0.55</td><td>641.03</td><td>484.57</td><td>679.54</td><td>872.90</td><td>863.94</td><td>836.78</td><td>943.53</td><td></td></tr><tr><td>RanReal960_21_30</td><td>15.44/16.31</td><td>4.29/5.04</td><td>4.14/4.69</td><td>0.77/1.07</td><td>0.84/1.22</td><td>0.00/0.84</td><td>0.60/0.67</td><td>495.14</td><td>312.03</td><td>715.60</td><td>789.02</td><td>901.12</td><td>907.89</td><td>901.04</td><td></td></tr><tr><td>RanReal960_22_30</td><td>16.64/17.39</td><td>3.52/4.85</td><td>3.90/4.38</td><td>0.80/1.01</td><td>0.75/1.06</td><td>0.00/0.75</td><td>0.31/0.48</td><td>550.63</td><td>576.58</td><td>623.63</td><td>826.25</td><td>874.07</td><td>873.06</td><td>887.61</td><td></td></tr><tr><td>RanReal960_23_30</td><td>16.81/17.34</td><td>4.68/5.24</td><td>4.38/4.80</td><td>0.94/1.16</td><td>0.94/1.23</td><td>0.00/0.94</td><td>0.47/0.63</td><td>427.92</td><td>440.24</td><td>668.37</td><td>808.81</td><td>852.82</td><td>873.26</td><td>923.81</td><td></td></tr><tr><td>RanReal960_24_30</td><td>16.13/16.42</td><td>3.96/5.24</td><td>4.38/4.46</td><td>0.80/1.00</td><td>0.69/1.08</td><td>0.00/0.69</td><td>0.50/0.53</td><td>382.58</td><td>287.23</td><td>684.55</td><td>830.99</td><td>839.14</td><td>818.90</td><td>890.90</td><td></td></tr><tr><td>RanReal960_25_30</td><td>15.81/16.51</td><td>4.25/5.22</td><td>3.88/4.54</td><td>0.98/1.22</td><td>0.89/1.30</td><td>0.00/0.89</td><td>0.65/0.72</td><td>460.62</td><td>462.68</td><td>663.19</td><td>831.31</td><td>895.34</td><td>868.22</td><td>889.58</td><td></td></tr><tr><td>RanReal960_26_30</td><td>18.86/19.43</td><td>4.32/5.23</td><td>3.77/4.62</td><td>0.75/0.95</td><td>0.71/1.12</td><td>0.00/0.71</td><td>0.61/0.75</td><td>464.96</td><td>443.56</td><td>625.41</td><td>766.03</td><td>872.94</td><td>836.76</td><td>864.12</td><td></td></tr><tr><td>RanReal960_27_30</td><td>17.58/18.02</td><td>3.86/4.52</td><td>3.89/4.32</td><td>0.74/1.05</td><td>0.69/1.16</td><td>0.00/0.69</td><td>0.38/0.42</td><td>382.48</td><td>287.23</td><td>684.55</td><td>918.06</td><td>909.03</td><td>878.59</td><td>875.95</td><td></td></tr><tr><td>RanReal960_28_30</td><td>16.32/17.07</td><td>3.98/5.01</td><td>3.94/4.61</td><td>0.61/1.01</td><td>0.83/1.11</td><td>0.00/0.83</td><td>0.38/0.51</td><td>616.02</td><td>344.11</td><td>750.21</td><td>851.60</td><td>911.42</td><td>859.76</td><td>870.01</td><td></td></tr><tr><td>RanReal960_29_30</td><td>15.36/15.80</td><td>4.08/5.04</td><td>4.27/4.72</td><td>0.85/1.16</td><td>0.96/1.27</td><td>0.00/0.96</td><td>0.41/0.63</td><td>454.24</td><td>454.70</td><td>685.44</td><td>770.73</td><td>849.73</td><td>868.30</td><td>900.64</td><td></td></tr><tr><td>RanReal960_30_30</td><td>17.99/18.30</td><td>4.62/5.21</td><td>4.03/4.55</td><td>0.84/1.04</td><td>0.94/1.28</td><td>0.00/0.47</td><td>0.63/0.75</td><td>403.71</td><td>367.32</td><td>617.20</td><td>855.35</td><td>898.95</td><td>857.38</td><td>878.89</td><td></td></tr><tr><td>MDG-a.21</td><td>19.04/19.68</td><td>6.83/7.49</td><td>3.90/4.13</td><td>2.58/3.34</td><td>0.16/0.53</td><td>0.00/0.16</td><td>1.57/1.77</td><td>1113.87</td><td>1996.39</td><td>1997.42</td><td>1938.05</td><td>1518.30</td><td>1867.83</td><td>1872.28</td><td></td></tr><tr><td>MDG-a.22</td><td>17.88/18.08</td><td>15.08/15.73</td><td>3.79/4.52</td><td>1.47/2.31</td><td>0.48/0.60</td><td>0.00/0.48</td><td>1.43/1.52</td><td>1067.71</td><td>1999.48</td><td>1996.70</td><td>1840.87</td><td>1806.64</td><td>1801.35</td><td>1931.75</td><td></td></tr><tr><td>MDG-a.23</td><td>18.11/18.59</td><td>7.00/7.27</td><td>4.70/5.98</td><td>2.99/3.18</td><td>0.29/0.46</td><td>0.00/0.29</td><td>0.17/1.20</td><td>1082.92</td><td>1997.29</td><td>1997.69</td><td>1869.53</td><td>1741.74</td><td>1839.26</td><td>1937.18</td><td></td></tr><tr><td>MDG-a.24</td><td>19.44/20.01</td><td>14.49/15.82</td><td>4.05/5.03</td><td>2.62/3.06</td><td>0.34/0.50</td><td>0.00/0.34</td><td>1.71/2.02</td><td>911.13</td><td>1997.83</td><td>1996.65</td><td>1892.93</td><td>1697.71</td><td>1830.54</td><td>1903.31</td><td></td></tr><tr><td>MDG-a.25</td><td>19.39/19.80</td><td>7.04/7.43</td><td>3.89/6.04</td><td>2.23/3.37</td><td>2.76/0.59</td><td>0.00/2.76</td><td>1.88/2.95</td><td>1074.60</td><td>1996.68</td><td>1997.50</td><td>1829.42</td><td>1663.95</td><td>1870.12</td><td>1824.79</td><td></td></tr><tr><td>MDG-a.26</td><td>20.32/20.70</td><td>6.80/7.30</td><td>3.87/5.78</td><td>2.42/3.24</td><td>1.34/0.53</td><td>0.00/1.34</td><td>2.22/2.29</td><td>1149.10</td><td>1996.75</td><td>1997.02</td><td>1923.60</td><td>1665.89</td><td>1790.90</td><td>1926.98</td><td></td></tr><tr><td>MDG-a.27</td><td>18.21/18.60</td><td>15.07/15.49</td><td>6.56/6.93</td><td>1.66/2.30</td><td>0.43/0.69</td><td>0.00/0.43</td><td>1.12/1.35</td><td>854.07</td><td>1999.38</td><td>1998.81</td><td>1790.23</td><td>1635.81</td><td>1890.33</td><td>1837.59</td><td></td></tr><tr><td>MDG-a.28</td><td>18.77/19.11</td><td>14.77/15.25</td><td>3.85/4.87</td><td>2.35/3.11</td><td>0.41/0.62</td><td>0.00/0.41</td><td>1.77/2.03</td><td>924.16</td><td>1999.27</td><td>1997.85</td><td>1920.76</td><td>1681.61</td><td>1879.05</td><td>1733.96</td><td></td></tr><tr><td>MDG-a.29</td><td>18.88/19.25</td><td>6.84/7.22</td><td>5.25/5.87</td><td>1.76/2.94</td><td>0.48/0.69</td><td>0.00/0.48</td><td>1.48/1.67</td><td>1026.38</td><td>1996.99</td><td>1997.08</td><td>1903.37</td><td>1835.42</td><td>1859.38</td><td>1913.92</td><td></td></tr><tr><td>MDG-a.30</td><td>19.19/19.75</td><td>13.48/14.73</td><td>3.91/5.42</td><td>1.78/2.61</td><td>0.47/0.60</td><td>0.00/0.47</td><td>1.82/1.87</td><td>1028.09</td><td>1998.03</td><td>1998.08</td><td>1820.66</td><td>1692.74</td><td>1793.70</td><td>1863.39</td><td></td></tr><tr><td>MDG-a.31</td><td>19.03/19.38</td><td>14.08/14.97</td><td>3.77/4.95</td><td>2.50/3.09</td><td>0.48/0.66</td><td>0.00/0.48</td><td>1.86/1.98</td><td>1302.25</td><td>1998.60</td><td>1997.17</td><td>1912.22</td><td>1691.17</td><td>1789.28</td><td>1703.24</td><td></td></tr><tr><td>MDG-a.32</td><td>18.96/19.29</td><td>12.03/14.31</td><td>6.05/7.72</td><td>2.72/3.39</td><td>0.36/0.53</td><td>0.00/0.36</td><td>2.48/2.64</td><td>575.50</td><td>1998.49</td><td>1997.63</td><td>1888.87</td><td>1663.50</td><td>1853.43</td><td>1913.13</td><td></td></tr><tr><td>MDG-a.33</td><td>17.93/18.38</td><td>7.00/7.37</td><td>4.02/4.60</td><td>1.72/2.91</td><td>0.45/0.63</td><td>0.00/0.45</td><td>1.36/1.99</td><td>1160.48</td><td>1997.66</td><td>1997.26</td><td>1908.54</td><td>1816.25</td><td>1908.27</td><td>1960.62</td><td></td></tr><tr><td>MDG-a.34</td><td>19.42/19.71</td><td>12.60/14.76</td><td>5.62/6.16</td><td>2.60/3.35</td><td>0.39/0.57</td><td>0.00/0.35</td><td>2.06/2.34</td><td>630.93</td><td>1998.63</td><td>1996.86</td><td>1812.31</td><td>1759.61</td><td>1840.43</td><td>1820.16</td><td></td></tr><tr><td>MDG-a.35</td><td>19.01/19.27</td><td>15.24/16.00</td><td>3.85/4.02</td><td>2.39/2.88</td><td>0.33/0.64</td><td>0.00/0.33</td><td>2.11/2.38</td><td>1051.55</td><td>1998.13</td><td>1996.08</td><td>1810.68</td><td>1661.62</td><td>1797.99</td><td>1895.51</td><td></td></tr><tr><td>MDG-a.36</td><td>19.63/19.87</td><td>14.32/15.40</td><td>4.85/6.81</td><td>1.80/3.17</td><td>0.45/0.55</td><td>0.00/0.45</td><td>1.42/1.99</td><td>899.31</td><td>1998.23</td><td>1999.26</td><td>1838.15</td><td>1700.47</td><td>1842.45</td><td>1715.11</td><td></td></tr><tr><td>MDG-a.37</td><td>18.89/19.31</td><td>11.40/12.72</td><td>4.76/6.49</td><td>0.93/1.93</td><td>0.36/0.55</td><td>0.00/0.36</td><td>0.57/0.67</td><td>752.54</td><td>1997.35</td><td>1999.13</td><td>1581.54</td><td>1752.65</td><td>1833.76</td><td>1935.18</td><td></td></tr><tr><td>MDG-a.38</td><td>18.13/19.25</td><td>7.25/8.63</td><td>3.93/4.77</td><td>2.12/2.81</td><td>0.40/0.50</td><td>0.00/0.40</td><td>1.81/2.04</td><td>1105.56</td><td>1996.57</td><td>1997.76</td><td>1863.12</td><td>1769.98</td><td>1804.21</td><td>1909.01</td><td></td></tr><tr><td>MDG-a.39</td><td>18.91/19.41</td><td>6.89/7.25</td><td>4.91/5.54</td><td>2.47/3.21</td><td>0.36/0.58</td><td>0.00/0.36</td><td>1.39/2.14</td><td>1018.71</td><td>1997.23</td><td>1998.49</td><td>1801.77</td><td>1732.95</td><td>1879.26</td><td>1874.83</td><td></td></tr><tr><td>MDG-a.40</td><td>19.90/20.31</td><td>14.01/14.98</td><td>3.64/3.90</td><td>3.07/3.37</td><td>0.38/0.51</td><td>0.00/0.31</td><td>2.19/2.39</td><td>1097.38</td><td>1998.11</td><td>1735.43</td><td>1770.49</td><td>1819.48</td><td>1876.35</td><td>1846.35</td><td></td></tr><tr><td>Average</td><td>16.94/17.44</td><td>6.60/7.36</td><td>3.77/4.47</td><td>1.27/1.70</td><td>0.61/0.80</td><td>0.01/0.61</td><td>0.89/1.07</td><td>694.09</td><td>1115.02</td><td>1221.46</td><td>1251.36</td><td>1202.49</td><td>1240.53</td><td>1282.67</td><td></td></tr></tbody></table>
<table><caption>Table 15. Comparison of FITS with the six state-of-art algorithms on handover minimization instances with $n \ge 100$, where the objective is to minimize the total cost function.</caption><thead><tr><th rowspan="2">Name</th><th colspan="2">GevPR-HMP</th><th colspan="2">GQAP</th><th colspan="2">BRKGA</th><th colspan="2">IVNS</th><th colspan="2">GVNS</th><th colspan="2">SGVNS</th><th colspan="2">FITS</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th></tr></thead><tbody><tr><td>100.15.270001</td><td>19174.00</td><td>19174.00</td><td>19000.00</td><td>19114.80</td><td>19000.00</td><td>19533.20</td><td>19000.00</td><td>19000.00</td><td>19000.00</td><td>19000.00</td><td>19000.00</td><td>19000.00</td><td>19000.00</td></tr><tr><td>100.15.270002</td><td>22686.00</td><td>22686.00</td><td>22686.00</td><td>22805.60</td><td>23288.00</td><td>23478.00</td><td>22686.00</td><td>22686.00</td><td>22686.00</td><td>22686.00</td><td>22686.00</td><td>22686.00</td><td>22686.00</td></tr><tr><td>100.15.270003</td><td>14558.00</td><td>14558.00</td><td>14558.00</td><td>14568.80</td><td>14616.00</td><td>14655.20</td><td>14558.00</td><td>14558.00</td><td>15184.00</td><td>15184.00</td><td>15184.00</td><td>14558.00</td><td>14558.00</td></tr><tr><td>100.15.270004</td><td>19762.00</td><td>19762.00</td><td>19762.00</td><td>19782.00</td><td>19711.20</td><td>20177.60</td><td>19700.00</td><td>19700.00</td><td>19700.00</td><td>19700.00</td><td>19700.00</td><td>19700.00</td><td>19700.00</td></tr><tr><td>100.15.270005</td><td>22892.00</td><td>22892.00</td><td>22746.00</td><td>22885.20</td><td>23092.00</td><td>23430.80</td><td>22746.00</td><td>22746.00</td><td>22894.00</td><td>22894.00</td><td>22894.00</td><td>22746.00</td><td>22746.00</td></tr><tr><td>100.25.270001</td><td>36412.00</td><td>36665.20</td><td>36448.00</td><td>36608.00</td><td>36752.00</td><td>37107.20</td><td>36412.00</td><td>36412.00</td><td>36412.00</td><td>36412.00</td><td>36412.00</td><td>36412.00</td><td>36412.00</td></tr><tr><td>100.25.270002</td><td>39144.00</td><td>39199.20</td><td>38608.00</td><td>38677.20</td><td>39253.60</td><td>39515.60</td><td>38608.00</td><td>38608.00</td><td>38608.00</td><td>38608.00</td><td>38608.00</td><td>38608.00</td><td>38608.00</td></tr><tr><td>100.25.270003</td><td>32966.00</td><td>33098.00</td><td>32686.00</td><td>32717.60</td><td>32978.00</td><td>33356.00</td><td>32686.00</td><td>32686.00</td><td>32686.00</td><td>32686.00</td><td>32686.00</td><td>32686.00</td><td>32686.00</td></tr><tr><td>100.25.270004</td><td>35678.00</td><td>35801.20</td><td>35322.00</td><td>35433.20</td><td>35954.00</td><td>36068.00</td><td>35322.00</td><td>35322.00</td><td>35322.00</td><td>35322.00</td><td>35322.00</td><td>35322.00</td><td>35322.00</td></tr><tr><td>100.25.270005</td><td>36906.00</td><td>36911.20</td><td>36878.00</td><td>36968.00</td><td>37100.00</td><td>37363.60</td><td>36690.00</td><td>36690.00</td><td>37092.00</td><td>37092.00</td><td>36690.00</td><td>36690.00</td><td>36690.00</td></tr><tr><td>100.50.270001</td><td>60822.00</td><td>61074.00</td><td>61172.00</td><td>61234.80</td><td>61554.00</td><td>61845.20</td><td>60822.00</td><td>60822.00</td><td>60822.00</td><td>60822.00</td><td>60822.00</td><td>60822.00</td><td>60822.00</td></tr><tr><td>100.50.270002</td><td>62046.00</td><td>62065.20</td><td>62022.00</td><td>62090.80</td><td>62524.00</td><td>62684.80</td><td>62022.00</td><td>62022.00</td><td>62022.00</td><td>62022.00</td><td>62022.00</td><td>62022.00</td><td>62022.00</td></tr><tr><td>100.50.270003</td><td>54618.00</td><td>54707.60</td><td>54596.00</td><td>55433.60</td><td>55192.00</td><td>55390.80</td><td>54596.00</td><td>54596.00</td><td>54596.00</td><td>54596.00</td><td>54596.00</td><td>54596.00</td><td>54596.00</td></tr><tr><td>100.50.270004</td><td>57894.00</td><td>57906.40</td><td>57894.00</td><td>57903.60</td><td>58208.00</td><td>58358.00</td><td>57894.00</td><td>57894.00</td><td>57894.00</td><td>57894.00</td><td>57894.00</td><td>57894.00</td><td>57894.00</td></tr><tr><td>100.50.270005</td><td>61088.00</td><td>61285.20</td><td>61318.00</td><td>61318.00</td><td>62784.00</td><td>63042.00</td><td>61080.00</td><td>61092.00</td><td>61080.00</td><td>61102.10</td><td>61080.00</td><td>61080.00</td><td>61080.00</td></tr><tr><td>200.15.270001</td><td>81558.00</td><td>81915.20</td><td>82834.00</td><td>84327.20</td><td>81558.00</td><td>81946.00</td><td>81558.00</td><td>81558.00</td><td>81558.00</td><td>81558.00</td><td>81558.00</td><td>81558.00</td><td>81558.00</td></tr><tr><td>200.15.270002</td><td>89810.00</td><td>90949.60</td><td>90240.00</td><td>93462.00</td><td>90506.00</td><td>92374.20</td><td>89492.00</td><td>89407.40</td><td>89463.60</td><td>89420.00</td><td>89275.20</td><td>89492.00</td><td>89275.20</td></tr><tr><td>200.15.270003</td><td>79323.00</td><td>79323.00</td><td>80980.00</td><td>81716.80</td><td>79548.00</td><td>79584.00</td><td>79232.00</td><td>79252.10</td><td>79232.00</td><td>79232.00</td><td>79232.00</td><td>79232.00</td><td>79232.00</td></tr><tr><td>200.15.270004</td><td>78324.00</td><td>78324.00</td><td>80538.00</td><td>84737.60</td><td>80026.00</td><td>81019.20</td><td>78324.00</td><td>78549.10</td><td>78324.00</td><td>78376.10</td><td>78324.00</td><td>78324.00</td><td>78324.00</td></tr><tr><td>200.15.270005</td><td>95998.00</td><td>96492.20</td><td>98826.00</td><td>100146.80</td><td>98830.00</td><td>99065.60</td><td>95680.00</td><td>96333.00</td><td>95734.00</td><td>95734.00</td><td>95734.00</td><td>95734.00</td><td>95734.00</td></tr><tr><td>200.25.270001</td><td>133108.00</td><td>133674.00</td><td>138454.00</td><td>141961.60</td><td>140492.00</td><td>141938.80</td><td>133168.00</td><td>133168.00</td><td>133774.00</td><td>133774.00</td><td>133774.00</td><td>133774.00</td><td>133774.00</td></tr><tr><td>200.25.270002</td><td>136038.00</td><td>137514.00</td><td>140066.00</td><td>141666.40</td><td>140690.00</td><td>141012.80</td><td>133778.00</td><td>133954.40</td><td>133876.00</td><td>133876.00</td><td>133876.00</td><td>133876.00</td><td>133876.00</td></tr><tr><td>200.25.270003</td><td>139438.00</td><td>139962.40</td><td>144120.00</td><td>145647.60</td><td>143724.00</td><td>144409.60</td><td>136782.00</td><td>136801.50</td><td>136782.00</td><td>136802.70</td><td>136782.00</td><td>136792.50</td><td>136782.00</td></tr><tr><td>200.25.270004</td><td>128554.00</td><td>129508.00</td><td>134054.00</td><td>136128.40</td><td>131786.00</td><td>133894.00</td><td>128246.00</td><td>128274.60</td><td>128472.00</td><td>128491.80</td><td>128472.00</td><td>128486.30</td><td>128246.00</td></tr><tr><td>200.25.270005</td><td>148402.00</td><td>149298.80</td><td>154260.00</td><td>157307.20</td><td>152934.00</td><td>154275.20</td><td>147844.00</td><td>147844.00</td><td>148050.00</td><td>148050.00</td><td>148050.00</td><td>148050.00</td><td>147844.00</td></tr><tr><td>200.50.270001</td><td>221550.00</td><td>221851.60</td><td>221821.60</td><td>223056.80</td><td>223090.00</td><td>224034.00</td><td>215388.00</td><td>215697.20</td><td>215388.00</td><td>215449.50</td><td>215388.00</td><td>215722.70</td><td>147844.00</td></tr><tr><td>200.50.270002</td><td>218254.00</td><td>218761.20</td><td>219910.10</td><td>221346.80</td><td>219834.00</td><td>221131.20</td><td>212798.00</td><td>213005.10</td><td>213178.00</td><td>213251.80</td><td>213178.00</td><td>213239.50</td><td>212798.00</td></tr><tr><td>200.50.270003</td><td>221500.00</td><td>222315.60</td><td>222404.00</td><td>223175.20</td><td>221110.00</td><td>221568.00</td><td>214364.00</td><td>214678.60</td><td>214364.00</td><td>214451.10</td><td>214364.00</td><td>214394.80</td><td>214364.00</td></tr><tr><td>200.50.270004</td><td>212044.00</td><td>212626.80</td><td>212544.00</td><td>213880.80</td><td>213170.00</td><td>213509.20</td><td>20647.00</td><td>206985.40</td><td>207254.00</td><td>207343.60</td><td>207254.00</td><td>207301.70</td><td>206476.00</td></tr><tr><td>200.50.270005</td><td>231890.00</td><td>232938.00</td><td>236136.00</td><td>232828.80</td><td>237156.00</td><td>237939.60</td><td>229918.00</td><td>230107.30</td><td>230484.00</td><td>230630.30</td><td>230484.00</td><td>230543.60</td><td>229900.00</td></tr><tr><td>400.15.270001</td><td>372694.00</td><td>373542.20</td><td>456158.00</td><td>475012.00</td><td>375350.00</td><td>378718.00</td><td>369048.00</td><td>369270.80</td><td>370878.00</td><td>370874.20</td><td>369048.00</td><td>369408.00</td><td>369408.00</td></tr><tr><td>400.15.270002</td><td>370274.00</td><td>373304.80</td><td>460232.00</td><td>465669.20</td><td>383096.00</td><td>386282.80</td><td>365878.00</td><td>370147.60</td><td>366062.00</td><td>369675.00</td><td>366062.00</td><td>368351.10</td><td>365878.00</td></tr><tr><td>400.15.270003</td><td>358684.00</td><td>360152.80</td><td>448830.00</td><td>456513.60</td><td>366314.00</td><td>369552.80</td><td>352588.00</td><td>358234.90</td><td>353078.00</td><td>355399.30</td><td>353078.00</td><td>355002.50</td><td>352588.00</td></tr><tr><td>400.15.270004</td><td>334430.00</td><td>336826.40</td><td>406834.00</td><td>447753.20</td><td>346282.00</td><td>349110.00</td><td>331888.00</td><td>339014.80</td><td>331888.00</td><td>335504.80</td><td>331888.00</td><td>337685.30</td><td>331888.00</td></tr><tr><td>400.15.270005</td><td>361904.00</td><td>365974.00</td><td>457274.00</td><td>476186.00</td><td>377094.00</td><td>380204.40</td><td>360422.00</td><td>364127.30</td><td>360714.00</td><td>364176.50</td><td>360714.00</td><td>362735.10</td><td>360422.00</td></tr><tr><td>400.25.270001</td><td>570852.00</td><td>571930.00</td><td>663908.00</td><td>694715.60</td><td>579130.00</td><td>584584.80</td><td>545662.00</td><td>547000.40</td><td>545674.00</td><td>547537.20</td><td>545228.00</td><td>546479.10</td><td>545540.00</td></tr><tr><td>400.25.270002</td><td>544568.00</td><td>547953.60</td><td>658440.00</td><td>679772.40</td><td>554840.00</td><td>560692.00</td><td>528470.00</td><td>530441.40</td><td>528470.00</td><td>530204.70</td><td>528470.00</td><td>529495.00</td><td>528470.00</td></tr><tr><td>400.25.270003</td><td>548000.00</td><td>554179.60</td><td>667932.00</td><td>680754.80</td><td>553162.00</td><td>555433.20</td><td>525016.00</td><td>527990.20</td><td>525016.00</td><td>527434.30</td><td>525016.00</td><td>526789.10</td><td>524678.00</td></tr><tr><td>400.25.270004</td><td>501750.00</td><td>504474.60</td><td>567672.00</td><td>583110.20</td><td>516416.00</td><td>517528.00</td><td>481660.00</td><td>482858.10</td><td>481920.00</td><td>482922.10</td><td>481994.00</td><td>483238.50</td><td>481436.00</td></tr><tr><td>400.25.270005</td><td>556044.00</td><td>561315.20</td><td>679848.00</td><td>703440.00</td><td>585070.00</td><td>589444.00</td><td>548100.00</td><td>548744.40</td><td>548450.00</td><td>549737.80</td><td>548450.00</td><td>549170.50</td><td>548100.00</td></tr><tr><td>400.50.270001</td><td>851412.00</td><td>854656.00</td><td>951882.00</td><td>957526.00</td><td>879438.00</td><td>881239.60</td><td>824868.00</td><td>825682.50</td><td>826252.00</td><td>826962.10</td><td>825956.00</td><td>826809.80</td><td>824656.00</td></tr><tr><td>400.50.270002</td><td>845486.00</td><td>848217.60</td><td>874226.00</td><td>877662.00</td><td>874242.00</td><td>850384.80</td><td>801722.00</td><td>802977.20</td><td>824468.00</td><td>826207.90</td><td>823762.00</td><td>825441.00</td><td>822336.00</td></tr><tr><td>400.50.270003</td><td>819242.00</td><td>824118.80</td><td>919140.00</td><td>927517.60</td><td>843242.00</td><td>850384.80</td><td>801722.00</td><td>802977.20</td><td>802936.00</td><td>804269.90</td><td>801824.00</td><td>803537.30</td><td>801472.00</td></tr><tr><td>400.50.270004</td><td>774564.00</td><td>777953.60</td><td>878912.00</td><td>885893.20</td><td>806960.00</td><td>810186.80</td><td>760514.00</td><td>761484.60</td><td>760044.00</td><td>761455.70</td><td>760044.00</td><td>762079.10</td><td>760232.00</td></tr><tr><td>400.50.270005</td><td>854726.00</td><td>857133.20</td><td>940538.50</td><td>950535.60</td><td>882060.00</td><td>885058.80</td><td>828398.00</td><td>829852.60</td><td>828902.00</td><td>829946.80</td><td>828450.00</td><td>829578.20</td><td>828398.00</td></tr></tbody><tfoot><tr><td>#Best</td><td>9</td><td>4</td><td>11</td><td>0</td><td>0</td><td>0</td><td>37</td><td>18</td><td>23</td><td>15</td><td>24</td><td>25</td><td>43</td><td>30</td></tr><tr><td>p-value</td><td>1.97e-9</td><td>1.68e-8</td><td>5.51e-9</td><td>1.97e-11</td><td>5.47e-11</td><td>1.97e-11</td><td>0</td><td>0.02</td><td>1.19e-5</td><td>0.08</td><td>7.44e-5</td><td>0.38</td><td></td><td></td></tr></tfoot></table>
<table><caption>Table 16. Comparison between FITS and six state-of-the-art algorithms on the handover minimization instances with $n \ge 100$.</caption><thead><tr><th rowspan="2">Name</th><th rowspan="2">GevPR-HMP</th><th rowspan="2">GQAP</th><th rowspan="2">BRKVA</th><th colspan="4">Devbest/Devavg (%)</th><th colspan="4">t<sub>avg</sub></th></tr><tr><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th><th>IVNS</th><th>GVNS</th><th>SGVNS</th><th>FITS</th></tr></thead><tbody><tr><td>100_15_270001</td><td>0.92/0.92</td><td>0.00/0.60</td><td>0.00/2.81</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>1.03</td><td>0.24</td><td>0.28</td><td>3.84</td></tr><tr><td>100_15_270002</td><td>0.00/0.00</td><td>0.00/0.53</td><td>2.65/3.49</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>1.54</td><td>0.39</td><td>0.49</td><td>25.06</td></tr><tr><td>100_15_270003</td><td>0.00/0.00</td><td>0.00/0.07</td><td>0.40/0.67</td><td>0.00/0.00</td><td>4.30/4.30</td><td>4.30/4.30</td><td>0.00/0.00</td><td>0.08</td><td>0.06</td><td>0.10</td><td>0.14</td></tr><tr><td>100_15_270004</td><td>0.31/0.31</td><td>0.00/0.06</td><td>0.92/2.42</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.30</td><td>0.13</td><td>0.11</td><td>2.03</td></tr><tr><td>100_15_270005</td><td>0.64/0.64</td><td>0.00/0.61</td><td>1.52/3.01</td><td>0.00/0.00</td><td>0.65/0.65</td><td>0.65/0.65</td><td>0.00/0.00</td><td>1.62</td><td>0.24</td><td>0.36</td><td>11.35</td></tr><tr><td>100_25_270001</td><td>0.00/0.70</td><td>0.10/0.54</td><td>0.93/1.91</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>1.54</td><td>0.64</td><td>0.82</td><td>4.38</td></tr><tr><td>100_25_270002</td><td>1.39/1.53</td><td>0.00/0.18</td><td>1.68/2.35</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>1.62</td><td>1.33</td><td>0.66</td><td>5.57</td></tr><tr><td>100_25_270003</td><td>0.86/1.26</td><td>0.00/0.10</td><td>0.07/2.05</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>5.42</td><td>1.40</td><td>0.86</td><td>12.78</td></tr><tr><td>100_25_270004</td><td>1.01/1.36</td><td>0.00/0.31</td><td>1.79/2.11</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>6.18</td><td>0.13</td><td>0.21</td><td>19.05</td></tr><tr><td>100_25_270005</td><td>0.59/0.60</td><td>0.51/0.76</td><td>1.12/1.84</td><td>0.00/0.00</td><td>1.10/1.10</td><td>1.10/1.10</td><td>0.00/0.00</td><td>6.89</td><td>0.15</td><td>0.23</td><td>14.61</td></tr><tr><td>100_50_270001</td><td>0.00/0.25</td><td>0.41/0.51</td><td>1.04/1.52</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>9.19</td><td>0.45</td><td>0.48</td><td>25.75</td></tr><tr><td>100_50_270002</td><td>0.04/0.07</td><td>0.00/0.11</td><td>0.81/1.07</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>10.47</td><td>0.87</td><td>0.71</td><td>7.41</td></tr><tr><td>100_50_270003</td><td>0.04/0.20</td><td>0.00/0.12</td><td>1.09/1.46</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>7.61</td><td>0.68</td><td>0.59</td><td>8.70</td></tr><tr><td>100_50_270004</td><td>0.00/0.02</td><td>0.00/0.02</td><td>0.54/0.80</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>5.63</td><td>1.26</td><td>0.05</td><td>14.18</td></tr><tr><td>100_50_270005</td><td>0.01/0.33</td><td>0.39/0.39</td><td>2.79/3.21</td><td>0.00/0.02</td><td>0.00/0.04</td><td>0.00/0.00</td><td>0.00/0.26</td><td>9.45</td><td>1.42</td><td>0.43</td><td>42.71</td></tr><tr><td>200_15_270001</td><td>0.00/0.44</td><td>1.56/3.40</td><td>0.00/0.48</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.00</td><td>25.19</td><td>2.23</td><td>2.77</td><td>67.35</td></tr><tr><td>200_15_270002</td><td>0.36/1.63</td><td>1.26/4.44</td><td>1.13/3.22</td><td>0.00/1.02</td><td>0.00/0.42</td><td>0.00/0.26</td><td>0.00/0.79</td><td>70.30</td><td>20.16</td><td>55.81</td><td>116.10</td></tr><tr><td>200_15_270003</td><td>0.00/0.00</td><td>2.21/3.14</td><td>0.40/0.44</td><td>0.00/0.03</td><td>0.00/0.00</td><td>0.00/0.00</td><td>0.00/0.01</td><td>38.27</td><td>2.08</td><td>1.85</td><td>13.10</td></tr><tr><td>200_15_270004</td><td>0.00/0.00</td><td>2.83/8.19</td><td>2.17/3.44</td><td>0.00/0.29</td><td>0.00/0.07</td><td>0.00/0.00</td><td>0.00/0.07</td><td>48.99</td><td>13.94</td><td>20.44</td><td>43.07</td></tr><tr><td>200_15_270005</td><td>0.33/0.85</td><td>3.29/4.67</td><td>3.29/3.54</td><td>0.00/0.68</td><td>0.06/0.06</td><td>0.06/0.06</td><td>0.00/0.36</td><td>11.33</td><td>29.97</td><td>31.91</td><td>40.97</td></tr><tr><td>200_25_270001</td><td>0.00/0.38</td><td>3.97/6.60</td><td>5.50/6.59</td><td>0.00/0.00</td><td>0.46/0.46</td><td>0.46/0.46</td><td>0.00/0.00</td><td>41.78</td><td>24.60</td><td>54.73</td><td>83.74</td></tr><tr><td>200_25_270002</td><td>1.69/2.79</td><td>4.70/5.90</td><td>5.17/5.41</td><td>0.00/0.13</td><td>0.07/0.07</td><td>0.07/0.07</td><td>0.00/0.05</td><td>87.71</td><td>47.07</td><td>19.05</td><td>91.89</td></tr><tr><td>200_25_270003</td><td>1.94/2.33</td><td>5.36/6.48</td><td>5.08/5.58</td><td>0.00/0.01</td><td>0.00/21.95</td><td>0.00/0.01</td><td>0.00/0.06</td><td>53.89</td><td>86.94</td><td>51.56</td><td>103.30</td></tr><tr><td>200_25_270004</td><td>0.24/0.98</td><td>4.53/6.15</td><td>2.76/4.40</td><td>0.00/0.02</td><td>0.18/0.19</td><td>0.18/0.19</td><td>0.00/0.00</td><td>49.99</td><td>35.98</td><td>19.00</td><td>92.27</td></tr><tr><td>200_25_270005</td><td>0.38/0.98</td><td>4.34/6.40</td><td>3.44/4.35</td><td>0.00/0.00</td><td>0.14/0.14</td><td>0.14/0.14</td><td>0.00/0.00</td><td>9.64</td><td>6.86</td><td>5.17</td><td>78.63</td></tr><tr><td>200_50_270001</td><td>2.86/2.99</td><td>3.58/3.79</td><td>3.58/4.01</td><td>0.00/0.14</td><td>0.00/0.03</td><td>0.00/0.03</td><td>0.00/0.16</td><td>76.15</td><td>62.88</td><td>65.42</td><td>87.34</td></tr><tr><td>200_50_270002</td><td>2.56/2.80</td><td>3.34/4.02</td><td>3.31/3.92</td><td>0.00/0.10</td><td>0.18/0.21</td><td>0.18/0.21</td><td>0.00/0.07</td><td>69.51</td><td>25.08</td><td>14.92</td><td>105.89</td></tr><tr><td>200_50_270003</td><td>3.33/3.71</td><td>3.75/4.11</td><td>3.15/3.36</td><td>0.00/0.15</td><td>0.00/0.04</td><td>0.00/0.01</td><td>0.00/0.22</td><td>69.87</td><td>46.94</td><td>83.88</td><td>101.50</td></tr><tr><td>200_50_270004</td><td>2.70/2.98</td><td>2.94/3.59</td><td>3.24/3.41</td><td>0.00/0.25</td><td>3.38/30.93</td><td>0.38/0.40</td><td>0.00/0.11</td><td>81.66</td><td>64.90</td><td>55.80</td><td>111.74</td></tr><tr><td>200_50_270005</td><td>0.87/1.32</td><td>2.71/3.62</td><td>3.16/3.50</td><td>0.01/0.09</td><td>0.25/0.32</td><td>0.25/0.28</td><td>0.00/0.03</td><td>86.92</td><td>65.05</td><td>68.95</td><td>131.04</td></tr><tr><td>400_15_270001</td><td>0.99/1.73</td><td>23.60/28.71</td><td>1.79/2.62</td><td>0.00/1.25</td><td>0.00/0.49</td><td>0.00/0.47</td><td>0.00/0.73</td><td>184.94</td><td>114.10</td><td>154.72</td><td>218.52</td></tr><tr><td>400_15_270002</td><td>1.20/2.03</td><td>25.79/27.27</td><td>4.71/5.58</td><td>0.00/1.17</td><td>0.05/1.04</td><td>0.05/0.68</td><td>0.00/0.91</td><td>197.33</td><td>195.42</td><td>162.95</td><td>230.06</td></tr><tr><td>400_15_270003</td><td>1.73/2.15</td><td>27.30/29.48</td><td>3.89/4.81</td><td>0.00/1.60</td><td>0.14/0.80</td><td>0.14/0.68</td><td>0.00/0.62</td><td>156.99</td><td>73.55</td><td>125.33</td><td>253.96</td></tr><tr><td>400_15_270004</td><td>0.77/1.49</td><td>22.58/34.91</td><td>4.34/5.19</td><td>0.00/2.15</td><td>0.00/1.09</td><td>0.00/1.75</td><td>0.00/1.81</td><td>245.49</td><td>123.96</td><td>171.49</td><td>226.90</td></tr><tr><td>400_15_270005</td><td>0.41/1.54</td><td>26.87/32.12</td><td>4.63/5.49</td><td>0.00/1.03</td><td>0.08/1.04</td><td>0.08/0.64</td><td>0.00/0.62</td><td>234.97</td><td>136.54</td><td>243.64</td><td>271.41</td></tr><tr><td>400_25_270001</td><td>4.70/4.90</td><td>21.77/27.42</td><td>6.22/7.22</td><td>0.08/0.33</td><td>0.08/0.42</td><td>0.00/0.23</td><td>0.06/0.42</td><td>239.15</td><td>124.71</td><td>127.27</td><td>280.77</td></tr><tr><td>400_25_270002</td><td>3.05/3.69</td><td>24.59/28.63</td><td>4.99/6.10</td><td>0.00/0.37</td><td>3.38/30.93</td><td>0.38/0.40</td><td>0.00/0.11</td><td>206.04</td><td>109.35</td><td>114.10</td><td>263.82</td></tr><tr><td>400_25_270003</td><td>4.45/5.62</td><td>27.31/29.75</td><td>5.43/5.86</td><td>0.06/0.63</td><td>0.06/0.53</td><td>0.06/0.40</td><td>0.00/0.29</td><td>213.34</td><td>176.03</td><td>182.30</td><td>239.13</td></tr><tr><td>400_25_270004</td><td>4.22/4.79</td><td>26.22/31.48</td><td>7.27/7.56</td><td>0.05/0.30</td><td>0.10/0.31</td><td>0.12/0.37</td><td>0.00/0.12</td><td>209.56</td><td>108.17</td><td>142.02</td><td>274.96</td></tr><tr><td>400_25_270005</td><td>1.45/2.41</td><td>24.04/28.34</td><td>6.75/7.54</td><td>0.00/0.12</td><td>0.06/0.30</td><td>0.06/0.20</td><td>0.00/0.18</td><td>243.63</td><td>192.24</td><td>215.43</td><td>295.26</td></tr><tr><td>400_50_270001</td><td>3.24/3.64</td><td>15.43/16.11</td><td>6.64/6.86</td><td>0.03/0.12</td><td>0.19/0.28</td><td>0.16/0.26</td><td>0.00/0.11</td><td>260.81</td><td>214.55</td><td>244.55</td><td>255.22</td></tr><tr><td>400_50_270002</td><td>2.82/3.15</td><td>15.47/15.97</td><td>6.31/6.73</td><td>0.03/0.27</td><td>0.26/0.47</td><td>0.17/0.38</td><td>0.00/0.21</td><td>284.52</td><td>228.68</td><td>229.22</td><td>260.60</td></tr><tr><td>400_50_270003</td><td>2.22/2.83</td><td>14.68/15.73</td><td>5.21/6.10</td><td>0.03/0.19</td><td>0.18/0.35</td><td>0.04/0.26</td><td>0.00/0.15</td><td>302.17</td><td>197.58</td><td>258.58</td><td>267.40</td></tr><tr><td>400_50_270004</td><td>1.91/2.36</td><td>15.64/16.56</td><td>6.14/6.60</td><td>0.06/0.19</td><td>0.00/0.27</td><td>0.00/0.19</td><td>0.02/0.44</td><td>265.09</td><td>228.35</td><td>230.35</td><td>294.04</td></tr><tr><td>400_50_270005</td><td>3.18/3.47</td><td>13.52/14.74</td><td>6.48/6.84</td><td>0.00/0.18</td><td>0.06/0.19</td><td>0.01/0.14</td><td>0.00/0.30</td><td>267.93</td><td>210.97</td><td>249.88</td><td>284.11</td></tr><tr><td>Average</td><td>1.32/1.74</td><td>8.37/10.15</td><td>3.19/3.94</td><td>0.01/0.28</td><td>0.20/1.53</td><td>0.19/0.33</td><td>0.00/0.20</td><td>97.82</td><td>66.18</td><td>75.77</td><td>120.48</td></tr></tbody></table>
<table><caption>Table 17
Comparison between FITS and MA on two sets of CCP instances (RanReal and DB).</caption><thead><tr><th rowspan="2">Name</th><th colspan="3">FITS</th><th colspan="3">MA</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub>(s)</th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub>(s)</th></tr></thead><tbody><tr><td>Sparse82_01</td><td>1342.17</td><td>1342.17</td><td>7.70</td><td>1342.17</td><td>1342.17</td><td>9.81</td></tr><tr><td>Sparse82_02</td><td>1306.64</td><td>1306.64</td><td>15.92</td><td>1306.64</td><td>1306.64</td><td>14.24</td></tr><tr><td>Sparse82_03</td><td>1353.94</td><td>1353.94</td><td>3.88</td><td>1353.94</td><td>1353.94</td><td>4.86</td></tr><tr><td>Sparse82_04</td><td>1291.22</td><td>1291.22</td><td>45.02</td><td>1291.22</td><td>1291.22</td><td>43.75</td></tr><tr><td>Sparse82_05</td><td>1352.35</td><td>1352.35</td><td>1.13</td><td>1352.35</td><td>1352.35</td><td>1.26</td></tr><tr><td>Sparse82_06</td><td>1354.61</td><td>1354.61</td><td>1.63</td><td>1354.61</td><td>1354.61</td><td>1.92</td></tr><tr><td>Sparse82_07</td><td>1266.94</td><td>1266.94</td><td>4.13</td><td>1266.94</td><td>1266.94</td><td>4.42</td></tr><tr><td>Sparse82_08</td><td>1393.02</td><td>1393.02</td><td>3.59</td><td>1393.02</td><td>1393.02</td><td>3.36</td></tr><tr><td>Sparse82_09</td><td>1294.12</td><td>1294.12</td><td>2.75</td><td>1294.12</td><td>1294.12</td><td>2.60</td></tr><tr><td>Sparse82_10</td><td>1356.98</td><td>1356.98</td><td>0.89</td><td>1356.98</td><td>1356.98</td><td>0.99</td></tr><tr><td>RanReal240_01</td><td>225003.53</td><td>224926.96</td><td>2348.59</td><td>225003.53</td><td>224937.30</td><td>2348.57</td></tr><tr><td>RanReal240_02</td><td>204624.36</td><td>204525.77</td><td>1580.11</td><td>204624.36</td><td>204553.10</td><td>1948.50</td></tr><tr><td>RanReal240_03</td><td>198976.88</td><td>198941.44</td><td>1572.29</td><td>199079.37</td><td>198956.17</td><td>2276.32</td></tr><tr><td>RanReal240_04</td><td>225667.77</td><td>225542.39</td><td>1151.94</td><td>225683.17</td><td>225547.69</td><td>2524.26</td></tr><tr><td>RanReal240_05</td><td>195621.68</td><td>195480.29</td><td>1631.35</td><td>195621.68</td><td>195481.00</td><td>1943.62</td></tr><tr><td>RanReal240_06</td><td>216747.32</td><td>216697.36</td><td>1667.33</td><td>216747.39</td><td>216699.09</td><td>1945.37</td></tr><tr><td>RanReal240_07</td><td>209316.85</td><td>209245.15</td><td>1562.66</td><td>209305.70</td><td>209213.53</td><td>1642.42</td></tr><tr><td>RanReal240_08</td><td>205246.82</td><td>205175.77</td><td>1768.87</td><td>205246.82</td><td>205134.15</td><td>2146.29</td></tr><tr><td>RanReal240_09</td><td>209186.90</td><td>209145.93</td><td>2038.81</td><td>209186.90</td><td>209152.19</td><td>2123.53</td></tr><tr><td>RanReal240_10</td><td>193062.60</td><td>192969.92</td><td>1856.91</td><td>193062.60</td><td>192972.14</td><td>1945.36</td></tr><tr><td>RanReal240_11</td><td>204722.75</td><td>204627.27</td><td>1975.32</td><td>204722.75</td><td>204635.30</td><td>1990.59</td></tr><tr><td>RanReal240_12</td><td>201117.11</td><td>201022.63</td><td>1197.68</td><td>201117.11</td><td>201037.08</td><td>2295.96</td></tr><tr><td>RanReal240_13</td><td>202338.43</td><td>202312.16</td><td>1218.02</td><td>202338.43</td><td>202312.50</td><td>1613.35</td></tr><tr><td>RanReal240_14</td><td>228870.89</td><td>228657.39</td><td>2027.09</td><td>228870.89</td><td>228601.66</td><td>1278.33</td></tr><tr><td>RanReal240_15</td><td>191263.28</td><td>191149.81</td><td>1653.79</td><td>191263.28</td><td>191177.81</td><td>2281.96</td></tr><tr><td>RanReal240_16</td><td>204072.57</td><td>203960.10</td><td>1710.90</td><td>204081.46</td><td>203971.34</td><td>1986.64</td></tr><tr><td>RanReal240_17</td><td>195623.04</td><td>195532.19</td><td>1791.09</td><td>195638.95</td><td>195544.67</td><td>2031.51</td></tr><tr><td>RanReal240_18</td><td>195127.57</td><td>195035.21</td><td>1887.10</td><td>195167.12</td><td>195070.91</td><td>2355.17</td></tr><tr><td>RanReal240_19</td><td>199307.33</td><td>199191.03</td><td>1317.83</td><td>199307.33</td><td>199175.59</td><td>1848.30</td></tr><tr><td>RanReal240_20</td><td>212321.06</td><td>212234.67</td><td>1798.98</td><td>212322.48</td><td>212236.65</td><td>2139.52</td></tr><tr><td>RanReal480_01</td><td>556259.42</td><td>555579.98</td><td>3785.15</td><td>556401.65</td><td>555586.79</td><td>5465.92</td></tr><tr><td>RanReal480_02</td><td>511504.92</td><td>510798.1</td><td>4735.30</td><td>511832.51</td><td>511033.52</td><td>5928.92</td></tr><tr><td>RanReal480_03</td><td>497973.87</td><td>497377.76</td><td>4213.93</td><td>498197.75</td><td>497467.34</td><td>6199.20</td></tr><tr><td>RanReal480_04</td><td>523131.64</td><td>522494.45</td><td>4786.27</td><td>523428.57</td><td>522493.58</td><td>6273.48</td></tr><tr><td>RanReal480_05</td><td>484701.85</td><td>483989.96</td><td>3463.80</td><td>484856.17</td><td>484089.84</td><td>5828.84</td></tr><tr><td>RanReal480_06</td><td>534897.14</td><td>534283.07</td><td>4402.99</td><td>535110.60</td><td>534324.91</td><td>5859.55</td></tr><tr><td>RanReal480_07</td><td>546052.12</td><td>545744.17</td><td>4340.06</td><td>546671.53</td><td>545774.12</td><td>5779.21</td></tr><tr><td>RanReal480_08</td><td>533042.97</td><td>532676.82</td><td>4098.46</td><td>533593.65</td><td>532710.69</td><td>5438.86</td></tr><tr><td>RanReal480_09</td><td>557169.08</td><td>556629.74</td><td>4028.24</td><td>557558.00</td><td>556641.92</td><td>5221.96</td></tr><tr><td>RanReal480_10</td><td>520714.86</td><td>519959.24</td><td>3871.66</td><td>520657.09</td><td>519841.12</td><td>5395.04</td></tr><tr><td>RanReal480_11</td><td>524479.86</td><td>524065.89</td><td>4859.36</td><td>524356.65</td><td>524044.88</td><td>5087.50</td></tr><tr><td>RanReal480_12</td><td>502547.16</td><td>502141.47</td><td>4282.61</td><td>502888.85</td><td>502143.97</td><td>5675.84</td></tr><tr><td>RanReal480_13</td><td>535381.87</td><td>535028.27</td><td>3833.55</td><td>536024.76</td><td>535078.71</td><td>5648.80</td></tr><tr><td>RanReal480_14</td><td>514731.74</td><td>514378.83</td><td>4568.84</td><td>515137.95</td><td>514415.58</td><td>5395.97</td></tr><tr><td>RanReal480_15</td><td>518140.43</td><td>517471.49</td><td>4449.48</td><td>518686.16</td><td>517480.73</td><td>5247.89</td></tr><tr><td>RanReal480_16</td><td>550260.76</td><td>549765.36</td><td>4074.76</td><td>550566.81</td><td>549796.27</td><td>5959.42</td></tr><tr><td>RanReal480_17</td><td>538339.63</td><td>537969.48</td><td>4540.85</td><td>538584.62</td><td>537997.22</td><td>5623.36</td></tr><tr><td>RanReal480_18</td><td>526419.74</td><td>525880.41</td><td>4768.13</td><td>527089.59</td><td>526065.80</td><td>5575.99</td></tr><tr><td>RanReal480_19</td><td>522972.89</td><td>522598.39</td><td>5210.14</td><td>523302.33</td><td>522624.73</td><td>5832.21</td></tr><tr><td>RanReal480_20</td><td>519148.25</td><td>518650.30</td><td>4097.54</td><td>519626.64</td><td>518717.70</td><td>6164.32</td></tr><tr><td>#Best</td><td>3</td><td>7</td><td></td><td>25</td><td>33</td><td></td></tr><tr><td>p-value</td><td>3.22e-5</td><td>3.94e-5</td><td></td><td></td><td></td><td></td></tr></tbody></table>
<caption>Table 18</caption>

Comparison between FITS and MA on the large handover minimization instances with $n \ge 100$. For direct comparisons, we present the results in the minimization form.

<table><thead><tr><th rowspan="2">Name</th><th colspan="3">FITS</th><th colspan="3">MA</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub>(s)</th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub>(s)</th></tr></thead><tbody><tr><td>100_15_270001</td><td>19000</td><td>19000.00</td><td>7.59</td><td>19000</td><td>19000.00</td><td>4.52</td></tr><tr><td>100_15_270002</td><td>22686</td><td>22686.00</td><td>143.84</td><td>22686</td><td>22686.00</td><td>70.77</td></tr><tr><td>100_15_270003</td><td>14558</td><td>14558.00</td><td>0.20</td><td>14558</td><td>14558.00</td><td>0.08</td></tr><tr><td>100_15_270004</td><td>19700</td><td>19700.00</td><td>3.34</td><td>19700</td><td>19700.00</td><td>0.84</td></tr><tr><td>100_15_270005</td><td>22746</td><td>22746.00</td><td>15.68</td><td>22746</td><td>22746.00</td><td>4.78</td></tr><tr><td>100_25_270001</td><td>36412</td><td>36412.00</td><td>5.73</td><td>36412</td><td>36412.00</td><td>2.53</td></tr><tr><td>100_25_270002</td><td>38608</td><td>38608.00</td><td>72.92</td><td>38608</td><td>38608.00</td><td>11.48</td></tr><tr><td>100_25_270003</td><td>32686</td><td>32686.00</td><td>84.02</td><td>32686</td><td>32686.00</td><td>28.65</td></tr><tr><td>100_25_270004</td><td>35322</td><td>35322.00</td><td>20.94</td><td>35322</td><td>35322.00</td><td>10.55</td></tr><tr><td>100_25_270005</td><td>36690</td><td>36690.00</td><td>9.81</td><td>36690</td><td>36690.00</td><td>6.19</td></tr><tr><td>100_50_270001</td><td>60922</td><td>60922.00</td><td>103.80</td><td>60922</td><td>60922.00</td><td>21.03</td></tr><tr><td>100_50_270002</td><td>62022</td><td>62022.00</td><td>42.17</td><td>62022</td><td>62022.00</td><td>8.20</td></tr><tr><td>100_50_270003</td><td>54596</td><td>54596.00</td><td>94.73</td><td>54596</td><td>54596.00</td><td>4.43</td></tr><tr><td>100_50_270004</td><td>57894</td><td>57894.00</td><td>121.33</td><td>57894</td><td>57894.00</td><td>55.42</td></tr><tr><td>100_50_270005</td><td>61080</td><td>61099.90</td><td>620.30</td><td>61080</td><td><strong>61080.00</strong></td><td>158.34</td></tr><tr><td>200_15_270001</td><td>81558</td><td>81558.00</td><td>544.44</td><td>81558</td><td>81558.00</td><td>348.50</td></tr><tr><td>200_15_270002</td><td>89492</td><td>90134.50</td><td>966.93</td><td>89492</td><td><strong>89653.40</strong></td><td>628.38</td></tr><tr><td>200_15_270003</td><td>79232</td><td>79232.00</td><td>165.95</td><td>79232</td><td>79232.00</td><td>56.59</td></tr><tr><td>200_15_270004</td><td>78324</td><td>78372.30</td><td>345.14</td><td>78324</td><td><strong>78324.00</strong></td><td>344.47</td></tr><tr><td>200_15_270005</td><td>95680</td><td>96023.90</td><td>398.99</td><td>95680</td><td><strong>95680.00</strong></td><td>115.01</td></tr><tr><td>200_25_270001</td><td>133168</td><td>133168.00</td><td>512.23</td><td>133168</td><td>133168.00</td><td>206.01</td></tr><tr><td>200_25_270002</td><td>133778</td><td><strong>133818.20</strong></td><td>742.93</td><td>133778</td><td>133829.00</td><td>686.27</td></tr><tr><td>200_25_270003</td><td>136782</td><td>136828.10</td><td>885.09</td><td>136782</td><td><strong>136796.70</strong></td><td>870.38</td></tr><tr><td>200_25_270004</td><td>128246</td><td>128246.00</td><td>1341.78</td><td>128246</td><td>128246.00</td><td>767.18</td></tr><tr><td>200_25_270005</td><td>147844</td><td>147844.00</td><td>132.42</td><td>147844</td><td>147844.00</td><td>189.92</td></tr><tr><td>200_50_270001</td><td>215388</td><td><strong>215560.80</strong></td><td>962.60</td><td>215388</td><td>215616.40</td><td>802.60</td></tr><tr><td>200_50_270002</td><td>212798</td><td><strong>212848.70</strong></td><td>731.01</td><td>212798</td><td>212858.40</td><td>1055.20</td></tr><tr><td>200_50_270003</td><td>214364</td><td>214555.20</td><td>1237.59</td><td>214364</td><td><strong>214550.10</strong></td><td>1333.02</td></tr><tr><td>200_50_270004</td><td>206476</td><td><strong>206574.40</strong></td><td>1097.72</td><td>206476</td><td>206595.90</td><td>797.46</td></tr><tr><td>200_50_270005</td><td>229900</td><td><strong>229936.70</strong></td><td>757.27</td><td>229900</td><td>229945.20</td><td>1044.29</td></tr><tr><td>400_15_270001</td><td>369048</td><td>371437.90</td><td>1659.67</td><td>369048</td><td><strong>369317.60</strong></td><td>1904.87</td></tr><tr><td>400_15_270002</td><td>365878</td><td>368928.70</td><td>2880.39</td><td>365878</td><td><strong>366497.10</strong></td><td>1558.38</td></tr><tr><td>400_15_270003</td><td>352588</td><td>353787.40</td><td>1394.43</td><td>352588</td><td><strong>352600.70</strong></td><td>1101.44</td></tr><tr><td>400_15_270004</td><td>331888</td><td>336731.60</td><td>1517.02</td><td>331888</td><td><strong>332017.50</strong></td><td>1631.73</td></tr><tr><td>400_15_270005</td><td>360422</td><td>361852.50</td><td>2456.41</td><td>360422</td><td><strong>360949.90</strong></td><td>2080.04</td></tr><tr><td>400_25_270001</td><td>545556</td><td>546421.40</td><td>2447.34</td><td><strong>545540</strong></td><td><strong>546420.60</strong></td><td>2447.35</td></tr><tr><td>400_25_270002</td><td>528470</td><td><strong>528792.60</strong></td><td>2686.55</td><td>528470</td><td>528862.50</td><td>2615.13</td></tr><tr><td>400_25_270003</td><td>524678</td><td>525339.10</td><td>2455.44</td><td>524678</td><td><strong>525226.00</strong></td><td>2204.49</td></tr><tr><td>400_25_270004</td><td>481436</td><td><strong>481925.10</strong></td><td>2715.72</td><td>481436</td><td>481974.50</td><td>2351.65</td></tr><tr><td>400_25_270005</td><td>548100</td><td><strong>548123.60</strong></td><td>2104.69</td><td>548100</td><td>548199.70</td><td>1808.02</td></tr><tr><td>400_50_270001</td><td>824604</td><td>825539.90</td><td>2749.00</td><td><strong>824518</strong></td><td><strong>825488.10</strong></td><td>3086.45</td></tr><tr><td>400_50_270002</td><td>822336</td><td>823753.30</td><td>3002.52</td><td>822336</td><td><strong>823699.90</strong></td><td>3006.55</td></tr><tr><td>400_50_270003</td><td>801432</td><td>802627.00</td><td>2814.66</td><td><strong>801346</strong></td><td><strong>802484.30</strong></td><td>3022.16</td></tr><tr><td>400_50_270004</td><td>760232</td><td>762474.40</td><td>3003.92</td><td>760232</td><td><strong>761699.40</strong></td><td>2924.69</td></tr><tr><td>400_50_270005</td><td>828398</td><td>829700.80</td><td>2739.78</td><td>828398</td><td><strong>829226.00</strong></td><td>3801.92</td></tr></tbody><tfoot><tr><td>#Best</td><td>0</td><td>8</td><td></td><td><strong>3</strong></td><td><strong>19</strong></td><td></td></tr><tr><td>p-value</td><td>0.08</td><td>0.05</td><td></td><td></td><td></td><td></td></tr></tfoot></table>
<table><caption>Table 19
Comparison between FITS and its two underlying components FLS and InfLS on the RanReal benchmark set.</caption><thead><tr><th rowspan="2">Name</th><th colspan="2">FITS</th><th colspan="2">FLS</th><th colspan="2">InfLS</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th></tr></thead><tbody><tr><td>RanReal240_01</td><td>224941.48</td><td>224802.06</td><td>224941.28</td><td>224700.99</td><td>224673.38</td><td>224351.31</td></tr><tr><td>RanReal240_02</td><td>204624.36</td><td>204359.38</td><td>204624.36</td><td>204273.94</td><td>204191.72</td><td>203800.45</td></tr><tr><td>RanReal240_03</td><td>198954.91</td><td>198799.84</td><td>198896.78</td><td>198715.24</td><td>198612.31</td><td>198358.12</td></tr><tr><td>RanReal240_04</td><td>225627.16</td><td>225364.97</td><td>225627.16</td><td>225242.26</td><td>225382.26</td><td>224953.72</td></tr><tr><td>RanReal240_05</td><td>195564.48</td><td>195320.28</td><td>195472.49</td><td>195298.72</td><td>195165.72</td><td>194470.36</td></tr><tr><td>RanReal240_06</td><td>216747.32</td><td>216487.02</td><td>216736.00</td><td>216422.13</td><td>216244.78</td><td>215840.77</td></tr><tr><td>RanReal240_07</td><td>209305.70</td><td>209029.23</td><td>209286.63</td><td>208984.08</td><td>208904.93</td><td>208538.21</td></tr><tr><td>RanReal240_08</td><td>205246.82</td><td>204961.05</td><td>205246.82</td><td>204971.43</td><td>204867.72</td><td>204447.79</td></tr><tr><td>RanReal240_09</td><td>209159.16</td><td>208952.48</td><td>209073.60</td><td>208877.53</td><td>208782.77</td><td>208445.36</td></tr><tr><td>RanReal240_10</td><td>192986.21</td><td>192811.13</td><td>193044.16</td><td>192762.94</td><td>192765.27</td><td>192429.05</td></tr><tr><td>RanReal240_11</td><td>204722.75</td><td>204559.39</td><td>204722.75</td><td>204491.34</td><td>204458.26</td><td>204014.37</td></tr><tr><td>RanReal240_12</td><td>201117.11</td><td>200797.67</td><td>201074.54</td><td>200874.41</td><td>200687.09</td><td>200360.62</td></tr><tr><td>RanReal240_13</td><td>202335.99</td><td>202139.57</td><td>202335.99</td><td>202107.26</td><td>201879.46</td><td>201616.58</td></tr><tr><td>RanReal240_14</td><td>228870.89</td><td>228554.78</td><td>228844.44</td><td>228457.67</td><td>228316.81</td><td>227946.95</td></tr><tr><td>RanReal240_15</td><td>191255.87</td><td>190923.28</td><td>191202.77</td><td>190903.62</td><td>190761.09</td><td>190372.67</td></tr><tr><td>RanReal240_16</td><td>204054.99</td><td>203710.39</td><td>204019.08</td><td>203706.22</td><td>203513.73</td><td>203196.32</td></tr><tr><td>RanReal240_17</td><td>195561.36</td><td>195243.32</td><td>195447.87</td><td>195225.20</td><td>195223.74</td><td>194857.78</td></tr><tr><td>RanReal240_18</td><td>195100.39</td><td>194872.13</td><td>195100.39</td><td>194864.12</td><td>194689.78</td><td>194398.32</td></tr><tr><td>RanReal240_19</td><td>199225.98</td><td>199040.43</td><td>199216.94</td><td>198997.54</td><td>199006.08</td><td>198450.68</td></tr><tr><td>RanReal240_20</td><td>212268.52</td><td>212049.85</td><td>212268.52</td><td>212015.41</td><td>211849.93</td><td>211537.55</td></tr><tr><td>RanReal480_01</td><td>555489.92</td><td>554376.54</td><td>555300.10</td><td>554228.16</td><td>552864.61</td><td>551299.72</td></tr><tr><td>RanReal480_02</td><td>511280.50</td><td>509757.15</td><td>510466.38</td><td>509449.52</td><td>509294.32</td><td>508336.14</td></tr><tr><td>RanReal480_03</td><td>497295.19</td><td>496059.50</td><td>496683.63</td><td>495938.74</td><td>495664.06</td><td>494292.73</td></tr><tr><td>RanReal480_04</td><td>522305.16</td><td>521062.13</td><td>522000.18</td><td>520565.30</td><td>520451.39</td><td>519325.61</td></tr><tr><td>RanReal480_05</td><td>484084.66</td><td>482867.74</td><td>483514.31</td><td>482241.30</td><td>481725.02</td><td>480777.24</td></tr><tr><td>RanReal480_06</td><td>533991.27</td><td>533036.36</td><td>533843.95</td><td>532409.06</td><td>531163.12</td><td>530249.35</td></tr><tr><td>RanReal480_07</td><td>545470.73</td><td>544651.12</td><td>545209.27</td><td>544128.41</td><td>542724.00</td><td>541454.69</td></tr><tr><td>RanReal480_08</td><td>532417.42</td><td>531667.91</td><td>532357.71</td><td>531527.82</td><td>529288.64</td><td>528038.04</td></tr><tr><td>RanReal480_09</td><td>556868.85</td><td>555634.40</td><td>556552.85</td><td>555295.47</td><td>554085.91</td><td>553165.52</td></tr><tr><td>RanReal480_10</td><td>520257.54</td><td>518071.71</td><td>519857.07</td><td>518083.48</td><td>517835.50</td><td>516098.53</td></tr><tr><td>RanReal480_11</td><td>523991.29</td><td>522816.94</td><td>523587.47</td><td>522613.58</td><td>521964.67</td><td>520488.83</td></tr><tr><td>RanReal480_12</td><td>501915.56</td><td>500776.79</td><td>501683.69</td><td>500647.73</td><td>500922.44</td><td>499723.69</td></tr><tr><td>RanReal480_13</td><td>535025.51</td><td>533823.79</td><td>534867.67</td><td>533594.29</td><td>531960.39</td><td>530949.44</td></tr><tr><td>RanReal480_14</td><td>514107.62</td><td>513053.25</td><td>514039.43</td><td>512915.41</td><td>512043.79</td><td>510844.33</td></tr><tr><td>RanReal480_15</td><td>517205.02</td><td>516018.38</td><td>518140.43</td><td>515941.80</td><td>514508.48</td><td>513428.89</td></tr><tr><td>RanReal480_16</td><td>549552.63</td><td>548462.13</td><td>549824.00</td><td>548211.77</td><td>547509.72</td><td>546087.39</td></tr><tr><td>RanReal480_17</td><td>537924.55</td><td>536745.39</td><td>537702.09</td><td>536639.04</td><td>534980.65</td><td>533909.81</td></tr><tr><td>RanReal480_18</td><td>525822.76</td><td>524712.42</td><td>525926.74</td><td>524565.69</td><td>523702.51</td><td>522359.71</td></tr><tr><td>RanReal480_19</td><td>522316.22</td><td>521267.22</td><td>522291.27</td><td>520957.84</td><td>520173.80</td><td>519077.31</td></tr><tr><td>RanReal480_20</td><td>518349.10</td><td>517430.77</td><td>518645.84</td><td>517467.88</td><td>515626.91</td><td>515025.41</td></tr><tr><td>#Best</td><td>35</td><td>36</td><td>12</td><td>4</td><td>0</td><td>0</td></tr><tr><td>p-value</td><td></td><td></td><td>6.23e-5</td><td>4.20e-7</td><td>2.54e-10</td><td>2.54e-10</td></tr></tbody></table>
<table><caption>Table 20
Comparison between FITS and its variation FITS_FI (using the first-improvement strategy) on the RanReal benchmark.</caption><thead><tr><th rowspan="2">Name</th><th colspan="3">FITS</th><th colspan="3">FITS_FI</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub></th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub></th></tr></thead><tbody><tr><td>RanReal240.01</td><td>224941.48</td><td>224802.06</td><td>149.09</td><td>224182.68</td><td>223791.06</td><td>97.10</td></tr><tr><td>RanReal240.02</td><td>204624.36</td><td>204359.38</td><td>150.75</td><td>204024.55</td><td>203748.76</td><td>115.86</td></tr><tr><td>RanReal240.03</td><td>198954.91</td><td>198799.84</td><td>169.95</td><td>198312.80</td><td>198070.31</td><td>107.81</td></tr><tr><td>RanReal240.04</td><td>225627.16</td><td>225364.97</td><td>118.58</td><td>224995.76</td><td>224412.34</td><td>116.39</td></tr><tr><td>RanReal240.05</td><td>195564.48</td><td>195320.28</td><td>132.33</td><td>195102.26</td><td>194867.72</td><td>117.86</td></tr><tr><td>RanReal240.06</td><td>216747.32</td><td>216487.02</td><td>155.99</td><td>215788.46</td><td>215440.78</td><td>99.28</td></tr><tr><td>RanReal240.07</td><td>209305.70</td><td>209029.23</td><td>144.96</td><td>208530.22</td><td>208114.22</td><td>96.03</td></tr><tr><td>RanReal240.08</td><td>205246.82</td><td>204961.05</td><td>124.22</td><td>204428.30</td><td>204277.73</td><td>108.99</td></tr><tr><td>RanReal240.09</td><td>209159.16</td><td>208952.48</td><td>141.69</td><td>208338.57</td><td>208175.46</td><td>116.96</td></tr><tr><td>RanReal240.10</td><td>192986.21</td><td>192811.13</td><td>134.20</td><td>192232.44</td><td>192071.19</td><td>120.39</td></tr><tr><td>RanReal240.11</td><td>204722.75</td><td>204559.39</td><td>129.91</td><td>204217.59</td><td>204001.29</td><td>89.54</td></tr><tr><td>RanReal240.12</td><td>201117.11</td><td>200797.67</td><td>132.03</td><td>200498.08</td><td>200344.22</td><td>78.75</td></tr><tr><td>RanReal240.13</td><td>202335.99</td><td>202139.57</td><td>131.34</td><td>201813.49</td><td>201615.62</td><td>69.13</td></tr><tr><td>RanReal240.14</td><td>228870.89</td><td>228554.78</td><td>135.87</td><td>228231.53</td><td>228117.87</td><td>92.49</td></tr><tr><td>RanReal240.15</td><td>191255.87</td><td>190923.28</td><td>131.83</td><td>190537.12</td><td>190180.38</td><td>81.39</td></tr><tr><td>RanReal240.16</td><td>204054.99</td><td>203710.39</td><td>89.11</td><td>203428.14</td><td>203258.65</td><td>100.98</td></tr><tr><td>RanReal240.17</td><td>195561.36</td><td>195243.32</td><td>171.03</td><td>194568.09</td><td>194356.29</td><td>64.85</td></tr><tr><td>RanReal240.18</td><td>195100.39</td><td>194872.13</td><td>152.83</td><td>194458.12</td><td>194254.79</td><td>89.27</td></tr><tr><td>RanReal240.19</td><td>199225.98</td><td>199040.43</td><td>98.09</td><td>198479.56</td><td>198337.34</td><td>102.39</td></tr><tr><td>RanReal240.20</td><td>212268.52</td><td>212049.85</td><td>115.38</td><td>211474.47</td><td>211194.85</td><td>66.20</td></tr><tr><td>RanReal480.01</td><td>555489.92</td><td>554376.54</td><td>340.60</td><td>551254.15</td><td>550147.26</td><td>236.79</td></tr><tr><td>RanReal480.02</td><td>511280.50</td><td>509757.15</td><td>355.59</td><td>507215.91</td><td>506193.99</td><td>251.43</td></tr><tr><td>RanReal480.03</td><td>497295.19</td><td>496059.50</td><td>352.06</td><td>494017.02</td><td>493425.88</td><td>251.20</td></tr><tr><td>RanReal480.04</td><td>522305.16</td><td>521062.13</td><td>399.51</td><td>516643.64</td><td>515925.45</td><td>112.97</td></tr><tr><td>RanReal480.05</td><td>484084.66</td><td>482867.74</td><td>335.84</td><td>480982.54</td><td>480210.46</td><td>240.39</td></tr><tr><td>RanReal480.06</td><td>533991.27</td><td>533036.36</td><td>390.06</td><td>530142.87</td><td>529021.63</td><td>230.79</td></tr><tr><td>RanReal480.07</td><td>545470.73</td><td>544651.12</td><td>390.23</td><td>541115.04</td><td>539994.76</td><td>258.65</td></tr><tr><td>RanReal480.08</td><td>532417.42</td><td>531667.91</td><td>380.64</td><td>529566.14</td><td>527736.78</td><td>223.86</td></tr><tr><td>RanReal480.09</td><td>556868.85</td><td>555634.40</td><td>383.67</td><td>551863.24</td><td>551045.16</td><td>204.35</td></tr><tr><td>RanReal480.10</td><td>520257.54</td><td>518071.71</td><td>328.85</td><td>517484.26</td><td>515898.39</td><td>272.95</td></tr><tr><td>RanReal480.11</td><td>523991.29</td><td>522816.94</td><td>383.65</td><td>520367.63</td><td>519570.84</td><td>204.96</td></tr><tr><td>RanReal480.12</td><td>501915.56</td><td>500776.79</td><td>347.32</td><td>498568.75</td><td>498030.75</td><td>227.79</td></tr><tr><td>RanReal480.13</td><td>535025.51</td><td>533823.79</td><td>330.84</td><td>530707.31</td><td>529726.48</td><td>147.77</td></tr><tr><td>RanReal480.14</td><td>514107.62</td><td>513053.25</td><td>352.07</td><td>510789.76</td><td>509613.70</td><td>252.60</td></tr><tr><td>RanReal480.15</td><td>517205.02</td><td>516018.38</td><td>387.02</td><td>514108.83</td><td>513515.25</td><td>195.55</td></tr><tr><td>RanReal480.16</td><td>549552.63</td><td>548462.13</td><td>392.78</td><td>543160.92</td><td>542154.24</td><td>252.46</td></tr><tr><td>RanReal480.17</td><td>537924.55</td><td>536745.39</td><td>360.93</td><td>533616.73</td><td>532759.09</td><td>254.00</td></tr><tr><td>RanReal480.18</td><td>525822.76</td><td>524712.42</td><td>320.60</td><td>521450.47</td><td>520006.79</td><td>108.58</td></tr><tr><td>RanReal480.19</td><td>522316.22</td><td>521267.22</td><td>380.69</td><td>518719.33</td><td>517865.80</td><td>214.04</td></tr><tr><td>RanReal480.20</td><td>518349.10</td><td>517430.77</td><td>353.52</td><td>514528.29</td><td>514097.85</td><td>224.97</td></tr><tr><td>#Best</td><td>40</td><td>40</td><td></td><td>0</td><td>0</td><td></td></tr><tr><td>p-value</td><td></td><td></td><td></td><td>2.54e-10</td><td>2.54e-10</td><td></td></tr></tbody></table>
<caption>Table 21</caption>

Comparison of two MA versions using uniform and cluster-based crossover respectively on the RanReal benchmark.

<table><thead><tr><th rowspan="2">Name</th><th colspan="3">Uniform CX</th><th colspan="3">Cluster-based CX</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub>(s)</th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg</sub>(s)</th></tr></thead><tbody><tr><td>RanReal240.01</td><td>224921.21</td><td>224821.36</td><td>1295.14</td><td>225003.53</td><td>224937.30</td><td>2348.57</td></tr><tr><td>RanReal240.02</td><td>204624.36</td><td>204493.54</td><td>1952.30</td><td>204624.36</td><td>204553.10</td><td>1948.50</td></tr><tr><td>RanReal240.03</td><td>198981.64</td><td>198893.17</td><td>1943.37</td><td>199079.37</td><td>198956.17</td><td>2276.32</td></tr><tr><td>RanReal240.04</td><td>225566.15</td><td>225454.43</td><td>1480.25</td><td>225683.17</td><td>225547.69</td><td>2524.26</td></tr><tr><td>RanReal240.05</td><td>195533.32</td><td>195428.43</td><td>1598.60</td><td>195621.68</td><td>195481.00</td><td>1943.62</td></tr><tr><td>RanReal240.06</td><td>216747.32</td><td>216618.54</td><td>1889.24</td><td>216747.39</td><td>216699.09</td><td>1945.37</td></tr><tr><td>RanReal240.07</td><td>209288.75</td><td>209194.38</td><td>1710.89</td><td>209305.70</td><td>209213.53</td><td>1642.42</td></tr><tr><td>RanReal240.08</td><td>205246.82</td><td>205108.07</td><td>1645.73</td><td>205246.82</td><td>205134.15</td><td>2146.29</td></tr><tr><td>RanReal240.09</td><td>209186.90</td><td>209094.98</td><td>1974.60</td><td>209186.90</td><td>209152.19</td><td>2123.53</td></tr><tr><td>RanReal240.10</td><td>192986.21</td><td>192903.33</td><td>2459.53</td><td>193062.60</td><td>192972.14</td><td>1945.36</td></tr><tr><td>RanReal240.11</td><td>204680.80</td><td>204587.50</td><td>1672.03</td><td>204722.75</td><td>204635.30</td><td>1990.59</td></tr><tr><td>RanReal240.12</td><td>201117.11</td><td>200944.04</td><td>1924.83</td><td>201117.11</td><td>201037.08</td><td>2295.96</td></tr><tr><td>RanReal240.13</td><td>202338.43</td><td>202281.95</td><td>1813.21</td><td>202338.43</td><td>202312.50</td><td>1613.35</td></tr><tr><td>RanReal240.14</td><td>228646.52</td><td>228555.05</td><td>1560.60</td><td>228870.89</td><td>228601.66</td><td>1278.33</td></tr><tr><td>RanReal240.15</td><td>191230.33</td><td>191094.96</td><td>1835.09</td><td>191263.28</td><td>191177.81</td><td>2281.96</td></tr><tr><td>RanReal240.16</td><td>203909.40</td><td>203808.95</td><td>1537.05</td><td>204081.46</td><td>203971.34</td><td>1986.64</td></tr><tr><td>RanReal240.17</td><td>195638.95</td><td>195464.27</td><td>1929.86</td><td>195638.95</td><td>195544.67</td><td>2031.51</td></tr><tr><td>RanReal240.18</td><td>195100.39</td><td>194968.12</td><td>1876.05</td><td>195167.12</td><td>195070.91</td><td>2355.17</td></tr><tr><td>RanReal240.19</td><td>199307.33</td><td>199162.91</td><td>1660.33</td><td>199307.33</td><td>199175.59</td><td>1848.30</td></tr><tr><td>RanReal240.20</td><td>212268.52</td><td>212159.63</td><td>1373.99</td><td>212322.48</td><td>212236.65</td><td>2139.52</td></tr><tr><td>RanReal480.01</td><td>555377.78</td><td>554896.75</td><td>3868.70</td><td>556401.65</td><td>555586.79</td><td>5465.92</td></tr><tr><td>RanReal480.02</td><td>511021.69</td><td>510398.02</td><td>4410.56</td><td>511832.51</td><td>511033.52</td><td>5928.92</td></tr><tr><td>RanReal480.03</td><td>497675.92</td><td>496992.13</td><td>4234.89</td><td>498197.75</td><td>497467.34</td><td>6199.20</td></tr><tr><td>RanReal480.04</td><td>522425.81</td><td>521851.94</td><td>3692.03</td><td>523428.57</td><td>522493.58</td><td>6273.48</td></tr><tr><td>RanReal480.05</td><td>484496.11</td><td>483529.47</td><td>3896.52</td><td>484856.17</td><td>484089.84</td><td>5828.84</td></tr><tr><td>RanReal480.06</td><td>534140.09</td><td>533526.58</td><td>4560.41</td><td>535110.60</td><td>534324.91</td><td>5859.55</td></tr><tr><td>RanReal480.07</td><td>545781.35</td><td>545111.15</td><td>4012.66</td><td>546671.53</td><td>545774.12</td><td>5779.21</td></tr><tr><td>RanReal480.08</td><td>532566.57</td><td>532224.38</td><td>3723.32</td><td>533593.65</td><td>532710.69</td><td>5438.86</td></tr><tr><td>RanReal480.09</td><td>556523.87</td><td>556084.63</td><td>4458.78</td><td>557558.00</td><td>556641.92</td><td>5221.96</td></tr><tr><td>RanReal480.10</td><td>520148.06</td><td>519300.68</td><td>4485.14</td><td>520657.09</td><td>519841.12</td><td>5395.04</td></tr><tr><td>RanReal480.11</td><td>524676.35</td><td>523771.15</td><td>3951.08</td><td>524356.65</td><td>524044.88</td><td>5087.50</td></tr><tr><td>RanReal480.12</td><td>502329.51</td><td>501725.88</td><td>4251.32</td><td>502888.85</td><td>502143.97</td><td>5675.84</td></tr><tr><td>RanReal480.13</td><td>535017.14</td><td>534562.12</td><td>4163.93</td><td>536024.76</td><td>535078.71</td><td>5648.80</td></tr><tr><td>RanReal480.14</td><td>514814.34</td><td>514085.50</td><td>4657.32</td><td>515137.95</td><td>514415.58</td><td>5395.97</td></tr><tr><td>RanReal480.15</td><td>517835.64</td><td>517051.95</td><td>4075.11</td><td>518686.16</td><td>517480.73</td><td>5247.89</td></tr><tr><td>RanReal480.16</td><td>550021.73</td><td>549159.13</td><td>3883.47</td><td>550566.81</td><td>549796.27</td><td>5959.42</td></tr><tr><td>RanReal480.17</td><td>538667.77</td><td>537830.76</td><td>3244.27</td><td>538584.62</td><td>537997.22</td><td>5623.36</td></tr><tr><td>RanReal480.18</td><td>526142.15</td><td>525543.15</td><td>4510.03</td><td>527089.59</td><td>526065.80</td><td>5575.99</td></tr><tr><td>RanReal480.19</td><td>522705.19</td><td>521971.51</td><td>3469.05</td><td>523302.33</td><td>522624.73</td><td>5832.21</td></tr><tr><td>RanReal480.20</td><td>518857.89</td><td>518260.21</td><td>3271.27</td><td>519626.64</td><td>518717.70</td><td>6164.32</td></tr><tr><td>#Best</td><td>2</td><td>0</td><td></td><td>31</td><td>40</td><td></td></tr><tr><td>p-value</td><td>4.46e-7</td><td>2.54e-10</td><td></td><td></td><td></td><td></td></tr></tbody></table>
<caption>Table 22</caption>

Computational results on small handover minimization instances. For direct comparison, the results are converted into the minimization form.

<table><thead><tr><th rowspan="2">Name</th><th colspan="3">FITS</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>t<sub>avg(s)</sub></th></tr></thead><tbody><tr><td>20.5.270001</td><td>540</td><td>540.00</td><td>0.00</td></tr><tr><td>20.5.270002</td><td>54</td><td>54.00</td><td>0.00</td></tr><tr><td>20.5.270003</td><td>816</td><td>816.00</td><td>0.00</td></tr><tr><td>20.5.270004</td><td>126</td><td>126.00</td><td>0.00</td></tr><tr><td>20.5.270005</td><td>372</td><td>372.00</td><td>0.00</td></tr><tr><td>20.10.270001</td><td>2148</td><td>2148.00</td><td>0.00</td></tr><tr><td>20.10.270002</td><td>1426</td><td>1426.00</td><td>0.00</td></tr><tr><td>20.10.270003</td><td>2458</td><td>2458.00</td><td>0.00</td></tr><tr><td>20.10.270004</td><td>1570</td><td>1570.00</td><td>0.00</td></tr><tr><td>30.5.270001</td><td>772</td><td>772.00</td><td>0.00</td></tr><tr><td>30.5.270002</td><td>136</td><td>136.00</td><td>0.00</td></tr><tr><td>30.5.270003</td><td>920</td><td>920.00</td><td>0.01</td></tr><tr><td>30.5.270004</td><td>52</td><td>52.00</td><td>0.00</td></tr><tr><td>30.5.270005</td><td>410</td><td>410.00</td><td>0.01</td></tr><tr><td>30.10.270001</td><td>3276</td><td>3276.00</td><td>0.00</td></tr><tr><td>30.10.270002</td><td>1404</td><td>1404.00</td><td>0.00</td></tr><tr><td>30.10.270003</td><td>2214</td><td>2214.00</td><td>0.00</td></tr><tr><td>30.10.270004</td><td>2150</td><td>2150.00</td><td>0.02</td></tr><tr><td>30.10.270005</td><td>2540</td><td>2540.00</td><td>0.04</td></tr><tr><td>30.15.270001</td><td>6178</td><td>6178.00</td><td>0.01</td></tr><tr><td>30.15.270002</td><td>4042</td><td>4042.00</td><td>0.00</td></tr><tr><td>30.15.270003</td><td>4126</td><td>4126.00</td><td>0.00</td></tr><tr><td>30.15.270004</td><td>3920</td><td>3920.00</td><td>0.01</td></tr><tr><td>40.5.270001</td><td>610</td><td>610.00</td><td>0.07</td></tr><tr><td>40.5.270002</td><td>136</td><td>136.00</td><td>0.05</td></tr><tr><td>40.5.270003</td><td>234</td><td>234.00</td><td>0.12</td></tr><tr><td>40.5.270004</td><td>232</td><td>232.00</td><td>1.30</td></tr><tr><td>40.5.270005</td><td>774</td><td>774.00</td><td>0.00</td></tr><tr><td>40.10.270001</td><td>4544</td><td>4544.00</td><td>0.08</td></tr><tr><td>40.10.270002</td><td>2068</td><td>2068.00</td><td>0.00</td></tr><tr><td>40.10.270003</td><td>2090</td><td>2090.00</td><td>0.01</td></tr><tr><td>40.10.270004</td><td>1650</td><td>1650.00</td><td>0.00</td></tr><tr><td>40.10.270005</td><td>4316</td><td>4316.00</td><td>0.01</td></tr><tr><td>40.15.270001</td><td>8646</td><td>8646.00</td><td>0.24</td></tr><tr><td>40.15.270002</td><td>4586</td><td>4586.00</td><td>0.26</td></tr><tr><td>40.15.270003</td><td>5396</td><td>5396.00</td><td>0.02</td></tr><tr><td>40.15.270004</td><td>4800</td><td>4800.00</td><td>0.00</td></tr><tr><td>40.15.270005</td><td>6272</td><td>6272.00</td><td>0.05</td></tr></tbody></table>