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

HAL
open science

# A hybrid metaheuristic approach for the capacitated arc routing problem

Yuning Chen, Jin-Kao Hao, Fred Glover

► To cite this version:

Yuning Chen, Jin-Kao Hao, Fred Glover. A hybrid metaheuristic approach for the capacitated arc routing problem. European Journal of Operational Research, 2016, 253 (1), pp.25-39. 10.1016/j.ejor.2016.02.015. hal-01412524

HAL Id: hal-01412524

https://hal.science/hal-01412524

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
# A Hybrid Metaheuristic Approach for the Capacitated Arc Routing Problem

Yuning Chen<sup>a</sup>, Jin-Kao Hao<sup>a,b,*</sup>, Fred Glover<sup>c</sup>

<sup>a</sup>LERIA, Université d'Angers, 2 Bd Lavoisier, 49045 Angers, Cedex 01, France

<sup>b</sup>Institut Universitaire de France, Paris, France

<sup>c</sup>OptTek Systems, Inc., 2241 17th Street Boulder, Colorado 80302, USA

## Abstract

The capacitated arc routing problem (CARP) is a difficult combinatorial optimization problem that has been intensively studied in the last decades. We present a hybrid metaheuristic approach (HMA) to solve this problem which incorporates an effective local refinement procedure, coupling a randomized tabu thresholding procedure with an infeasible descent procedure, into the memetic framework. Other distinguished features of HMA include a specially designed route-based crossover operator for solution recombination and a distance-and-quality based replacement criterion for pool updating. Extensive experimental studies show that HMA is highly scalable and is able to quickly identify either the best known results or improved best known results for almost all currently available CARP benchmark instances. In particular, it discovers an improved best known result for 15 benchmark instances (6 classical instances and 9 large-sized instances all with unknown optima). Furthermore, we analyze some key elements and properties of the HMA-CARP algorithm to better understand its behavior.

*Keywords:* Capacitated arc routing problem; Memetic search; Tabu thresholding.

## 1 Introduction

The capacitated arc routing problem (CARP) has been the subject of a large number of studies during the last decades due to its wide applicability in logis-

<footnote>* Corresponding author.</footnote>

<footnote>Email addresses: yuning@info.univ-angers.fr (Yuning Chen), hao@info.univ-angers.fr (Jin-Kao Hao), glover@opttek.com (Fred Glover).</footnote>
tics, such as household waste collection, product distribution, winter gritting and postal deliveries, among others [10]. The CARP model can be informally described as follows. We are given a graph with a set of vertices and edges, where each edge has a predefined traversal cost and where a subset of edges, which are required to be serviced by some vehicles, are additionally associated with a service cost and a demand. A fleet of identical vehicles with a limited capacity is based at the depot vertex. The objective of CARP is to find a set of vehicle routes with a minimum cost such that: 1) each required edge is serviced on one of the routes; 2) each route must start and end at the depot vertex; and 3) the total demand serviced on the route of a vehicle must not exceed the vehicle capacity.

From a theoretical point of view, CARP is known to be NP-hard [12], and hence is not expected to be solved by any exact algorithm in a polynomial time in the general case. The computational difficulty of solving CARP is also confirmed in practice. Indeed, the best existing exact algorithms are limited to moderate instances with only 140 vertices and 190 edges [3, 6, 7]. For these reasons, intensive research has been devoted to developing heuristic and metaheuristic methods. Representative heuristic methods include Augment-Merge [12], Path-Scanning [17], the route first-cluster second heuristic [33] and Ulusoys Heuristic [35]. Among the metaheuristic methods, neighborhood search approaches are popular, e.g., tabu search [4, 19, 24], variable neighborhood search [20, 30], guided local search [2], GRASP with evolutionary path relinking [36]. As another class of popular metaheuristics for tackling CARP, population-based algorithms generally achieve better performances, such as the memetic algorithm [22, 34], the ant colony algorithm [32] and the cooperative co-evolution algorithm [26]. Among these methods, two population-based algorithms (MEANS [34] and Ant-CARP [32]) and one local search algorithm (GLS [2]) represent the state-of-the-art solution methods for the classical test instance set, while RDG-MEANS [26] is the current best performing algorithm for the large-scale CARP (LSCARP) instances. Finally, for a thorough and up-to-date discussion of arc routing problems, the reader is referred to the recent book [8] edited by Á. Corberán and G. Laporte and in particular, chapter 7 by C. Prins dedicated to heuristic approaches.

In this work, we investigate a new population-based algorithm under the memetic search framework [27]. Memetic algorithms (MAs) have been proved to be very effective for solving a large number of difficult combinatorial optimization problems [28, 29], including CARP [22, 34]. The success of a MA highly depends on a careful design of two key search components: the crossover operator and the local refinement procedure [18]. Based on our previous experiences on MAs applied to various combinatorial problems, we go one step further by innovating especially on these two key components (crossover and local refinement) with the goal of elaborating a powerful memetic algorithm able to surpass the current state-of-the-art CARP methods.
The main contributions of our work can be summarized as follows.

* From the algorithmic perspective, the proposed population-based hybrid metaheuristic approach (HMA) combines a powerful local refinement procedure to ensure an effective search intensification with a dedicated crossover operator specially designed for CARP to guarantee a valid search diversification. The local refinement procedure couples a randomized tabu thresholding procedure to locate high-quality feasible solutions, with an infeasible descent procedure to enable tunneling between feasible and infeasible regions. The dedicated crossover operator relies on route information that can be embodied in exchanges of parent solutions to create new promising solutions. Additionally, to maintain a healthy population diversity and to avoid premature convergence, HMA employs a quality-and-distance strategy to manage the pool of solutions using a dedicated distance measure.

* In terms of computational results, extensive experiments carried out on 8 sets of widely used benchmarks show the competitiveness of the proposed method compared to the state-of-the-art CARP algorithms in solution quality and computational efficiency. For the 7 sets of 181 small-sized and medium-sized instances, HMA consistently matches or improves on all the best known results. In particular, HMA discovers a new best known result (new upper bound) for 6 well-studied instances. For the last set of 10 large-sized CARP benchmarks, HMA exhibits an even better performance. It easily dominates the state-of-the-art algorithms, including those specially designed for these CARP instances, by finding 9 new best known solutions, demonstrating the outstanding scalability of the proposed method.

The rest of the paper is organized as follows. Section 2 introduces preliminary notation and the solution representation. Sections 3 and 4 are dedicated to the description of the main HMA algorithm. Section 5 presents the computational results. Section 6 investigates some key elements of HMA, followed by the conclusions in Section 7.

## 2 Notation and solution representation

We are given a graph $G(V, E)$ with a set of vertices $(V)$, a set of edges $(E)$, a set of required edges $(E_R \subset E)$ and a fleet of identical vehicles with a capacity of $Q$ that is based at the depot vertex $v_d$ ($v_d \in V$). Each edge $e = (i, j) \in E$ is represented by a pair of arcs $<i, j>$ and $<j, i>$. A required edge is said to be served if and only if one of its two arcs is included in one vehicle route of the routing plan. For the sake of simplicity, we use the term *task* to represent a required edge hereafter. Let $n$ be the number of tasks, i.e., $n = |E_R|$. Each arc of a task, say $u$, is characterized by four elements: the head vertex (*head*($u$)), the tail vertex (*tail*($u$)), the traversal cost (*tc*($u$)) and the demand (*q*($u$)).
To represent a CARP solution, we assign to each task (i.e., a required edge) two IDs $(i, i+n)$ where $i$ is an integer number in $[1, n]$, i.e., one ID for each arc of the task. We also define a dummy task with 0 as its task ID and both its head and tail vertices being the depot vertex $v_d$. This dummy task is to be inserted somewhere in the solution as a trip delimiter. Suppose a solution $S$ involves $m$ vehicle routes, $S$ can then be encoded as an order list of $(n+m+1)$ task IDs among which $(m+1)$ are dummy tasks: $S = \{S(1), S(2), ..., S(n+m+1)\}$, where $S(i)$ denotes a task ID (an arc of the task or a dummy task) in the $i^{th}$ position of $S$. $S$ can be also written as a set of $m$ routes (one route per vehicle): $S = \{0, R_1, 0, R_2, 0, ..., 0, R_m, 0\}$, where $R_i$ denotes the $i^{th}$ route composed of $|R_i|$ task IDs (arcs), i.e., $R_i = \{R_i(1), R_i(2), ..., R_i(|R_i|)\}$, with $R_i(j)$ being the task ID at the $j^{th}$ position of $R_i$. Let $dist(u, v)$ denote the shortest path distance between the head vertex of arc $u$ (head($u$)) and the tail vertex of arc $v$ (tail($v$)), the total cost of a solution $S$ can be calculated as:

$$f(S) = \sum_{i=1}^{n+m} (tc(S(i)) + dist(S(i), S(i+1))) \quad (1)$$

The total load $load(R_i)$ of a route $R_i$ can be calculated as:

$$load(R_i) = \sum_{j=1}^{|R_i|} q(R_i(j)) \quad (2)$$

# 3 A hybrid metaheuristic algorithm for CARP

In this section, we describe the proposed hybrid metaheuristic algorithm (HMA) for CARP including the main procedure, the procedure for generating initial solutions, the specific route-based crossover as well as the quality-and-distance based pool maintenance procedure. The local refinement procedure of HMA is presented in Section 4.

## 3.1 Main scheme

Our HMA algorithm can be considered as a hybrid steady-state evolutionary algorithm which updates only one population solution at each generation of the evolution process [14]. Algorithm 1 shows the main scheme of the HMA algorithm. HMA starts with an initial population of solutions (Line 1 of Algo. 1) which are first generated by a random path scanning heuristic (Sect. 3.2) and further improved with the local refinement procedure (Sect. 4). Before entering the main loop, HMA initializes a counter array Cnt (Lines 3-4) which
is used to record the accumulated number of successful pool updates with the related threshold ratio value in a given set $S_r$ (an external input).

At each generation, HMA randomly selects two parent solutions $S^1$ and $S^2$ from the population (Line 6), and performs a route-based crossover (RBX) operation (Line 7, see Sect. 3.3) to generate an offspring solution $S^0$. RBX basically replaces one route of one parent solution with one route from the other parent solution, and repairs, if needed, the resulting solution to ensure the feasibility of $S^0$. HMA then applies the local refinement procedure (Line 10, Sect. 4) to further improve $S^0$. The local refinement procedure involves two sub-procedures, namely a randomized tabu thresholding procedure (RTTP) and an infeasible descent procedure (IDP), which can be carried out in two possible orders: RTTP followed by IDP (RTTP→IDP) and IDP followed by RTTP (IDP→RTTP). The applied order is determined randomly before running the local refinement procedure (Line 8, see Sect 4.4). RTTP requires a threshold ratio which is probabilistically chosen among the values of a given set $S_r$ according to the probability formula: $Pr(i) = Cnt(i)/\sum_{i=1}^{|S_r|} Cnt(i)$, where $Pr(i)$ denotes the probability of selecting the $i^{th}$ value of $S_r$ (Line 9).

<caption>**Algorithm 1:** Main Scheme of HMA for CARP</caption>

**Data:** $P$ - a CARP instance; $Psize$ - population size; $St$ - a set of tabu timing values; $W$ - the number of non-improving attractors visited; $Sr$ - a set of threshold ratios; $LB$ - the best known lower bound of $P$

**Result:** the best solution $S^*$ found

// Population initialization, Section 3.2
1 $POP \leftarrow Pool_Initialization(Psize)$;
2 $S^* \leftarrow Best(POP)$; /* $S^*$ records the best solution found so far */
3 **for** $i = 1$ **to** $|Sr|$ **do**
4 $Cnt(i) = 1$; /* Initialize the counter array $Cnt$ */
// Main search procedure
5 **while** stopping condition not reached **do**
6 $S^0 \leftarrow Crossover(S^1, S^2)$; /* Route-based crossover, Sect. 3.3 */
7 $Od \leftarrow random_determine(RTTP \rightarrow IDP, IDP \rightarrow RTTP)$; /* Determine the order of conducting RTTP and IDP, Sect. 4.4 */
8 $k \leftarrow probabilistic_select(Cnt)$; /* Select a ratio, Sect. 4.2 */
9 $S^0 \leftarrow Local_refine(P, S^0, St, Sr(k), W, Od)$; /* Improve $S^0$, Sect. 4 */
10 **if** $f(S^0) = LB$ **then**
11 $\leftarrow return S^0$
12 $(S^*, POP) \leftarrow Pool_Updating(S^0, POP)$; /* Pool updating, Sect. 3.4 */
13 **if** pool updating is successful **then**
14 $\leftarrow Cnt(k) + 1$;
15 **return** $S^*$
If the improved solution reaches the lower bound LB, HMA terminates immediately and returns this solution (Line 11-12). Otherwise, HMA ends a generation by updating the recorded best solution and the population with the offspring solution $S_c$ (Line 13, see Sect. 3.4). If $S^0$ is successfully inserted into the population, the counter in relation to the threshold ratio used in the current generation is incremented by one (Lines 14-15). HMA terminates when a stopping condition is reached, which is typically a lower bound cutoff or a maximum number of generations.

## 3.2 Population initialization

To generate one initial solution of the population, HMA uses a randomized path-scanning heuristic (RPSH) to construct a solution which is then further improved by the local refinement procedure described in Section 4. RPSH is adapted from the well-known path-scanning heuristic [17] by randomizing its five arc selecting rules. Specifically, RPSH builds one route at a time in a step-by-step way, each route starting at the depot vertex. At each step, RPSH identifies a set $A$ of arcs (belonging to a set of unserved tasks) that are closest to the end of the current route and satisfy the vehicle capacity constraint. If $A$ is empty, RPSH completes the current route by following a shortest deadheading path to the depot vertex and starts a new route. Otherwise RPSH randomly selects one arc from $A$ and extends the current route with the selected arc. The selected arc as well as its inverse arc are marked served. This process continues until all tasks are served.

The solution constructed by RPSH is further improved by the local refinement procedure of Section 4. The improved solution is inserted to the population if it is unique in terms of solution cost relative to the existing solutions, or discarded otherwise. The population initialization procedure stops when the population is filled with $Psize$ (population size) different individuals or when a maximum of $3 * Psize$ trials is reached. The latter case helps to fill the population with $Psize$ distinct individuals. If ever only $k < Psize$ distinct solutions are obtained after $3 * Psize$ trials, we set the population size to $k$.

## 3.3 Route-based crossover operator for CARP

At each of its generations, HMA applies a crossover operator to create an off-spring solution by recombining two parent solutions randomly selected from the population. It has been commonly recognized that the success of memetic algorithms relies greatly on the recombination operator which should be adapted to the problem at hand and be able to transfer meaningful properties (building
blocks) from parents to offspring [18]. This idea is closely related to the idea
of using structured combinations and vocabulary building [16].

By considering that the solution of CARP is composed of a set of routes, it
is a natural idea to manipulate routes of tasks rather than individual tasks.
In this regard, the route-based crossover (RBX) operator used for the vehicle
routing problem (VRP) [31] seems attractive for CARP. However, given that
CARP is quite different from the VRP, RBX must be properly adapted in
our context within HMA. Given two parent solutions $S^1 = \{R_1^1, R_2^1, ..., R_{m_1}^1\}$
with $m_1$ routes and $S^2 = \{R_1^2, R_2^2, ..., R_{m_2}^2\}$ with $m_2$ routes, our RBX crossover
basically copies $S^1$ to an offspring solution $S^0$ and replaces a route of $S^0$ with
a route from $S^2$, and then repairs $S^0$ to establish feasibility if needed. The
RBX crossover procedure consists of three main steps:

* **Step 1:** Copy $S^1$ to an offspring solution $S^0 = \{R_1^0, R_2^0, ..., R_{m_1}^0\}$ and replace a route of $S^0$ with a route from $S^2$. Generate two random integer values $a$ ($a \in [1, m_1]$) and $b$ ($b \in [1, m_2]$); Replace the route $R_a^0$ of solution $S^0$ with the route $R_b^0$ of solution $S^2$, and collect the tasks that are not served in $S^0$ to a set *UT*;

* **Step 2:** Remove duplicated tasks by the following rule. Let $S^0(p_i)$ be the task in position $p_i$, and let $p_i - 1$ be the position before $p_i$ and $p_i + 1$ be the position after $p_i$. Also let $dist(u, v)$ denote the shortest path distance between vertex head($u$) and vertex tail($v$). Given a task $t_0$ which appears twice respectively in position $p_1$ and $p_2$, RBX removes the appearance with the largest value of $s(p_i)$ ($i \in \{1, 2\}$), where $s(p_i) = dist(S^0(p_i - 1), S^0(p_i)) + dist(S^0(p_i), S^0(p_i + 1)) - dist(S^0(p_i - 1), S^0(p_i + 1))$.

* **Step 3:** Insert the unserved tasks of *UT* in $S^0$. Before task insertion, RBX sorts the tasks in set *UT* in random order. Then for each task *t* in *UT*, RBX scans all possible positions of $S^0$ to insert *t*. If a position is able to accommodate *t* while respecting the vehicle capacity, RBX further calculates the saving (change of the total cost) with *t* inserted. The two arcs of *t* are both considered for insertion, and the minimum saving is recorded. RBX finally inserts the task to a position which causes the overall least augmentation of the total cost while maintaining the solution feasibility. Ties are broken randomly. This process is repeated until *UT* becomes empty.

Our proposed RBX operator not only introduces a new route (taken from $S^2$) into $S^0$, but also modifies other existing routes due to deletion of duplicated tasks and insertion of unserved tasks. Clearly, RBX could lead to an offspring solution which is structurally different from its parent solutions. This is a desirable feature which promotes the overall diversity of HMA. Moreover, the quality of the offspring is not much deteriorated due to the use of greedy heuristics in Steps 2 and 3. As such, when the offspring is used as a seeding solution of local refinement, it helps the search to move into a new promising region. RBX can be realized in $O(n^2)$, where *n* is the number of tasks.
## 3.4 Population management

In population-based algorithms, one important goal aims to avoid premature convergence of the population. This can be achieved by adopting a carefully designed strategy for population management. In HMA, we use a quality-and-distance strategy (QNDS) for this purpose. QNDS takes into account not only the solution quality, but also the diversity that the solution contributes to the whole population by resorting to a solution distance measure.

We propose in this work to adapt for the first time the Hamming distance in the context of CARP and use it as our distance measure. Any pair of consecutive tasks $(S(i), S(i+1))$ of a solution $S$ is linked by a shortest path (a path with minimum deadheading cost) between head($S(i)$) and tail($S(i+1)$), called deadheading-link hereafter. Thus, solution $S$ has $n+m$ deadheading-links where $n$ is the number of tasks and $m$ is the number of routes. Let $V_R \subset V$ be a set of vertices that belong to the required edges, let $V'_R = V_R \cup \{v_d\}$ be a set containing both the vertices of $V_R$ and the depot vertex $v_d$, let $\Pi = \{(u, v)|u, v \in V'_R\}$ be the set of all possible deadheading-links. Given two solutions $S^i$ with $m_i$ routes and $S^j$ with $m_j$ routes, their Hamming distance $D_{i,j}$ is defined as the number of different deadheading-links between $S^i$ and $S^j$:

$$D_{i,j} = (n+m) - \sum_{(u,v) \in \Pi} x_{uv} \quad (3)$$

where $m = \min\{m_i, m_j\}$,

$$x_{uv} = \begin{cases} 1, & \text{if } (u, v) \text{ is a deadheading-link of both } S^i \text{ and } S^j \\ 0, & \text{otherwise} \end{cases} \quad (4)$$

Given a population $POP = \{S^1, S^2, ..., S^{Psize}\}$ of size $Psize$ and the distance $D_{i,j}$ between any two individuals $S^i$ and $S^j$ ($i \neq j \in [1, Psize]$), the average distance between $S^i$ and any other individual in $POP$ is given by:

$$AD_{i,POP} = \left( \sum_{S^j \in POP, j \neq i} D_{i,j} \right) / (Psize - 1) \quad (5)$$

QNDS evaluates each solution in the population using the following quality-and-distance fitness (QDF for short) function:

$$QDF(S^i) = \alpha * OR(f(S^i)) + (1 - \alpha) * DR(AD_{i,POP}) \quad (6)$$

where $OR(f(S^i))$ and $DR(AD_{i,POP})$ represent respectively the rank of solution $S^i$ with respect to its objective value and the average distance to the population (objective value is ranked in ascending order while average distance is ranked in descending order), and $\alpha$ is a parameter. We require the
value of $\alpha$ to be higher than 0.5 to ensure that the best individual in terms of objective value will never be removed from the population, which formalizes the elitism property of QNDS.

Given an offspring $S^0$ (which has undergone both crossover and local refinement), QNDS first inserts $S^0$ into *POP*, evaluates the QDF value of each individual and finally removes from *POP* the solution $S^w$ with the largest QDF value.

# 4 Local refinement procedure of HMA

The local refinement procedure is another key component of our HMA algorithm and plays an essential role in enforcing intensification which ensures the high performance of HMA. Our local refinement procedure involves two sub-procedures, i.e., a randomized tabu thresholding procedure which explores only the feasible region, and an infeasible descent procedure which visits both feasible and infeasible regions. Both sub-procedures are based on a set of move operators which are explained below. The implementation of the two sub-procedures are also described.

## 4.1 Move operators

Our local refinement procedure employs six move operators, including five traditional small-step-size operators: inversion, single insertion, double insertion, swap, two-opt; as well as a large-step-size operator called merge-split recently proposed in [34]. These operators are briefly described as follows.

Let $u$ and $v$ be a pair of tasks in the current solution $S$, tasks $x$ and $y$ be respectively the successor of $u$ and $v$, $rt(u)$ be the route including task $u$.

* Inversion (IV): replace the current arc of task $u$ with its reverse arc in $S$;

* Single insertion (SI): displace task $u$ after task $v$ (also before task $v$ if $v$ is the first task of $rt(v)$); both arcs of $u$ are considered when inserting $u$ in the target position, and the one yielding the best solution is selected;

* Double insertion (DI): displace a sequence $(u, x)$ after task $v$ (also before task $v$ if $v$ is the first task of $rt(v)$); similar to SI, both directions are considered for each task and the resulting best move is chosen;

* Swap (SW): exchange task $u$ and task $v$; similar to SI, both directions are considered for each task to be swapped and the resulting best move is chosen;

* Two-opt (TO): two cases exist for this move operator: 1) if $rt(u) = rt(v)$,
reverse the direction of the sequence $(x, v)$; 2) if $rt(u) \neq rt(v)$, cut the link between $(u, x)$ and $(v, y)$, and establish a link between $(u, y)$ and $(v, x)$;

* Merge-split (MS): this operator obtains an unordered list of tasks by merging multiple routes of the current solution, and sorts the unordered list with the path scanning heuristic [17]. It then optimally splits the ordered list into new routes using the Ulusoy's splitting procedure [35]. Each application of this operator results in five new solutions and the best one is chosen. Interested readers are referred to [34] for more details.

In the following two subsections, we explain how these operators are used in
our two local refinement sub-procedures.

## 4.2 Randomized tabu thresholding procedure

The proposed randomized tabu thresholding procedure (RTTP) follows the general principle of the Tabu Thresholding (TT) method whose basis was first proposed in [13]. A main ingredient of TT is the candidate list strategy (CLS) which is dedicated to reduce the number of moves to be considered in order to accelerate the neighborhood examination. CLS subdivides the possible moves of the current solution into subsets and executes one move for each subset rather than for the whole neighborhood. CLS, along with the elements of probabilistic tabu search, simulates the tabu mechanism with memory structure. RTTP is a randomized procedure in the sense that it explores multiple neighborhoods in a random order.

### 4.2.1 *Outline of the randomized tabu thresholding procedure*

The randomized tabu thresholding procedure basically alternates between a *Mixed phase* and an *Improving phase* where for both phases, five traditional move operators are employed: inversion, single insertion, double insertion, swap and two-opt. Algorithm 2 sketches the outline of the RTTP procedure for CARP. RTTP starts by initializing a set of global variables with an initial solution $S_0$ taken from an external input. RTTP then enters the main loop where *Mixed phase* and *Improving phase* alternate.

In the *Mixed phase*, for any move operator *o* and for a given task *i*, RTTP examines the candidate list `MOVE_CL(i, S, o)` in random order and accepts the first improving feasible move if any, or the best admissible feasible move otherwise. The admissible feasible move satisfies a quality threshold *TV*, i.e., $f(S') \le TV$ where *S'* is the neighboring solution generated by the accepted move. *TV* is calculated as: $TV = (1 + r) * f_p$, where *f*<sub>*p*</sub> is the current best local optimum objective value, and *r* is a threshold ratio. With this quality threshold, deteriorating solutions are allowed in order to diversify the search.
Solution cycling is prevented through the complete reshuffling of the order in which candidate lists are examined before each neighborhood examination. An iteration of the *Mixed phase* is based on the examination of the complete neighborhoods of all move operators. The *Mixed phase* is repeated for *T* iterations. *T* is called a tabu timing parameter, which is analogous to the tabu tenure when an explicit tabu list is used. *T* is randomly selected among the values of a given set *St*.

<caption>**Algorithm 2:** Outline of the RTTP for CARP</caption>

**Data:** *P* - a CARP instance, *St* - a set of tabu timing values, *r* - threshold ratio, *W* - the number of non-improving attractors visited, *S*₀ - an initial solution;
**Result:** the best solution *S*\* found so far;
1 &nbsp;&nbsp;*O* ← {*IV, SI, DI, SW, TO*}; /* *O* contains five move operators */
2 &nbsp;&nbsp;*S*\* ← *S*₀; /* *S*\* records the global best solution */
3 &nbsp;&nbsp;*S* ← *S*₀; /* *S* records the current solution */
4 &nbsp;&nbsp;*f*ₚ ← *f*(*S*\*); /* *f*ₚ records the best local optimum objective value */
5 &nbsp;&nbsp;*w* ← 0; /* set counter for consecutive non-improving local optima */
6 &nbsp;&nbsp;**while** *w* &lt; *W* **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;*T* ← *random_select*(*St*); // **Mixed Phase**
8 &nbsp;&nbsp;&nbsp;&nbsp;**for** *k* ← 1 **to** *T* **do**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Randomly shuffle all operators in *O*;
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** **each** *o* ∈ *O* **do**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Randomly shuffle tasks of *S* in *M*;
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** **each** *i* ∈ *M* **do**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*S*, *S*\*) ← Apply operator *o* to task *i* by searching
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MOVE_CL(*i*, *S*, *o*) and accepting a move according to the quality
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;threshold;
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**// Improving Phase**
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**while** Improving moves can be found **do**
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Randomly shuffle all operators in *O*;
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** **each** *o* ∈ *O* **do**
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Randomly shuffle tasks of *S* in *M*;
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** **each** *i* ∈ *M* **do**
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*S*, *S*\*) ← Apply operator *o* to task *j* by searching
23 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MOVE_CL(*i*, *S*, *o*) and accepting the first met improving move;
24 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *f*(*S*) &gt; *f*ₚ **then**
25 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*f*ₚ ← *f*(*S*); *w* ← 0;
26 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
27 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*w* ← *w* + 1;

In the *Improving phase*, RTTP always seeks an improving move among the feasible moves within each candidate list `MOVE_CL(i, S, o)`. If no improving move is found in a given candidate list, RTTP skips to the next candidate list. This phase is iterated until no improving move can be found in any candidate list.

If the local optimum reached in the *Improving phase* has a better objective value than the recorded best objective value *f*<sub>p</sub>, the algorithm updates *f*<sub>p</sub> and
resumes a new round of *Mixed-Improving* phases. RTTP terminates when $f_p$ has not been updated for a consecutive *W Mixed-Improving* phases.

### 4.2.2 Construct candidate list

When using the five traditional move operators, neighborhoods of the current solution can always be obtained by operating on two distinct tasks. For instance, *insertion* is to insert one task after or before another task; *swap* is to swap one task with another task; *two-opt* is to exchange the subsequent part of a task with that of another one. As such, given a move operator *o*, a natural choice for the subsets to be used in the candidate list strategy is to define one subset $MOVE_SUBSET(i, S, o)$ for each task *i*. In order to speed up neighborhood examination, we further use an estimation criterion to discard moves from $MOVE_SUBSET(i, S, o)$ that are unlikely to lead to a promising solution. This estimation criterion is based on a distance measure between two tasks $t_1, t_2$ which is defined as:

$$D_{task}(t_1, t_2) = \left( \sum_{a=1}^{2} \sum_{b=1}^{2} D(v_a(t_1), v_b(t_2)) \right) / 4 \quad (7)$$

where $D(v_a(t_1), v_b(t_2))$ is the traversing distance between $t_1$'s *a*th end node $v_a(t_1)$ and $t_2$'s *b*th end node $v_b(t_2)$. (This distance measure was first used in [26] to define the distance between two routes.) The candidate move list associated to task *i* ($MOVE_CL(i, S, o)$) is restricted to contain *Csize* most promising moves such that for each move which is associated with two tasks (*i*, *t*), *t* is a member of *i*'s *Csize* closest neighboring tasks according to the distance measure of formula 7.

### 4.3 Infeasible descent procedure

For a constrained optimization problem like CARP, it is known that allowing a controlled exploration of infeasible solutions may facilitate transitions between structurally different solutions and help discover high-quality solutions that are difficult to locate if the search is limited to the feasible region. This observation is highlighted by discoveries made with the strategic oscillation approach (see, e.g., [15]) which alternates between phases of infeasible descent and phases of improving feasible search. To further intensify the search, we employ in our local refinement procedure, as a complement to RTTP, an infeasible descent procedure (IDP) which allows visiting infeasible solutions. IDP is a best-improvement descent procedure based on three traditional move operators, i.e., single insertion, double insertion, swap, as well as a large-step-size merge-split operator that was recently proposed and proved to be effective for CARP [34]. We use the merge-split operator in the way as suggested in [34].
IDP basically involves two different stages. In the first stage, IDP examines the complete neighborhoods induced by the SI, DI and SW operators and chooses the best move to perform if it improves the current solution. When no improvement can be found in the first stage, IDP switches to the second stage where it examines the neighboring solutions generated by the MS operator. Since MS is computationally expensive, IDP restricts the examination to a maximum of 100 neighboring solutions which are randomly sampled from the $C_m^2$ possibilities where $m$ is the number of routes. If $C_m^2 \le 100$, all neighboring solutions will be examined. Still, the best improving move is performed until no improvement is reported in this stage. If any improvement is found in the second stage, IDP switches back to the first stage to explore the new local region and terminates the algorithm when this stage is finished; otherwise, IDP terminates at the end of the second stage. As in many previous CARP algorithms which allow intermediate infeasible solutions [2, 4, 19, 34], we evaluate the solution quality generated in the search process of IDP by adding a penalty item to the original cost:

$$ \phi(S) = f(S) + \beta * EX(S) \quad (8) $$

where $EX(S)$ is the total excess demand of $S$ and $\beta$ is a self-adjusting penalty parameter. $\beta$ is halved (doubled) if feasible (infeasible) solutions have been achieved for five consecutive iterations, and its initiating value is set to:

$$ \beta = f(S)/(2 * Q) \quad (9) $$

where $Q$ is the vehicle capacity. One notices that we don't consider the violation of $S$ in Eq. 9. This is because we always ensure that IDP starts the search from a feasible solution.

## 4.4 Combination of RTTP and IDP

After presenting the implementation of RTTP and IDP, the order of combining them in the local refinement procedure remains an issue to be addressed. RTTP is the most important component of our HMA algorithm which compared to IDP, makes more contribution to the high performance of HMA, but also consumes more computing time (see the analysis in Sect. 6.1). IDP is a very simple descent procedure which, when used alone, is not expected to identify very high quality solutions (see the analysis in Sect. 6.1). However, the search ability of RTTP and IDP can be mutually strengthened when they are combined. Indeed, it is beneficial to put IDP either before or after RTTP. When IDP is placed before RTTP, the best feasible solution found by IDP can be considered as a good starting point for RTTP. This is because the performance of neighborhood search algorithms may highly depend on the initial solution and a high-quality initial solution could help discover
still better solutions. When IDP is put after RTTP, the property of tunneling
through infeasible regions and the large-step-size MS operator of IDP may
help to further improve the high quality solution provided by RTTP. For the
above reasons, both orders (i.e., RTTP→IDP and IDP→RTTP) are allowed
in our HMA algorithm. The order is randomly determined before the local
refinement procedure is carried out.

# 5 Computational experiments

To evaluate the efficacy of the proposed HMA algorithm, we carry out exten-
sive experiments on a large number of well-known CARP benchmark instances,
and compare the results<fnref n="1" /> with those of the state-of-the-art algorithms as well
as the best known solutions ever reported in the literature.

HMA was coded in C++ and compiled by GNU g++ 4.1.2 with the '-O3'
option. The experiments were conducted on a computer with an AMD Opteron
4184 processor (2.8GHz and 2GB RAM) running Ubuntu 12.04. When solving
the DIMACS machine benchmarks<fnref n="2" /> without compilation optimization flag,
the run time on our machine is 0.40, 2.50 and 9.55 seconds respectively for
instances r300.5, r400.5 and r500.5.

5.1 *Experimental setup*

Our HMA algorithm was evaluated on a total of 191 benchmark graphs with
7 to 255 vertices and 11 to 375 edges. These instances are very popular and
widely used in the CARP literature. They cover both random instances and
real-life applications, and are typically classified into eight sets:

* **gdb**: 23 instances randomly generated by DeArmon [9], with 7-27 nodes and 11-55 required edges.

* val : 34 instances derived from 10 randomly generated graphs proposed by Benavent et al. [1], with 25-50 nodes and 34-97 required edges.

* **egl**: 24 instances proposed by Eglese [11], which originate from the data of a winter gritting application in Lancashire (UK), with 77-140 nodes and 98-190 edges that include 51-190 required edges.

* C: 25 instances generated by Beullens et al. [2] based on the intercity road network in Flanders, with 32-97 nodes and 42-140 edges that include 32-107 required edges.

<footnote n="1">¹ Our best solution certificates are available at: http://www.info.univ-
angers.fr/pub/hao/CARPResults.zip</footnote>

<footnote n="2">² dfmax: ftp://dimacs.rutgers.edu/pub/dsj/clique/</footnote>
• *D*: 25 instances modified from the instances of set *C* by doubling the vehicle capacity for each instance.

• *E*: 25 instances, also generated by Beullens *et al.* [2] based on the intercity road network in Flanders, with 26-97 nodes and 35-142 edges that include 28-107 required edges.

• *F*: 25 instances modified from the instances of set *E* by doubling the vehicle capacity for each instance.

• *EGL-G*: 10 large-sized CARP instances, which like the set *egl*, were also generated based on the road network of Lancashire (UK) [4], each having 255 nodes and 375 edges with 374 to 375 required edges.

Following the common practice in the literature, we compare the results produced by our HMA algorithm on these benchmarks to those of the following eight state-of-the-art algorithms:

1. A guided local search (GLS) algorithm proposed by Beullens *et al.* [2], who reported results on the instance set *gdb*, *val* and *C-F*.

2. A deterministic tabu search algorithm (TSA) proposed by Brando & Eglese [4], who reported results on all eight instance sets. Two sets of results ("TSA1" and "TSA2") were reported, and the one ("TSA2") yielding better performance will be considered for comparative study for all instance sets except for EGL-G where only results of "TSA1" were reported.

3. A variable neighbourhood search (VNS) algorithm proposed by Polacek *et al.* [30], who reported results on set *val* and *egl*. Two sets of results ("993 MHz" and "3.6 GHz") were reported, and the one ("3.6 GHz") yielding better performance will be considered for comparative study.

4. A memetic algorithm with extended neighbourhood search (MAENS) proposed by Tang *et al.* [34], who reported results on set *gdb*, *val*, *egl* and *C-F*.

5. An improved ant colony optimization based algorithm (Ant-CARP) proposed by Santos *et al.* [32], who reported results on set *gdb*, *val*, *egl* and *C-F*. Two sets of results ("Ant-CARP_6" and "Ant-CARP_12") were reported, and the one ("Ant-CARP_12") yielding overall better performance will be considered for comparative study. Hereafter, we use "Ant_12" to represent "Ant-CARP_12", and use its median results for comparison when we study the average performance of the reference algorithms since their average results are not available.

6. A GRASP with evolutionary path relinking (GRASP) proposed by Usberti *et al.* [36], who reported results on the set *gdb*, *val* and *egl*.

7. An iterated variable neighbourhood descent algorithm (ILS-RVND) proposed by Martinelli *et al.* [25]. We reference their reported results of set *EGL-G*.

8. A cooperative co-evolution algorithm with route distance grouping (RDG-MAENS) proposed by Mei *et al.* [26]. RDG-MAENS was specifically designed for large-sized CARP instances, and thus we reference their results
<table><caption>Table 1
Scaling factors for computers used in the reference algorithms. Our computer (AMD Opteron 4184) is used as the basis.</caption><thead><tr><td>Algorithm</td><td>Reference</td><td>Processor type</td><td>Frequency (GHz)</td><td>Factor</td></tr></thead><tbody><tr><td>HMA</td><td>-</td><td>AMD Opteron 4184</td><td>2.8</td><td>1.0</td></tr><tr><td>GLS</td><td>[2]</td><td>Pentium II</td><td>0.5</td><td>0.18</td></tr><tr><td>VNS</td><td>[30]</td><td>Pentium IV</td><td>3.6</td><td>1.29</td></tr><tr><td>TSA2</td><td>[4]</td><td>Pentium Mobile</td><td>1.4</td><td>0.50</td></tr><tr><td>MAENS</td><td>[34]</td><td>Intel Xeon E5335</td><td>2.0</td><td>0.71</td></tr><tr><td>Ant_12</td><td>[32]</td><td>Pentium III</td><td>1.0</td><td>0.36</td></tr><tr><td>GRASP</td><td>[36]</td><td>Intel Core 2</td><td>3.0</td><td>1.07</td></tr><tr><td>ILS-RVNS</td><td>[25]</td><td>Intel Core i5</td><td>3.2</td><td>1.14</td></tr><tr><td>RDG-MAENS</td><td>[26]</td><td>Intel Core i7-2600</td><td>3.4</td><td>1.21</td></tr></tbody></table>

on set *EGL-G*.

These reference algorithms were tested on different computers with a CPU frequency ranging from 500 MHz to 3.6 GHz. To make a relatively fair comparison of the runtime, all CPU times reported in the reference papers are scaled here into the equivalent AMD Opteron 4184 2.8 GHz run times. Like in previous CARP literature [25, 26, 32, 34], our time conversion is based on the assumption that the CPU speed is approximately linearly proportional to the CPU frequency. We provide in Table 1 the CPU type and its frequency of each reference algorithm, as well as its resulting scaling factors. This time conversion is only made for indicative purposes, since the computing time of each algorithm is not only influenced by the processor, but also by some inacessible factors such as the operating systems, compilers and coding skills of the programmer. Nevertheless, we show in the following experiments, the outcomes provide interesting information about the performance of the proposed algorithm relative to the best performing algorithms.

## 5.2 Parameter tuning

The HMA algorithm relies on a set of correlated parameters. To achieve a reasonable tuning of the parameters, we adopt the Iterated F-race (IFR) method [5], which allows an automatic parameter configuration, using the IFR algorithm that is implemented and integrated in the irace package [23]. Table 2 summarizes the parameters of our HMA algorithm, along with the range of values that were determined by preliminary experiments. Among these parameters, four of them (Psize, α, W, Csize) need to be tuned and the other two parameters (threshold ratio *r* and tabu timing parameter *T*) are adaptively or randomly chosen among the values in the given sets (Sr and St) during the search process. We set the tuning budget to 1000 runs of HMA and each run is given 100 generations. We restrict the training set to contain 8 challenging instances taken from *val*, *egl*, *C*, *E* and *EGL-G* sets: val-10D, egl-e3-B, egl-s3-C, C11, E12, E15, EGL-G1-B, EGL-G2-B. The final choices of the parameter
<table><caption>Table 2
Parameter tuning results</caption><thead><tr><th>Parameter</th><th>Description</th><th>Range</th><th>Final value</th></tr></thead><tbody><tr><td>Psize</td><td>population size</td><td>[6,16]</td><td>10</td></tr><tr><td>α</td><td>parameter of QDF in pool updating</td><td>[0.51,0.90]</td><td>0.60</td></tr><tr><td>St</td><td>tabu timing parameter values in RTTP</td><td>[28,33]</td><td>-</td></tr><tr><td>W</td><td>maximum number of attractors in RTTP</td><td>[5,20]</td><td>10</td></tr><tr><td>Sr</td><td>threshold ratios in RTTP for classical sets<br>for EGL-G set</td><td>{0.003,0.004,0.005,0.006}<br>{0.0001,0.0005,0.0010,0.0015}</td><td>-</td></tr><tr><td>Csize</td><td>candidate list size</td><td>[6,20]</td><td>12</td></tr></tbody></table>

values are presented in Table 2 and they are used in all experiments in the following sections unless otherwise mentioned.

## 5.3 Comparative results on 7 classical instance sets

We first assess HMA on the 7 most commonly used instance sets (181 instances): gdb, val, egl, C, D, E, F. It is compared to 5 current state-of-the-art algorithms: GLS [2], TSA2 [4], VNS [30], Ant-CARP [32], GRASP [36], and MAENS [34]. To give a general picture of the performance of each compared algorithm, we summarize in Table 3, for each instance set and for each algorithm, the number of best results that match or improve on the best known results (#Best), the number of average results that match or improve on the best known results (#BestAvg), the average gap between the average results and the best known results in percentage (AvgGap, the gap is calculated as $(f_{avg}-f_{bk})\times100/f_{bk}$ where $f_{avg}$ is the average solution value obtained by the algorithm and $f_{bk}$ is the best known solution value reported in the literature), and the average of the instance computing time in seconds (AvgTime). When we count #Best, we refer to the current best known results (BKRs) which are compiled from the "best results" reported in all previous CARP literature. These "best results" could be those obtained by a single algorithm with various parameter settings (e.g., [22, 30, 32]) or even with a specific setting tuned for each instance (e.g., TSA<sub>best</sub> in [4]). Finally, to complement these summarized results, Appendix A (Tables A.1–A.7) reports, for each of the 181 CARP instance, the detailed results of our HMA algorithm as well as the average results of the reference algorithms. These tables permit a thorough assessment of all compared algorithms.

Note that some results were obtained from a single run of the algorithms (GLS and TSA) whereas other results came from multiple runs (VNS, GRASP, Ant-CARP, MAENS, HMA1 and HMA2). Clearly, #Best favors multiple-run results. To make a fair comparison, we refer to average statistics (#BestAvg, AvgGap, AvgTime) when we compare single-run results with multiple-run results.

For each instance, our HMA algorithm was run 30 times under two different
stop criteria: 500 generations and 2000 generations. To ease presentation, we denote HMA with 500 generations as $HMA_1$, and HMA with 2000 generations as $HMA_2$. Studying the outcomes of these two termination criteria affords insights into how HMA behaves when more computing time is available.

From Table 3, we can see that $HMA_1$ shows a remarkable performance on all 7 tested instance sets compared to the multiple-run reference algorithms. Indeed, it attains the largest number of best known results for all 7 data sets and the lowest average gap to the best known results for 6 out of 7 sets. Compared to Ant_12 and MAENS which, like $HMA_1$, are both population-based algorithms, $HMA_1$ clearly shows its dominance in terms of both best results and average results. For set D, $HMA_1$ is the only algorithm which is able to find all BKRs. Additionally, $HMA_1$ obtains improved best known results on three well-studied instances from set *egl*. By increasing the $HMA_1$ termination criterion of 500 generations to 2000 generations, $HMA_2$ achieves a still better performance, always obtaining equal or better results in terms of both \#Best and AvgGap. In particular, for set *egl*, $HMA_2$ discovers 6 new BKRs and matches 6 more BKRs, leading to \#Best = 23 which is significantly larger than those obtained by the reference algorithms. $HMA_2$ is able to achieve overall 180 current or new BKRs out of 181 instances with one standard parameter setting, while the previous BKRs are compiled from many previous articles, among which some were obtained with parameters specifically tuned for individual instance.

Now we turn to compare our HMA algorithm to the single-run reference algorithms. As mentioned before, we should look at average statistics when comparing multiple-run algorithms to single-run algorithms. According to two average indicators, namely \#BestAvg and AvgGap, GLS is clearly the best performing single-run algorithm among all 6 reference algorithms (including single-run algorithms and multiple-run ones). Still, compared to GLS, our HMA algorithm remains competitive on 6 instance sets (i.e., gdb, val and C-F). Indeed, when the short time limit (500 generations) is applied, $HMA_1$ performs better in items of AvgGap (by achieving an equal or lower AvgGap for more instance sets: 5 vs. 3), but worse in terms of \#BestAvg (by attaining an equal or higher \#BestAvg for less instance sets: 2 vs. 6). On set D, both $HMA_1$ and $HMA_2$ are dominated by GLS in terms of both indicators. Finally, one observes that when given more computing time, $HMA_2$ is able to further improve its results.

To validate the above observations, we apply a Wilcoxon test with a significance factor of 0.05 for a pairwise comparison of the average performance between $HMA_1$ and TSA2, Ant_12 as well as MAENS, which are three approaches that have been tested on all 181 instances. The resulting p-values of 2.15E-10, 9.31E-10 and 2.20E-16 confirm that the results of $HMA_1$ are significantly better than those of these current best performing algorithms. This conclusion remains valid for $HMA_2$ since it always performs better than
<caption>Table 3</caption>

Comparative statistical results on the 7 classical instance sets: gdb, val, egl, C-F. The best result of each row is indicated in bold. The results of HMA₂ are starred if they improve on the results of HMA₁.

<table><thead><tr><th></th><th></th><th>GLS<br>1 run</th><th>TSA2<br>1 run</th><th>VNS<br>10 runs</th><th>GRASP<br>15 runs</th><th>Ant_12<br>10 runs</th><th>MAENS<br>30 runs</th><th>HMA<sub>1</sub><br>30 runs</th><th>HMA<sub>2</sub><br>30 runs</th></tr></thead><tbody><tr><td rowspan="4">gdb</td><td>#Best</td><td><b>23</b></td><td>21</td><td>-</td><td><b>23</b></td><td>22</td><td><b>23</b></td><td><b>23</b></td><td><b>23</b></td></tr><tr><td>#BestAvg</td><td><b>23</b></td><td>21</td><td>-</td><td>19</td><td>21</td><td>22</td><td><b>23</b></td><td><b>23</b></td></tr><tr><td>AvgGap</td><td><b>0.00</b></td><td>0.07</td><td>-</td><td>0.11</td><td>0.10</td><td>0.01</td><td><b>0.00</b></td><td><b>0.00</b></td></tr><tr><td>AvgTime</td><td><b>0.32</b></td><td>1.23</td><td>-</td><td>5.47</td><td>1.21</td><td>4.47</td><td>1.19</td><td>1.19</td></tr><tr><td rowspan="4">val</td><td>#Best</td><td>30</td><td>29</td><td><b>32</b></td><td>30</td><td>29</td><td>31</td><td><b>32</b></td><td><b>34</b>*</td></tr><tr><td>#BestAvg</td><td><b>30</b></td><td>29</td><td>26</td><td>0</td><td>26</td><td>0</td><td>29</td><td><b>30</b></td></tr><tr><td>AvgGap</td><td>0.05</td><td>0.14</td><td>0.09</td><td>0.12</td><td>0.17</td><td>0.18</td><td><b>0.03</b></td><td><b>0.02</b>*</td></tr><tr><td>AvgTime</td><td>14.64</td><td>10.09</td><td>56.70</td><td>65.85</td><td><b>9.11</b></td><td>48.35</td><td>11.23</td><td>26.71</td></tr><tr><td rowspan="4">egl</td><td>#Best</td><td>-</td><td>4</td><td>11</td><td>12</td><td>11</td><td>12</td><td><b>15</b></td><td><b>23</b>*</td></tr><tr><td>#BestAvg</td><td>-</td><td>4</td><td>4</td><td>3</td><td><b>9</b></td><td>2</td><td><b>9</b></td><td><b>14</b>*</td></tr><tr><td>AvgGap</td><td>-</td><td>0.75</td><td>0.56</td><td>0.50</td><td>0.58</td><td>0.59</td><td><b>0.13</b></td><td><b>0.07</b>*</td></tr><tr><td>AvgTime</td><td>-</td><td><b>145.68</b></td><td>649.17</td><td>854.48</td><td>181.09</td><td>498.49</td><td>198.83</td><td>646.03</td></tr><tr><td rowspan="4">C</td><td>#Best</td><td>20</td><td>18</td><td>-</td><td>-</td><td>22</td><td>23</td><td><b>24</b></td><td><b>25</b>*</td></tr><tr><td>#BestAvg</td><td>20</td><td>18</td><td>-</td><td>-</td><td>16</td><td>3</td><td>18</td><td><b>23</b></td></tr><tr><td>AvgGap</td><td>0.12</td><td>0.14</td><td>-</td><td>-</td><td>0.52</td><td>0.98</td><td><b>0.06</b></td><td><b>0.02</b>*</td></tr><tr><td>AvgTime</td><td>42.49</td><td>42.92</td><td>-</td><td>-</td><td>40.76</td><td>165.50</td><td><b>36.88</b></td><td>54.22</td></tr><tr><td rowspan="4">D</td><td>#Best</td><td>24</td><td>17</td><td>-</td><td>-</td><td>23</td><td>23</td><td><b>25</b></td><td><b>25</b></td></tr><tr><td>#BestAvg</td><td><b>24</b></td><td>17</td><td>-</td><td>-</td><td>20</td><td>10</td><td>20</td><td>23</td></tr><tr><td>AvgGap</td><td><b>0.04</b></td><td>0.66</td><td>-</td><td>-</td><td>0.34</td><td>0.79</td><td>0.17</td><td>0.10</td></tr><tr><td>AvgTime</td><td>17.36</td><td>19.20</td><td>-</td><td>-</td><td>51.88</td><td>219.53</td><td><b>14.65</b></td><td>35.13</td></tr><tr><td rowspan="4">E</td><td>#Best</td><td>19</td><td>17</td><td>-</td><td>-</td><td>20</td><td>20</td><td><b>23</b></td><td><b>25</b>*</td></tr><tr><td>#BestAvg</td><td>19</td><td>17</td><td>-</td><td>-</td><td>16</td><td>5</td><td>16</td><td><b>20</b></td></tr><tr><td>AvgGap</td><td>0.20</td><td>0.39</td><td>-</td><td>-</td><td>0.83</td><td>1.44</td><td><b>0.19</b></td><td><b>0.08</b>*</td></tr><tr><td>AvgTime</td><td>40.65</td><td>46.00</td><td>-</td><td>-</td><td><b>40.54</b></td><td>160.89</td><td>42.62</td><td>116.54</td></tr><tr><td rowspan="4">F</td><td>#Best</td><td>25</td><td>15</td><td>-</td><td>-</td><td>22</td><td><b>25</b></td><td><b>25</b></td><td><b>25</b></td></tr><tr><td>#BestAvg</td><td><b>25</b></td><td>15</td><td>-</td><td>-</td><td>20</td><td>12</td><td><b>25</b></td><td><b>25</b></td></tr><tr><td>AvgGap</td><td><b>0.00</b></td><td>0.90</td><td>-</td><td>-</td><td>0.77</td><td>1.01</td><td><b>0.00</b></td><td><b>0.00</b></td></tr><tr><td>AvgTime</td><td>10.67</td><td>21.09</td><td>-</td><td>-</td><td>52.17</td><td>166.85</td><td><b>8.44</b></td><td><b>8.44</b></td></tr></tbody></table>

HMA₁.

When it comes to computational time ('AvgTime' in Table 3), our HMA algorithm also remains competitive. Recall that the indicated time for the reference algorithms are scaled according to our computer and the average time of a multiple-run algorithm can be compared to the time of a single-run algorithm. Table 3 shows that HMA₁ is in overall not slower than any of the reference algorithms. Compared to the fast GLS, TSA2 and Ant_12 algorithms, HMA₁ generally requires comparable computing time. Compared to the remaining reference algorithms (i.e., VNS, GRASP and MAENS), HMA₁ is clearly more efficient. By extending the stop condition to 2000 generations, HMA₂, which finds improved solutions, consumes more computing time than HMA₁ as expected.

Finally, the "best results" reported by previous CARP studies were often achieved by executing tests involving multiple parameter settings to show the extreme performance of the associated algorithms. Following this practice, we
report in Appendix A some new best known results discovered by our HMA
algorithm with parameter settings other than the standard one given in Table
2. The form of HMA using these additional parameter settings, which we call
HMA*, further attains two new BKRs (for S4-A, S4-B) and matches the BKR
for S3-C, which finally makes HMA* consistently match or improve on *all* 181
BKRs.

5.4 *Comparative results on the EGL-G set*

To test the scalability of HMA, we carried out experiments on the EGL-
G set containing 10 large scale CARP (LSCARP) instances. As stated in
[26], solving LSCARP is much more challenging than solving small-sized or
medium-sized instances since the solution space increases exponentially as the
problem size increases. Compared to the classical instance sets which involve
instances having at most 190 required edges, all instances in EGL-G have
more than 347 required edges. Such a size, as was shown in previous studies
[4, 25], is large enough to pose a scalability challenge to the existing CARP
algorithms. For this reason, a dedicated algorithm called RDG-MAENS [26]
has been proposed specifically for solving LSCARP instances. In this section,
we evaluate the capacity of our HMA algorithm to solve these 10 LSCARP
instances by comparing its performance to those of the current best performing
CARP algorithms including RDG-MAENS.

As before, HMA was executed 30 runs to solve each instance under two ter-
mination criteria: 500 generations (HMA₁) and 2000 generations (HMA₂).
We also report the results obtained by HMA with various other parameter
settings (HMA*). Table 4 summarizes our results on the EGL-G set, along
with those of the current best performing algorithms: TSA1, ILS, MAENS,
RDG-MAENS. In [26], the authors report the results of RDG-MAENS for 6
parameter combinations of (g,α) where g = 2 and 3, α = 1, 5 and 10. We
include the results of the best version (g = 2, α = 10) for our comparative
study. Table 4 lists the average results of each algorithm, the solution time of
HMA, the best lower bounds (LB), the best known results (BKR), and the
best results of HMA. The last two rows show, for each algorithm, the average
of the average gaps to the BKR (*AvgGap*), and the "scaled" average of the
average solution time (*AvgTime*).

Table 4 discloses that HMA₁ dominates all reference algorithms. In terms of
average results, HMA₁ is much better than any of the reference algorithms for
all 10 instances. The very small *AvgGap* value of -0.02% of HMA₁ indicates
that HMA₁ is on average better than the previous BKRs, and compares fa-
vorably to the *AvgGap* value of more than 0.89% for the other approaches.
In terms of best results, HMA₁ discovers an improved solution relative to the
<caption>Table 4</caption>

Comparative results of our HMA algorithm with 4 state-of-the-art algorithms on the 10 instances of EGL-G set. The best average results and best results are in bold. The best result of HMA* is starred if it improves on the BKR.

<table><thead><tr><th rowspan="2">INST</th><th rowspan="2">(|N|, |E<sub>R</sub>|)</th><th colspan="8">Average results</th><th colspan="5">Best results</th></tr><tr><th>TSA1<br>1 run</th><th>ILS<br>10 runs</th><th>MAENS<br>30<br>runs</th><th>RDG<br>30<br>runs</th><th>HMA<sub>1</sub><br>30<br>runs</th><th>Time</th><th>HMA<sub>2</sub><br>30<br>runs</th><th>Time</th><th>LB</th><th>BKR</th><th>HMA<sub>1</sub></th><th>HMA<sub>2</sub></th><th>HMA*</th></tr></thead><tbody><tr><td>G1-A</td><td>(255,347)</td><td>1049708</td><td>1010937.40</td><td>1009302</td><td>1007619</td><td>992823.00</td><td>1221.45</td><td><b>992300.33</b></td><td>3209.16</td><td>976907</td><td>998777</td><td>992337</td><td><b>992045</b></td><td>992045*</td></tr><tr><td>G1-B</td><td>(255,347)</td><td>1140692</td><td>1137141.50</td><td>1128114</td><td>1122863</td><td>1117198.77</td><td>1354.57</td><td><b>1114992.53</b></td><td>3961.81</td><td>1093884</td><td>1111971</td><td>1114125</td><td>1113003</td><td>1112245</td></tr><tr><td>G1-C</td><td>(255,347)</td><td>1282270</td><td>1266576.80</td><td>1255709</td><td>1250174</td><td>1240200.13</td><td>1453.32</td><td><b>1237543.93</b></td><td>4288.60</td><td>1212151</td><td>1241762</td><td>1235062</td><td><b>1233536</b></td><td>1231335*</td></tr><tr><td>G1-D</td><td>(255,347)</td><td>1420126</td><td>1406929.00</td><td>1390034</td><td>1386120</td><td>1374555.27</td><td>1411.71</td><td><b>1371488.53</b></td><td>3768.35</td><td>1341918</td><td>1371443</td><td>1370331</td><td><b>1365259</b></td><td>1365259*</td></tr><tr><td>G1-E</td><td>(255,347)</td><td>1583133</td><td>1554220.20</td><td>1535511</td><td>1525629</td><td>1516790.63</td><td>1338.02</td><td><b>1513731.10</b></td><td>3496.35</td><td>1482176</td><td>1512584</td><td>1511684</td><td><b>1506179</b></td><td>1503871*</td></tr><tr><td>G2-A</td><td>(255,375)</td><td>1129229</td><td>1118363.00</td><td>1109376</td><td>1104944</td><td>1095027.80</td><td>1816.93</td><td><b>1091999.37</b></td><td>4566.27</td><td>1069536</td><td>1094912</td><td>1090595</td><td><b>1088040</b></td><td>1088040*</td></tr><tr><td>G2-B</td><td>(255,375)</td><td>1255907</td><td>1233720.50</td><td>1225361</td><td>1221429</td><td>1206313.77</td><td>1749.72</td><td><b>1201944.50</b></td><td>4972.88</td><td>1185221</td><td>1208326</td><td>1200817</td><td><b>1199877</b></td><td>1199272*</td></tr><tr><td>G2-C</td><td>(255,375)</td><td>1418145</td><td>1374479.70</td><td>1358398</td><td>1355548</td><td>1338918.87</td><td>1646.83</td><td><b>1337615.83</b></td><td>3913.69</td><td>1311339</td><td>1341519</td><td>1334130</td><td><b>1332791</b></td><td>1331646*</td></tr><tr><td>G2-D</td><td>(255,375)</td><td>1516103</td><td>1515119.30</td><td>1500415</td><td>1492063</td><td>1480175.70</td><td>1580.93</td><td><b>1477007.10</b></td><td>4464.64</td><td>1446680</td><td>1481181</td><td>1473099</td><td><b>1471107</b></td><td>1470059*</td></tr><tr><td>G2-E</td><td>(255,375)</td><td>1701681</td><td>1658378.10</td><td>1641260</td><td>1629002</td><td>1618924.97</td><td>1655.15</td><td><b>1615848.83</b></td><td>4407.06</td><td>1581459</td><td>1618899</td><td>1611364</td><td><b>1606807</b></td><td>1606079*</td></tr><tr><td>AvgGap</td><td></td><td>3.94</td><td>2.22</td><td>1.32</td><td>0.89</td><td>-0.02</td><td>-0.22</td><td></td><td></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>AvgTime</td><td></td><td>510.55</td><td>1163.71</td><td>2437.30</td><td>1633.86</td><td>1522.86</td><td>4104.88</td><td></td><td></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

BKRs for 9 out of 10 instances (90%). As the current best and highly specialized algorithm, the best version of the reference algorithm RDG-MAENS is outperformed by $HMA_1$. Moreover, the average computational time of $HMA_1$ is comparable to that of the reference algorithms. $HMA_1$ requires much less time to find substantially better results than MAENS. Compared to the best version of RDG-MAENS, $HMA_1$ is also on average faster (1522.86 vs. 1633.86 seconds). The fact that $HMA_2$ further significantly improves on $HMA_1$ demonstrates that HMA can reach better performance when more computational time is allowed. By testing several other parameter settings, $HMA^*$ further discovers 6 improved best known results.

A Wilcoxon test is finally applied to a pairwise comparison of the average performance between $HMA_1$ and each of the four reference methods, which always results in a p-value of 0.001953 (<0.05) for all tested pairs, indicating the superiority of our method relative to the compared approaches.

## 6 Analysis

In this section, we present additional experimental results to analyze the performance of each algorithmic component of the proposed HMA algorithm, in order to understand their contribution to the overall performance of HMA and how they should be combined in the proposed algorithm. These experiments were performed on the *egl* set which contains a number of challenging instances of medium size, and helps to better distinguish the performance of the algorithm variants to be considered.
Table 5

Analysis of the components of the local refinement procedure using a single solution approach.

<table><thead><tr><th></th><th>IDP</th><th>TTP</th><th>RTTP</th><th>I+R</th><th>RST</th><th>HMA<sub>1</sub></th></tr></thead><tbody><tr><td>BestGap</td><td>4.63</td><td>0.69</td><td>0.65</td><td>0.55</td><td>0.14</td><td>0.01</td></tr><tr><td>AvgGap</td><td>9.30</td><td>1.80</td><td>1.79</td><td>1.80</td><td>0.29</td><td>0.13</td></tr><tr><td>AvgTime</td><td>0.07</td><td>0.98</td><td>0.98</td><td>0.99</td><td>213.02</td><td>198.83</td></tr></tbody></table>

## 6.1 Analysis of algorithmic components

To provide insight of the performance of the local refinement procedure and the crossover operator, we test in this experiment several algorithm variants based on a single solution rather than a population of solutions. The "IDP" version is a very simple algorithm having only solution initialization (random path scanning) and IDP as its two components. Similar to "IDP", the "RTTP" version includes only the solution initialization and the RTTP procedure. The "TTP" version is exactly the same as "RTTP" except that the move operators are used in a fixed order as they are presented in Section 4.1. The "I+R" version combines IDP and RTTP in random order. The "RST" version is a random restart algorithm that simply starts "I+R" for 500 times. We also include the results of $HMA_1$ (500 generations) for comparative purposes. For each algorithm variant, we report in Table 5 the average of the best gap to the BKR in percentage (BestGap), and the average of the average gap to the BKR in percentage (AvgGap), as well as the average computing time in seconds (AvgTime).

Table 5 shows that TTP performs much better than IDP. RTTP further improves on TTP which shows the effectiveness of the random use of move operators. The results of "I+R" indicates that though RTTP is a very crucial component, its performance can be still ameliorated by a random collaboration with IDP. The comparative results of RST and $HMA_1$ clearly shows the relevance of the crossover operator and the population-based framework.

## 6.2 Analysis under the population-based framework

Given that both the local refinement procedures and the crossover operator are effective, this part of analysis investigates how they should be combined to achieve the best performance. For this purpose, we propose another set of algorithm variants based on a population of solutions. The "XO+I" version is obtained by removing the RTTP procedure from $HMA$, "XO+R" version by removing IDP from $HMA$. "XO+I→R" version works all the same as $HMA$, except that the order of using IDP and RTTP is fixed to $I→R$. Similarly, "XO+R→I" uses the order $R→I$. Table 6 summarizes the results of these
<caption>Table 6</caption>

Analysis of different combinations of the crossover operator and the local refinement procedure using a population of solutions.

<table><caption>Table 7</caption><thead><tr><th></th><th>XO+I</th><th>XO+R</th><th>XO+I→R</th><th>XO+R→I</th><th>HMA<sub>1</sub></th></tr></thead><tbody><tr><th>BestGap</th><td>0.72</td><td>0.02</td><td>0.02</td><td>0.04</td><td>0.01</td></tr><tr><th>AvgGap</th><td>1.59</td><td>0.16</td><td>0.16</td><td>0.15</td><td>0.13</td></tr><tr><th>AvgTime</th><td>6.77</td><td>254.11</td><td>158.37</td><td>244.20</td><td>198.83</td></tr></tbody></table>

Analysis of the quality-and-distance pool updating strategy.

<table><thead><tr><th></th><th>HMA<sub>PW1</sub></th><th>HMA<sub>1</sub></th><th>HMA<sub>PW2</sub></th><th>HMA<sub>2</sub></th></tr></thead><tbody><tr><th>BestGap</th><td>0.02</td><td>0.01</td><td>0.00</td><td>-0.04</td></tr><tr><th>AvgGap</th><td>0.15</td><td>0.13</td><td>0.10</td><td>0.07</td></tr><tr><th>AvgTime</th><td>188.15</td><td>198.83</td><td>437.34</td><td>646.03</td></tr></tbody></table>

algorithm variants, along with those of HMA₁. Without surprise, using only IDP in the local refinement procedure shows a rather poor performance, while employing RTTP in the local refinement procedure leads to a much better performance. Compared to "XO+R", including an additional IDP in the local refinement procedure never leads to a definitely better performance if the order of using IDP and RTTP is fixed. However, if IDP and RTTP are used in a random order as in HMA, a better performance can be observed in terms of both BestGap and AvgGap.

## 6.3 Analysis on the pool updating strategy

The third part of the analysis investigates the effectiveness of our pool updating strategy, which uses the hamming distance to control the diversity of the population. We therefore compare the adopted strategy to a traditional "pool worst" strategy which simply replaces the worst solution in terms of fitness in the population, leading to an algorithm variant denoted as HMA<sub>PW</sub>. HMA<sub>PW</sub> was tested under two termination criteria: 500 generations (HMA<sub>PW1</sub>) and 2000 generations (HMA<sub>PW2</sub>), and the outcomes are compared to those of HMA₁ and HMA₂. The computational results are summarized in Table 7, from which we can clearly see that HMA₁ performs better than HMA<sub>PW1</sub>, and the superiority of HMA₂ relative to HMA<sub>PW2</sub> enlarges when more computing time is allowed. This experiment confirms the usefulness of the diversity control mechanism used in our HMA.
# 7 Conclusions

The capacitated arc routing problem (CARP) is of great practical interest and represents a significant computational challenge due to its NP-hardness. We developed a new hybrid metaheuristic approach (HMA) for effectively solving CARP, which employs a randomized tabu thresholding procedure (RTTP) coupled with an infeasible descent procedure to explore both feasible and infeasible regions. HMA relies on a specialized route-based crossover operator to generate diversified and promising new solutions. Thanks to its quality- and-distance based pool updating strategy, HMA prevents the search process from premature convergence.

The proposed approach demonstrates an excellent performance over the eight sets of 191 popular CARP benchmarks. Specifically, on the 7 sets of 181 classical instances, HMA with a standard parameter setting outperforms the current best performing algorithms, in terms of both solution quality and computational efficiency. HMA further improves its own performance when more computing time is available (to run 2000 generations), attaining the best known results for all 181 cases including 6 improved new best results. HMA also proves to be scalable to handle the last set of 10 large-sized instances, by obtaining 9 new best results, dominating the current state-of-the-art algorithms including the approaches which were specially designed for the large-sized CARP instances. We additionally conducted experiments to analyze the contribution of the two sub-procedures for local refinement, the relevance of the route-based crossover operator (and thus the population-based framework), the strategy for combining crossover with the local optimization procedure, as well as the quality-and-distance pool updating strategy.

Finally, we observe that the proposed method can be adapted to handle other CARP variants with slight modifications of the route-based crossover operator and of the local refinement procedure to accommodate additional constraints.

# Acknowledgment

We are grateful to the anonymous referees for their valuable suggestions and comments which helped us to improve the paper. The work is partially supported by the PGMO (2014-0024H) project from the Jacques Hadamard Mathematical Foundation and the National Natural Science Foundation of China (Grants 61473301, 71201171, 71501179). Support for Yuning Chen from the China Scholarship Council is also acknowledged.
References

[1] Benavent E., Campos V., Corberan E., Mota E. The capacitated arc routing problem: lower bounds. Networks 1992; 22(4) 669-690.

[2] Beullens P., Muyldermans L., Cattrysse D., Van Oudheusden D. A guided local search heuristic for the capacitated arc routing problem. European Journal of Operational Research 2003; 147(3): 629-643.

[3] Baldacci R., Maniezzo V. Exact methods based on noderouting formulations for undirected arcrouting problems. Networks 2006; 47(1): 52-60.

[4] Brandão J., Eglese R. A deterministic tabu search algorithm for the capacitated arc routing problem. Computers & Operations Research 2008; 35(4): 1112-1126.

[5] Birattari M., Yuan Z., Balaprakash P., Stützle T. F-Race and iterated F-Race: An overview. Experimental methods for the analysis of optimization algorithms 2010; Berlin, Germany: Springer, pp. 311-336.

[6] Bartolini E., Cordeau J.F., Laporte G. Improved lower bounds and exact algorithm for the capacitated arc routing problem. Mathematical Programming 2013; 137(1-2): 409-452.

[7] Bode C., Irnich S. Cut-first branch-and-price-second for the capacitated arc-routing problem. Operations research 2012; 60(5): 1167-1182.

[8] Corberán Á., Laporte G. Arc routing: problems, methods, and applications. MOS-SIAM Series on Optimization, Vol. 20. SIAM, 2015.

[9] DeArmon J. S. A comparison of heuristics for the capacitated Chinese postman problems. Master thesis, University of Maryland, College Park, MD, 1981.

[10] Dror, M. Arc Routing: Theory, Solutions and Applications. Kluwer Academic Publishers 2000.

[11] Eglese R.W. Routing Winter Gritting Vehicles. Discrete Applied Mathematics 1994; 48(3): 231-244.

[12] Golden B. L. and Wong R. T. Capacitated arc routing problems. Networks 1981; 11(3): 305-315.

[13] Glover F. Tabu thresholding: Improved search by nonmonotonic trajectories. ORSA Journal on Computing 1995; 7(4): 426-442.

[14] Glover F., Kochenberger G. (Eds.). Handbook of Metaheuristics, Kluwer, Norwell, Massachusetts, USA. 2003.

[15] Glover F., Hao J.K. The case for strategic oscillation. Annals of Operations Research 2011; 183(1): 163-173.

[16] Glover F, Laguna M. Tabu search. Kluwer Academic Publishers 1997.

[17] Golden B. L., DeArmon J. S., Baker E. K. Computational experiments with algorithms for a class of routing problems. Computers & Operations Research 1983; 10(1): 47-59.

[18] Hao J.K. Memetic algorithms in discrete optimization. In Neri F., Cotta C., Moscato P.(Eds.) Handbook of Memetic Algorithms. Studies in Computational Intelligence 379, Chapter 6, pages 7394, 2012.
[19] Hertz A., Laporte G., Mittaz M. A tabu search heuristic for the capacitated arc routing problem. Operations research 2000; 48(1): 129-135.

[20] Hertz A., Mittaz M. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem. Transportation science 2001; 35(4): 425-434.

[21] Kirkpatrick S., Vecchi M. P. Optimization by simulated annealing. Science 1983; 220(4598), 671-680.

[22] Lacomme P., Prins C., Ramdane-Cherif W. Competitive memetic algorithms for arc routing problems. Annals of Operations Research 2004; 131(1-4): 159-185.

[23] López-Ibáñez M., Dubois-Lacoste J., Stützle T., Birattari M. The irace package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Universit Libre de Bruxelles, Belgium.

[24] Mei Y., Tang K., Yao X. A global repair operator for capacitated arc routing problem. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 2009; 39(3): 723-734.

[25] Martinelli R., Poggi M., Subramanian A. Improved Bounds for Large Scale Capacitated Arc Routing Problem. Computers & Operations Research 2013; 40(8): 2145-2160.

[26] Mei Y., Li X., Yao X. Cooperative coevolution with route distance grouping for large-scale capacitated arc routing problems. IEEE Transactions on Evolutionary Computation 2014; 18(3): 435-449.

[27] Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Report, 826, 1989.

[28] Moscato P., Cotta C. A Gentle Introduction to Memetic Algorithms. In Glover F. and Kochenberger G. A. (Eds.), Handbook of Metaheuristics. Kluwer, Norwell, Massachusetts, USA, 2003.

[29] Neri F., Cotta C., Moscato P. (Eds.) Handbook of Memetic Algorithms. Studies in Computational Intelligence 379, Springer, 2011.

[30] Polacek M., Doerner K.F., Hartl R.F., Maniezzo V. A variable neighborhood search for the capacitated arc routing problem with intermediate facilities. Journal of Heuristics 2008, 14(5), 405-423.

[31] Potvin J. Y., Bengio S. The vehicle routing problem with time windows part II: genetic search. INFORMS journal on Computing 1996; 8(2): 165-172.

[32] Santos L., Coutinho-Rodrigues J., Current J. R. An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Research Part B: Methodological 2010; 44(2): 246-266.

[33] Stern H. I., Dror M. Routing electric meter readers. Computers & Operations Research 1979; 6(4): 209-223.

[34] Tang K., Mei Y., Yao X. Memetic algorithm with extended neighborhood search for capacitated arc routing problems. IEEE Transactions on Evolutionary Computation 2009; 13(5): 1151-1166.

[35] Ulusoy, G. The fleet size and mix problem for capacitated arc routing. European Journal of Operational Research 1985; 22(3): 329-337.
<caption>Table A.1</caption>

Detailed comparative results of HMA algorithm with five state-of-the-art algorithms on the 23 instances of Set gdb. The average results of all algorithms and the best results of HMA₁ (500 generations) are highlighted in bold if they match the BKRs.

<table><thead><tr><th rowspan="2">INST</th><th rowspan="2">(|N|, |E|)</th><th colspan="7">Average (median) results</th><th colspan="2">Best results</th></tr><tr><th>GLS 1 run</th><th>TSA2 1 run</th><th>Ant_12 10 runs</th><th>GRASP 15 runs</th><th>MAENS 30 runs</th><th>HMA<sub>1</sub> 30 runs</th><th>Time</th><th>BKR</th><th>HMA<sub>1</sub></th></tr></thead><tbody><tr><td>1</td><td>(12,22)</td><td><strong>316</strong></td><td><strong>316</strong></td><td><strong>316</strong></td><td><strong>316.00</strong></td><td><strong>316.00</strong></td><td><strong>316.00</strong></td><td>0.09</td><td><strong>316</strong></td><td><strong>316</strong></td></tr><tr><td>2</td><td>(12,26)</td><td><strong>339</strong></td><td><strong>339</strong></td><td><strong>339</strong></td><td><strong>339.00</strong></td><td><strong>339.00</strong></td><td><strong>339.00</strong></td><td>0.16</td><td><strong>339</strong></td><td><strong>339</strong></td></tr><tr><td>3</td><td>(12,22)</td><td><strong>275</strong></td><td><strong>275</strong></td><td><strong>275</strong></td><td><strong>275.00</strong></td><td><strong>275.00</strong></td><td><strong>275.00</strong></td><td>0.09</td><td><strong>275</strong></td><td><strong>275</strong></td></tr><tr><td>4</td><td>(11,19)</td><td><strong>287</strong></td><td><strong>287</strong></td><td><strong>287</strong></td><td><strong>287.00</strong></td><td><strong>287.00</strong></td><td><strong>287.00</strong></td><td>0.08</td><td><strong>287</strong></td><td><strong>287</strong></td></tr><tr><td>5</td><td>(13,26)</td><td><strong>377</strong></td><td><strong>377</strong></td><td><strong>377</strong></td><td><strong>377.00</strong></td><td><strong>377.00</strong></td><td><strong>377.00</strong></td><td>0.13</td><td><strong>377</strong></td><td><strong>377</strong></td></tr><tr><td>6</td><td>(12,22)</td><td><strong>298</strong></td><td><strong>298</strong></td><td><strong>298</strong></td><td><strong>298.00</strong></td><td><strong>298.00</strong></td><td><strong>298.00</strong></td><td>0.13</td><td><strong>298</strong></td><td><strong>298</strong></td></tr><tr><td>7</td><td>(12,22)</td><td><strong>325</strong></td><td><strong>325</strong></td><td><strong>325</strong></td><td><strong>325.00</strong></td><td><strong>325.00</strong></td><td><strong>325.00</strong></td><td>0.09</td><td><strong>325</strong></td><td><strong>325</strong></td></tr><tr><td>8</td><td>(27,46)</td><td><strong>348</strong></td><td><strong>348</strong></td><td><strong>348</strong></td><td>349.50</td><td>348.70</td><td><strong>348.00</strong></td><td>14.01</td><td><strong>348</strong></td><td><strong>348</strong></td></tr><tr><td>9</td><td>(27,51)</td><td><strong>303</strong></td><td><strong>303</strong></td><td><strong>303</strong></td><td>303.60</td><td><strong>303.00</strong></td><td><strong>303.00</strong></td><td>3.20</td><td><strong>303</strong></td><td><strong>303</strong></td></tr><tr><td>10</td><td>(12,25)</td><td><strong>275</strong></td><td><strong>275</strong></td><td><strong>275</strong></td><td><strong>275.00</strong></td><td><strong>275.00</strong></td><td><strong>275.00</strong></td><td>0.12</td><td><strong>275</strong></td><td><strong>275</strong></td></tr><tr><td>11</td><td>(22,45)</td><td><strong>395</strong></td><td><strong>395</strong></td><td><strong>395</strong></td><td><strong>395.00</strong></td><td><strong>395.00</strong></td><td><strong>395.00</strong></td><td>0.34</td><td><strong>395</strong></td><td><strong>395</strong></td></tr><tr><td>12</td><td>(13,23)</td><td><strong>458</strong></td><td><strong>458</strong></td><td><strong>458</strong></td><td><strong>458.00</strong></td><td><strong>458.00</strong></td><td><strong>458.00</strong></td><td>0.24</td><td><strong>458</strong></td><td><strong>458</strong></td></tr><tr><td>13</td><td>(10,28)</td><td><strong>536</strong></td><td><strong>540</strong></td><td><strong>544</strong></td><td><strong>542.60</strong></td><td><strong>536.00</strong></td><td><strong>536.00</strong></td><td>6.59</td><td><strong>536</strong></td><td><strong>536</strong></td></tr><tr><td>14</td><td>(7,21)</td><td><strong>100</strong></td><td><strong>100</strong></td><td><strong>100</strong></td><td><strong>100.00</strong></td><td><strong>100.00</strong></td><td><strong>100.00</strong></td><td>0.11</td><td><strong>100</strong></td><td><strong>100</strong></td></tr><tr><td>15</td><td>(7,21)</td><td><strong>58</strong></td><td><strong>58</strong></td><td><strong>58</strong></td><td><strong>58.00</strong></td><td><strong>58.00</strong></td><td><strong>58.00</strong></td><td>0.10</td><td><strong>58</strong></td><td><strong>58</strong></td></tr><tr><td>16</td><td>(8,28)</td><td><strong>127</strong></td><td><strong>127</strong></td><td><strong>127</strong></td><td><strong>127.00</strong></td><td><strong>127.00</strong></td><td><strong>127.00</strong></td><td>0.14</td><td><strong>127</strong></td><td><strong>127</strong></td></tr><tr><td>17</td><td>(8,28)</td><td><strong>91</strong></td><td><strong>91</strong></td><td><strong>91</strong></td><td><strong>91.00</strong></td><td><strong>91.00</strong></td><td><strong>91.00</strong></td><td>0.13</td><td><strong>91</strong></td><td><strong>91</strong></td></tr><tr><td>18</td><td>(9,36)</td><td><strong>164</strong></td><td><strong>164</strong></td><td><strong>164</strong></td><td><strong>164.00</strong></td><td><strong>164.00</strong></td><td><strong>164.00</strong></td><td>0.16</td><td><strong>164</strong></td><td><strong>164</strong></td></tr><tr><td>19</td><td>(8,11)</td><td><strong>55</strong></td><td><strong>55</strong></td><td><strong>55</strong></td><td><strong>55.00</strong></td><td><strong>55.00</strong></td><td><strong>55.00</strong></td><td>0.05</td><td><strong>55</strong></td><td><strong>55</strong></td></tr><tr><td>20</td><td>(11,22)</td><td><strong>121</strong></td><td><strong>121</strong></td><td><strong>121</strong></td><td><strong>121.00</strong></td><td><strong>121.00</strong></td><td><strong>121.00</strong></td><td>0.12</td><td><strong>121</strong></td><td><strong>121</strong></td></tr><tr><td>21</td><td>(11,33)</td><td><strong>156</strong></td><td><strong>156</strong></td><td><strong>156</strong></td><td><strong>156.00</strong></td><td><strong>156.00</strong></td><td><strong>156.00</strong></td><td>0.19</td><td><strong>156</strong></td><td><strong>156</strong></td></tr><tr><td>22</td><td>(11,44)</td><td><strong>200</strong></td><td><strong>200</strong></td><td><strong>200</strong></td><td><strong>200.00</strong></td><td><strong>200.00</strong></td><td><strong>200.00</strong></td><td>0.33</td><td><strong>200</strong></td><td><strong>200</strong></td></tr><tr><td>23</td><td>(11,55)</td><td><strong>233</strong></td><td><strong>235</strong></td><td><strong>235</strong></td><td><strong>234.70</strong></td><td><strong>233.00</strong></td><td><strong>233.00</strong></td><td>0.71</td><td><strong>233</strong></td><td><strong>233</strong></td></tr><tr><td>AvgGap</td><td></td><td>0.00</td><td>0.07</td><td>0.10</td><td>0.11</td><td>0.01</td><td>0.00</td><td></td><td>-</td><td>-</td></tr><tr><td>AvgTime (scaled)</td><td></td><td>0.32</td><td>1.23</td><td>1.21</td><td>5.47</td><td>4.47</td><td>1.19</td><td></td><td>-</td><td>-</td></tr></tbody></table>

[36] Usberti F.L., Paulo M.F., André L.M.F. GRASP with evolutionary path-relinking for the capacitated arc routing problem. Computers & Operations Research 2013; 40(12): 3206-3217.

## A Appendix

This appendix shows the detailed results of our HMA algorithm on the 181 conventional CARP instances (Table A.1–A.7). We also include in Table A.3 the new best known results (BKRs) discovered by HMA on *egl* instances with various parameter settings (indicated by HMA*) other than the standard setting given in Table 2.
<table><caption>Table A.2 Detailed comparative results of HMA algorithm with 6 state-of-the-art algorithms on the 34 instances of Set val. The average results of all algorithms and the best results of HMA₁ (500 generations) and HMA₂ (2000 generations) are highlighted in bold if they match the BKRs. The optimal BKRs are underlined.</caption><thead><tr><th rowspan="2"></th><th rowspan="2">INST</th><th rowspan="2">(N<sub>t</sub>, E<sub>t</sub>)</th><th colspan="10">Average (median) results</th><th colspan="2">Best results</th></tr><tr><th>GLS<br>1 run</th><th>TSA2<br>1 run</th><th>VNS<br>10 runs</th><th>Ant.12<br>10 runs</th><th>GRASP<br>15 runs</th><th>MAENS<br>30 runs</th><th>HMA1<br>30 runs</th><th>Time<br>30 runs</th><th>HMA2<br>30 runs</th><th>Time<br>30 runs</th><th>BKR</th><th>HMA1</th><th>HMA2</th></tr></thead><tbody><tr><td>1A</td><td>(24.39)</td><td>173</td><td>173.00</td><td>173</td><td>173</td><td>173.00</td><td>173.00</td><td>173.00</td><td>0.28</td><td>173.00</td><td>0.28</td><td>173</td><td>173</td><td>173</td></tr><tr><td>1B</td><td>(24.39)</td><td>173</td><td>173.00</td><td>173</td><td>173</td><td>173.00</td><td>173.00</td><td>173.00</td><td>0.33</td><td>173.00</td><td>0.33</td><td>173</td><td>173</td><td>173</td></tr><tr><td>1C</td><td>(24.39)</td><td>245</td><td>245.00</td><td>245</td><td>245.00</td><td>245.00</td><td>245.00</td><td>245.00</td><td>0.43</td><td>245.00</td><td>0.43</td><td>245</td><td>245</td><td>245</td></tr><tr><td>2A</td><td>(24.34)</td><td>227</td><td>227.00</td><td>227</td><td>227.00</td><td>227.00</td><td>227.00</td><td>227.00</td><td>0.16</td><td>227.00</td><td>0.16</td><td>227</td><td>227</td><td>227</td></tr><tr><td>2B</td><td>(24.34)</td><td>259</td><td>259.00</td><td>259</td><td>259.00</td><td>259.00</td><td>259.00</td><td>259.00</td><td>6.37</td><td>259.00</td><td>6.37</td><td>259</td><td>259</td><td>259</td></tr><tr><td>2C</td><td>(24.34)</td><td>457</td><td>457.00</td><td>457</td><td>457.30</td><td>457.20</td><td>457.17</td><td>10.18</td><td>457.00</td><td>12.90</td><td>457</td><td>457</td><td>457</td><td>457</td></tr><tr><td>3A</td><td>(24.35)</td><td>81</td><td>81.00</td><td>81</td><td>81.00</td><td>81.00</td><td>81.00</td><td>0.17</td><td>81.00</td><td>0.17</td><td>81</td><td>81</td><td>81</td><td>81</td></tr><tr><td>3B</td><td>(24.35)</td><td>87</td><td>87.00</td><td>87</td><td>87.00</td><td>87.00</td><td>87.00</td><td>0.25</td><td>87.00</td><td>0.25</td><td>87</td><td>87</td><td>87</td><td>87</td></tr><tr><td>3C</td><td>(24.35)</td><td>138</td><td>138.00</td><td>138</td><td>138.00</td><td>138.00</td><td>138.00</td><td>0.31</td><td>138.00</td><td>0.31</td><td>138</td><td>138</td><td>138</td><td>138</td></tr><tr><td>4A</td><td>(41.69)</td><td>400</td><td>400.00</td><td>400</td><td>400.00</td><td>400.00</td><td>400.00</td><td>0.43</td><td>400.00</td><td>0.43</td><td>400</td><td>400</td><td>400</td><td>400</td></tr><tr><td>4B</td><td>(41.69)</td><td>412</td><td>412.00</td><td>412</td><td>412.00</td><td>412.00</td><td>412.00</td><td>412.00</td><td>0.44</td><td>412.00</td><td>0.44</td><td>412</td><td>412</td><td>412</td></tr><tr><td>4C</td><td>(41.69)</td><td>428</td><td>428.00</td><td>428</td><td>430.30</td><td>431.10</td><td>428.00</td><td>1.22</td><td>428.00</td><td>1.22</td><td>428</td><td>428</td><td>428</td><td>428</td></tr><tr><td>4D</td><td>(41.69)</td><td>530</td><td>530.20</td><td>530</td><td>531.00</td><td>532.90</td><td>530.00</td><td>6.39</td><td>529.87</td><td>17.57</td><td>528</td><td>530</td><td>528</td><td>528</td></tr><tr><td>5A</td><td>(34.65)</td><td>423</td><td>423.00</td><td>423</td><td>423.00</td><td>423.00</td><td>423.00</td><td>0.49</td><td>423.00</td><td>0.49</td><td>423</td><td>423</td><td>423</td><td>423</td></tr><tr><td>5B</td><td>(34.65)</td><td>446</td><td>446.00</td><td>446</td><td>446.00</td><td>446.00</td><td>446.00</td><td>0.41</td><td>446.00</td><td>0.41</td><td>446</td><td>446</td><td>446</td><td>446</td></tr><tr><td>5C</td><td>(34.65)</td><td>474</td><td>474.00</td><td>474</td><td>474.00</td><td>474.00</td><td>474.00</td><td>0.48</td><td>474.00</td><td>0.48</td><td>474</td><td>474</td><td>474</td><td>474</td></tr><tr><td>5D</td><td>(34.65)</td><td>579</td><td>583</td><td>579.80</td><td>583</td><td>584.50</td><td>582.90</td><td>576.33</td><td>59.65</td><td>575.60</td><td>210.21</td><td>575</td><td>575</td><td>575</td></tr><tr><td>6A</td><td>(31.50)</td><td>223</td><td>223.00</td><td>223</td><td>223.00</td><td>223.00</td><td>223.00</td><td>0.25</td><td>223.00</td><td>0.25</td><td>223</td><td>223</td><td>223</td><td>223</td></tr><tr><td>6B</td><td>(31.50)</td><td>233</td><td>233.00</td><td>233</td><td>233.00</td><td>233.00</td><td>233.00</td><td>0.82</td><td>233.00</td><td>0.82</td><td>233</td><td>233</td><td>233</td><td>233</td></tr><tr><td>6C</td><td>(31.50)</td><td>317</td><td>317.00</td><td>317</td><td>317.00</td><td>317.00</td><td>317.00</td><td>0.54</td><td>317.00</td><td>0.54</td><td>317</td><td>317</td><td>317</td><td>317</td></tr><tr><td>7A</td><td>(40.66)</td><td>283</td><td>283.00</td><td>283</td><td>283.00</td><td>283.00</td><td>283.00</td><td>0.37</td><td>283.00</td><td>0.37</td><td>283</td><td>283</td><td>283</td><td>283</td></tr><tr><td>7B</td><td>(40.66)</td><td>334</td><td>334.00</td><td>334</td><td>334.00</td><td>334.00</td><td>334.00</td><td>0.48</td><td>334.00</td><td>0.48</td><td>334</td><td>334</td><td>334</td><td>334</td></tr><tr><td>7C</td><td>(40.66)</td><td>334</td><td>334.00</td><td>334</td><td>334.00</td><td>334.00</td><td>334.00</td><td>0.48</td><td>334.00</td><td>0.48</td><td>334</td><td>334</td><td>334</td><td>334</td></tr><tr><td>8A</td><td>(30.63)</td><td>386</td><td>386.00</td><td>386</td><td>386.00</td><td>386.00</td><td>386.00</td><td>0.39</td><td>386.00</td><td>0.39</td><td>386</td><td>386</td><td>386</td><td>386</td></tr><tr><td>8B</td><td>(30.63)</td><td>395</td><td>395.00</td><td>395</td><td>395.00</td><td>395.00</td><td>395.00</td><td>0.43</td><td>395.00</td><td>0.43</td><td>395</td><td>395</td><td>395</td><td>395</td></tr><tr><td>8C</td><td>(30.63)</td><td>521</td><td>522.00</td><td>527</td><td>526.50</td><td>525.90</td><td>521.00</td><td>58.00</td><td>521.00</td><td>58.00</td><td>521</td><td>521</td><td>521</td><td>521</td></tr><tr><td>9A</td><td>(50.92)</td><td>323</td><td>323.00</td><td>323</td><td>323.00</td><td>323.00</td><td>323.00</td><td>1.09</td><td>323.00</td><td>1.09</td><td>323</td><td>323</td><td>323</td><td>323</td></tr><tr><td>9B</td><td>(50.92)</td><td>326</td><td>326.00</td><td>326</td><td>326.00</td><td>326.00</td><td>326.00</td><td>0.83</td><td>326.00</td><td>0.83</td><td>326</td><td>326</td><td>326</td><td>326</td></tr><tr><td>9C</td><td>(50.92)</td><td>332</td><td>332.00</td><td>332</td><td>332.00</td><td>332.00</td><td>332.00</td><td>0.88</td><td>332.00</td><td>0.88</td><td>332</td><td>332</td><td>332</td><td>332</td></tr><tr><td>10A</td><td>(50.97)</td><td>428</td><td>428.40</td><td>428</td><td>428.40</td><td>428.00</td><td>428.00</td><td>1.52</td><td>428.00</td><td>1.52</td><td>428</td><td>428</td><td>428</td><td>428</td></tr><tr><td>10B</td><td>(50.97)</td><td>436</td><td>436.60</td><td>436</td><td>436.00</td><td>436.00</td><td>436.00</td><td>2.45</td><td>436.00</td><td>2.45</td><td>436</td><td>436</td><td>436</td><td>436</td></tr><tr><td>10C</td><td>(50.97)</td><td>446</td><td>447.00</td><td>446</td><td>446.20</td><td>446.00</td><td>446.00</td><td>1.78</td><td>446.00</td><td>1.78</td><td>446</td><td>446</td><td>446</td><td>446</td></tr><tr><td>10D</td><td>(50.97)</td><td>526</td><td>530</td><td>526.90</td><td>528</td><td>530.60</td><td>533.60</td><td>111.37</td><td>526.00</td><td>194.26</td><td>525</td><td>526</td><td>525</td><td>525</td></tr><tr><td>AvgGap</td><td></td><td>0.05</td><td>0.14</td><td>0.09</td><td>0.12</td><td>0.18</td><td>0.03</td><td></td><td>0.02</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>AvgTime (scaled)</td><td></td><td>14.64</td><td>10.09</td><td>56.70</td><td>9.11</td><td>65.85</td><td>48.35</td><td>11.23</td><td>26.71</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
<caption>Table A.3</caption>

Detailed comparative results of HMA algorithm with five state-of-the-art algorithms on the 24 instances of Set egl. The average results of all algorithms and the best results of HMA₁ (500 generations) and HMA₂ (2000 generations) are highlighted in bold if they match the BKRs. The best results of HMA* are starred if they are new BKRs. The optimal BKRs are underlined.

<table><thead><tr><th rowspan="2"></th><th rowspan="2">INST</th><th rowspan="2">(N, |E|)</th><th colspan="10">Average (median) results</th><th colspan="4">Best results</th></tr><tr><th>TSA2<br>1 run</th><th>VNS<br>10 runs</th><th>Ant.12<br>10 runs</th><th>GRASP<br>15 runs</th><th>MAENS<br>30 runs</th><th>HMA1<br>30 runs</th><th>Time</th><th>HMA2<br>30 runs</th><th>Time</th><th>LB</th><th>BKR</th><th>HMA1</th><th>HMA2</th><th>HMA*</th></tr></thead><tbody><tr><td>E1-A</td><td>(77,98)</td><td>3548</td><td>3548.00</td><td>3548</td><td>3548.00</td><td>3548.00</td><td>3548.00</td><td>0.58</td><td>3548.00</td><td>0.58</td><td>3548</td><td>3548</td><td>3548</td><td>3548</td><td>3548</td></tr><tr><td>E1-B</td><td>(77,98)</td><td>4533</td><td>4522.20</td><td>4539</td><td>4508.60</td><td>4516.50</td><td>4498.00</td><td>9.62</td><td>4498.00</td><td>9.62</td><td>4498</td><td>4498</td><td>4498</td><td>4498</td><td>4498</td></tr><tr><td>E1-C</td><td>(77,98)</td><td>5595</td><td>5608.00</td><td>5595</td><td>5615.30</td><td>5601.60</td><td>5595.00</td><td>8.71</td><td>5595.00</td><td>8.71</td><td>5595</td><td>5595</td><td>5595</td><td>5595</td><td>5595</td></tr><tr><td>E2-A</td><td>(77,98)</td><td>5018</td><td>5023.80</td><td>5018</td><td>5018.00</td><td>5018.00</td><td>5018.00</td><td>24.08</td><td>5018.00</td><td>24.08</td><td>5018</td><td>5018</td><td>5018</td><td>5018</td><td>5018</td></tr><tr><td>E2-B</td><td>(77,98)</td><td>6343</td><td>6335.40</td><td>6344</td><td>6330.70</td><td>6341.40</td><td>6319.77</td><td>44.29</td><td>6317.00</td><td>104.93</td><td>6317</td><td>6317</td><td>6317</td><td>6317</td><td>6317</td></tr><tr><td>E2-C</td><td>(77,98)</td><td>8347</td><td>8355.90</td><td>8335</td><td>8335.80</td><td>8355.70</td><td>8335.00</td><td>28.12</td><td>8335.00</td><td>28.12</td><td>8335</td><td>8335</td><td>8335</td><td>8335</td><td>8335</td></tr><tr><td>E3-A</td><td>(77,98)</td><td>5902</td><td>5898.00</td><td>5898</td><td>5898.00</td><td>5898.80</td><td>5898.00</td><td>5.35</td><td>5898.00</td><td>5.35</td><td>5898</td><td>5898</td><td>5898</td><td>5898</td><td>5898</td></tr><tr><td>E3-B</td><td>(77,98)</td><td>7816</td><td>7806.40</td><td>7787</td><td>7787.30</td><td>7802.90</td><td>7777.00</td><td>76.19</td><td>7776.93</td><td>98.19</td><td>7775</td><td>7775</td><td>7777</td><td>7775</td><td>7775</td></tr><tr><td>E3-C</td><td>(77,98)</td><td>10309</td><td>10322.30</td><td>10292</td><td>10296.50</td><td>10321.90</td><td>10294.43</td><td>133.00</td><td>10292.00</td><td>177.41</td><td>10244</td><td>10292</td><td>10292</td><td>10292</td><td>10292</td></tr><tr><td>E4-A</td><td>(77,98)</td><td>6473</td><td>6459.40</td><td>6464</td><td>6461.10</td><td>6475.20</td><td>6461.17</td><td>82.61</td><td>6450.57</td><td>675.30</td><td>6408</td><td>6444</td><td>6446</td><td>6444</td><td>6444</td></tr><tr><td>E4-B</td><td>(77,98)</td><td>9063</td><td>9016.30</td><td>9047</td><td>9037.10</td><td>9023.00</td><td>8991.50</td><td>143.63</td><td>8987.00</td><td>454.17</td><td>8935</td><td>8961</td><td>8972</td><td>8961</td><td>8961</td></tr><tr><td>E4-C</td><td>(77,98)</td><td>11627</td><td>11750.10</td><td>11645</td><td>11670.00</td><td>11645.80</td><td>11582.40</td><td>203.43</td><td>11563.97</td><td>511.24</td><td>11512</td><td>11529</td><td>11545</td><td>11529</td><td>11529</td></tr><tr><td>S1-A</td><td>(140,190)</td><td>5072</td><td>5018.00</td><td>5018</td><td>5038.90</td><td>5039.80</td><td>5018.00</td><td>11.98</td><td>5018.00</td><td>11.98</td><td>5018</td><td>5018</td><td>5018</td><td>5018</td><td>5018</td></tr><tr><td>S1-B</td><td>(140,190)</td><td>6388</td><td>6388.00</td><td>6388</td><td>6388.40</td><td>6433.40</td><td>6388.00</td><td>36.29</td><td>6388.00</td><td>36.29</td><td>6388</td><td>6388</td><td>6388</td><td>6388</td><td>6388</td></tr><tr><td>S1-C</td><td>(140,190)</td><td>8535</td><td>8518.20</td><td>8518</td><td>8521.50</td><td>8518.30</td><td>8518.00</td><td>21.59</td><td>8518.00</td><td>21.59</td><td>8518</td><td>8518</td><td>8518</td><td>8518</td><td>8518</td></tr><tr><td>S2-A</td><td>(140,190)</td><td>10038</td><td>9997.90</td><td>9974</td><td>9980.50</td><td>9959.20</td><td>9907.23</td><td>390.84</td><td>9891.33</td><td>1887.59</td><td>9825</td><td>9884</td><td>9888</td><td>9874</td><td>9874*</td></tr><tr><td>S2-B</td><td>(140,190)</td><td>13178</td><td>13176.00</td><td>13283</td><td>13240.60</td><td>13231.60</td><td>13149.97</td><td>361.66</td><td>13153.70</td><td>597.74</td><td>13017</td><td>13099</td><td>13111</td><td>13078*</td><td>13078*</td></tr><tr><td>S2-C</td><td>(140,190)</td><td>16505</td><td>16551.60</td><td>16558</td><td>16539.90</td><td>16509.80</td><td>16465.30</td><td>294.90</td><td>16439.67</td><td>1002.06</td><td>16425</td><td>16430</td><td>16425</td><td>16425</td><td>16425</td></tr><tr><td>S3-A</td><td>(140,190)</td><td>10451</td><td>10291.20</td><td>10306</td><td>10276.10</td><td>10312.70</td><td>10228.10</td><td>463.81</td><td>10217.83</td><td>1719.03</td><td>10165</td><td>10220</td><td>10201</td><td>10201*</td><td>10201*</td></tr><tr><td>S3-B</td><td>(140,190)</td><td>13981</td><td>13829.20</td><td>13890</td><td>13860.70</td><td>13876.60</td><td>13739.10</td><td>466.39</td><td>13705.67</td><td>1397.05</td><td>13648</td><td>13682</td><td>13688</td><td>13682</td><td>13682</td></tr><tr><td>S3-C</td><td>(140,190)</td><td>17346</td><td>17327.90</td><td>17304</td><td>17277.70</td><td>17305.80</td><td>17248.60</td><td>345.12</td><td>17217.63</td><td>1338.38</td><td>17188</td><td>17188</td><td>17196</td><td>17189</td><td>17188</td></tr><tr><td>S4-A</td><td>(140,190)</td><td>12462</td><td>12440.40</td><td>12439</td><td>12406.50</td><td>12419.20</td><td>12269.73</td><td>603.98</td><td>12258.30</td><td>2035.96</td><td>12153</td><td>12268</td><td>12254</td><td>12244</td><td>12216*</td></tr><tr><td>S4-B</td><td>(140,190)</td><td>16490</td><td>16410.30</td><td>16502</td><td>16432.00</td><td>16441.20</td><td>16264.70</td><td>611.16</td><td>16243.70</td><td>1663.58</td><td>16113</td><td>16260</td><td>16222</td><td>16216</td><td>16201*</td></tr><tr><td>S4-C</td><td>(140,190)</td><td>20733</td><td>20731.50</td><td>20731</td><td>20660.50</td><td>20767.20</td><td>20545.53</td><td>404.61</td><td>20518.37</td><td>1695.86</td><td>20430</td><td>20481</td><td>20479</td><td>20476</td><td>20476*</td></tr><tr><td>AvgGap</td><td></td><td>0.75</td><td>0.56</td><td>0.58</td><td>0.50</td><td>0.59</td><td>0.13</td><td></td><td>0.07</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>AvgTime (scaled)</td><td></td><td>145.68</td><td>649.17</td><td>181.09</td><td>854.48</td><td>498.49</td><td>198.83</td><td></td><td>646.03</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
<caption>Table A.4</caption>

Detailed comparative results of HMA algorithm with 4 state-of-the-art algorithms on the 25 instances of Set C. The average results of all algorithms and the best results of HMA₁ (500 generations) and HMA₂ (2000 generations) are highlighted in bold if they match the BKRs. The optimal BKRs are underlined.

<table><caption>Table A.5</caption><thead><tr><th rowspan="2">INST</th><th rowspan="2">(|N|, |E|)</th><th colspan="8">Average (median) results</th><th colspan="4">Best results</th></tr><tr><th>GLS<br>1 run</th><th>TSA2<br>1 run</th><th>Ant.12<br>10 runs</th><th>MAENS<br>30 runs</th><th>HMA1<br>30 runs</th><th>Time</th><th>HMA2<br>30 runs</th><th>Time</th><th>LB</th><th>BKR</th><th>HMA1</th><th>HMA2</th></tr></thead><tbody><tr><td>C1</td><td>(69,98)</td><td><strong>1660</strong></td><td><strong>1660</strong></td><td>1705</td><td>1707.00</td><td>1661.00</td><td>117.04</td><td><strong>1660.00</strong></td><td>160.51</td><td>1660</td><td><strong>1660</strong></td><td><strong>1660</strong></td><td><strong>1660</strong></td></tr><tr><td>C2</td><td>(48,66)</td><td><strong>1095</strong></td><td><strong>1095</strong></td><td><strong>1095</strong></td><td>1095.70</td><td><strong>1095.00</strong></td><td>9.10</td><td><strong>1095.00</strong></td><td>9.10</td><td>1095</td><td><u>1095</u></td><td><strong>1095</strong></td><td><strong>1095</strong></td></tr><tr><td>C3</td><td>(46,64)</td><td><strong>925</strong></td><td><strong>925</strong></td><td><strong>925</strong></td><td>927.80</td><td>930.33</td><td>30.94</td><td>926.33</td><td>163.67</td><td>925</td><td><u>925</u></td><td><strong>925</strong></td><td><strong>925</strong></td></tr><tr><td>C4</td><td>(60,84)</td><td><strong>1340</strong></td><td><strong>1340</strong></td><td><strong>1340</strong></td><td>1342.70</td><td><strong>1340.00</strong></td><td>5.20</td><td><strong>1340.00</strong></td><td>5.20</td><td>1340</td><td><u>1340</u></td><td><strong>1340</strong></td><td><strong>1340</strong></td></tr><tr><td>C5</td><td>(56,79)</td><td>2475</td><td><strong>2470</strong></td><td>2540</td><td>2522.30</td><td>2470.33</td><td>67.19</td><td><strong>2470.00</strong></td><td>84.00</td><td>2470</td><td><u>2470</u></td><td><strong>2470</strong></td><td><strong>2470</strong></td></tr><tr><td>C6</td><td>(38,55)</td><td><strong>895</strong></td><td><strong>895</strong></td><td><strong>895</strong></td><td>907.50</td><td><strong>895.00</strong></td><td>13.78</td><td><strong>895.00</strong></td><td>13.78</td><td>895</td><td><u>895</u></td><td><strong>895</strong></td><td><strong>895</strong></td></tr><tr><td>C7</td><td>(54,70)</td><td><strong>1795</strong></td><td><strong>1795</strong></td><td><strong>1795</strong></td><td><strong>1795.00</strong></td><td><strong>1795.00</strong></td><td>0.61</td><td><strong>1795.00</strong></td><td>0.61</td><td>1795</td><td><u>1795</u></td><td><strong>1795</strong></td><td><strong>1795</strong></td></tr><tr><td>C8</td><td>(66,88)</td><td><strong>1730</strong></td><td><strong>1730</strong></td><td><strong>1730</strong></td><td>1732.30</td><td><strong>1730.00</strong></td><td>14.20</td><td><strong>1730.00</strong></td><td>14.20</td><td>1730</td><td><u>1730</u></td><td><strong>1730</strong></td><td><strong>1730</strong></td></tr><tr><td>C9</td><td>(76,117)</td><td>1825</td><td>1830</td><td>1860</td><td>1852.80</td><td><strong>1820.00</strong></td><td>74.70</td><td><strong>1820.00</strong></td><td>74.70</td><td>1805</td><td><u>1820</u></td><td><strong>1820</strong></td><td><strong>1820</strong></td></tr><tr><td>C10</td><td>(60,82)</td><td>2290</td><td><strong>2270</strong></td><td>2305</td><td>2317.80</td><td><strong>2270.00</strong></td><td>24.17</td><td><strong>2270.00</strong></td><td>24.17</td><td>2270</td><td><u>2270</u></td><td><strong>2270</strong></td><td><strong>2270</strong></td></tr><tr><td>C11</td><td>(83,118)</td><td>1815</td><td>1815</td><td>1820</td><td>1853.70</td><td>1815.00</td><td>37.19</td><td>1813.67</td><td>121.19</td><td>1790</td><td><u>1805</u></td><td>1815</td><td><strong>1805</strong></td></tr><tr><td>C12</td><td>(62,88)</td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610.00</strong></td><td><strong>1610.00</strong></td><td>1.30</td><td><strong>1610.00</strong></td><td>1.30</td><td>1605</td><td><u>1610</u></td><td><strong>1610</strong></td><td><strong>1610</strong></td></tr><tr><td>C13</td><td>(40,60)</td><td><strong>1110</strong></td><td><strong>1110</strong></td><td><strong>1110</strong></td><td>1122.00</td><td><strong>1110.00</strong></td><td>8.20</td><td><strong>1110.00</strong></td><td>8.20</td><td>1110</td><td><u>1110</u></td><td><strong>1110</strong></td><td><strong>1110</strong></td></tr><tr><td>C14</td><td>(58,79)</td><td><strong>1680</strong></td><td><strong>1680</strong></td><td><strong>1680</strong></td><td>1687.30</td><td><strong>1680.00</strong></td><td>15.88</td><td><strong>1680.00</strong></td><td>15.88</td><td>1680</td><td><u>1680</u></td><td><strong>1680</strong></td><td><strong>1680</strong></td></tr><tr><td>C15</td><td>(97,140)</td><td><strong>1860</strong></td><td><strong>1860</strong></td><td><strong>1860</strong></td><td>1896.50</td><td><strong>1860.00</strong></td><td>82.70</td><td><strong>1860.00</strong></td><td>82.70</td><td>1840</td><td><u>1860</u></td><td><strong>1860</strong></td><td><strong>1860</strong></td></tr><tr><td>C16</td><td>(32,42)</td><td><strong>585</strong></td><td><strong>585</strong></td><td><strong>585</strong></td><td>585.20</td><td><strong>585.00</strong></td><td>9.56</td><td><strong>585.00</strong></td><td>9.56</td><td>585</td><td><u>585</u></td><td><strong>585</strong></td><td><strong>585</strong></td></tr><tr><td>C17</td><td>(43,56)</td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610</strong></td><td>1618.30</td><td><strong>1610.00</strong></td><td>5.00</td><td><strong>1610.00</strong></td><td>5.00</td><td>1610</td><td><u>1610</u></td><td><strong>1610</strong></td><td><strong>1610</strong></td></tr><tr><td>C18</td><td>(93,133)</td><td>2410</td><td>2415</td><td>2390</td><td>2411.70</td><td><strong>2385.00</strong></td><td>160.09</td><td><strong>2385.00</strong></td><td>160.09</td><td>2345</td><td><u>2385</u></td><td><strong>2385</strong></td><td><strong>2385</strong></td></tr><tr><td>C19</td><td>(62,84)</td><td><strong>1395</strong></td><td>1400</td><td>1400</td><td>1425.70</td><td>1396.33</td><td>53.91</td><td><strong>1395.00</strong></td><td>115.09</td><td>1395</td><td><u>1395</u></td><td><strong>1395</strong></td><td><strong>1395</strong></td></tr><tr><td>C20</td><td>(45,64)</td><td><strong>665</strong></td><td><strong>665</strong></td><td><strong>665</strong></td><td>668.50</td><td><strong>665.00</strong></td><td>0.64</td><td><strong>665.00</strong></td><td>0.64</td><td>665</td><td><u>665</u></td><td><strong>665</strong></td><td><strong>665</strong></td></tr><tr><td>C21</td><td>(60,84)</td><td><strong>1725</strong></td><td><strong>1725</strong></td><td><strong>1725</strong></td><td>1725.20</td><td><strong>1725.00</strong></td><td>1.52</td><td><strong>1725.00</strong></td><td>1.52</td><td>1725</td><td><u>1725</u></td><td><strong>1725</strong></td><td><strong>1725</strong></td></tr><tr><td>C22</td><td>(56,76)</td><td><strong>1070</strong></td><td><strong>1070</strong></td><td><strong>1070</strong></td><td><strong>1070.00</strong></td><td><strong>1070.00</strong></td><td>0.30</td><td><strong>1070.00</strong></td><td>0.30</td><td>1070</td><td><u>1070</u></td><td><strong>1070</strong></td><td><strong>1070</strong></td></tr><tr><td>C23</td><td>(78,109)</td><td><strong>1690</strong></td><td>1700</td><td>1710</td><td>1724.30</td><td>1690.33</td><td>66.86</td><td><strong>1690.00</strong></td><td>76.30</td><td>1680</td><td><u>1690</u></td><td><strong>1690</strong></td><td><strong>1690</strong></td></tr><tr><td>C24</td><td>(77,115)</td><td><strong>1360</strong></td><td><strong>1360</strong></td><td><strong>1360</strong></td><td>1368.50</td><td>1361.00</td><td>104.42</td><td><strong>1360.00</strong></td><td>190.24</td><td>1360</td><td><u>1360</u></td><td><strong>1360</strong></td><td><strong>1360</strong></td></tr><tr><td>C25</td><td>(37,50)</td><td><strong>905</strong></td><td><strong>905</strong></td><td><strong>905</strong></td><td>907.00</td><td><strong>905.00</strong></td><td>17.47</td><td><strong>905.00</strong></td><td>17.47</td><td>905</td><td><u>905</u></td><td><strong>905</strong></td><td><strong>905</strong></td></tr><tr><td>AvgGap</td><td></td><td>0.12</td><td>0.14</td><td>0.52</td><td>0.98</td><td>0.06</td><td></td><td>0.02</td><td></td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>AvgTime (scaled)</td><td></td><td>42.49</td><td>42.92</td><td>40.76</td><td>165.50</td><td>36.88</td><td></td><td>54.22</td><td></td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

Detailed comparative results of HMA algorithm with 4 state-of-the-art algorithms on the 25 instances of Set D. The average results of all algorithms and the best results of HMA₁ (500 generations) and HMA₂ (2000 generations) are highlighted in bold if they match the BKRs. The optimal BKRs are underlined.

<table><thead><tr><th rowspan="2">INST</th><th rowspan="2">(|N|, |E|)</th><th colspan="8">Average (median) results</th><th colspan="4">Best results</th></tr><tr><th>GLS<br>1 run</th><th>TSA2<br>1 run</th><th>Ant.12<br>10 runs</th><th>MAENS<br>30 runs</th><th>HMA1<br>30 runs</th><th>Time</th><th>HMA2<br>30 runs</th><th>Time</th><th>LB</th><th>BKR</th><th>HMA1</th><th>HMA2</th></tr></thead><tbody><tr><td>D1</td><td>(69,98)</td><td><strong>725</strong></td><td>740</td><td>745</td><td>745.00</td><td>743.83</td><td>14.09</td><td>738.83</td><td>145.70</td><td>725</td><td><strong>725</strong></td><td><strong>725</strong></td><td><strong>725</strong></td></tr><tr><td>D2</td><td>(48,66)</td><td><strong>480</strong></td><td><strong>480</strong></td><td><strong>480</strong></td><td><strong>480.00</strong></td><td><strong>480.00</strong></td><td>0.34</td><td><strong>480.00</strong></td><td>0.34</td><td>480</td><td><u>480</u></td><td><strong>480</strong></td><td><strong>480</strong></td></tr><tr><td>D3</td><td>(46,64)</td><td><strong>415</strong></td><td><strong>415</strong></td><td><strong>415</strong></td><td>415.20</td><td><strong>415.00</strong></td><td>0.24</td><td><strong>415.00</strong></td><td>0.24</td><td>415</td><td><u>415</u></td><td><strong>415</strong></td><td><strong>415</strong></td></tr><tr><td>D4</td><td>(60,84)</td><td><strong>615</strong></td><td><strong>615</strong></td><td><strong>615</strong></td><td>616.00</td><td><strong>615.00</strong></td><td>1.25</td><td><strong>615.00</strong></td><td>1.25</td><td>615</td><td><u>615</u></td><td><strong>615</strong></td><td><strong>615</strong></td></tr><tr><td>D5</td><td>(56,79)</td><td><strong>1040</strong></td><td><strong>1040</strong></td><td><strong>1040</strong></td><td><strong>1040.00</strong></td><td><strong>1040.00</strong></td><td>0.76</td><td><strong>1040.00</strong></td><td>0.76</td><td>1040</td><td><u>1040</u></td><td><strong>1040</strong></td><td><strong>1040</strong></td></tr><tr><td>D6</td><td>(38,55)</td><td><strong>485</strong></td><td><strong>485</strong></td><td><strong>485</strong></td><td>493.00</td><td><strong>485.00</strong></td><td>0.43</td><td><strong>485.00</strong></td><td>0.43</td><td>485</td><td><u>485</u></td><td><strong>485</strong></td><td><strong>485</strong></td></tr><tr><td>D7</td><td>(54,70)</td><td><strong>835</strong></td><td><strong>835</strong></td><td><strong>835</strong></td><td>847.30</td><td>838.67</td><td>53.72</td><td><strong>835.00</strong></td><td>145.24</td><td>835</td><td><u>835</u></td><td><strong>835</strong></td><td><strong>835</strong></td></tr><tr><td>D8</td><td>(66,88)</td><td><strong>685</strong></td><td><strong>685</strong></td><td><strong>685</strong></td><td>704.20</td><td><strong>685.00</strong></td><td>6.98</td><td><strong>685.00</strong></td><td>6.98</td><td>685</td><td><u>685</u></td><td><strong>685</strong></td><td><strong>685</strong></td></tr><tr><td>D9</td><td>(76,117)</td><td><strong>680</strong></td><td><strong>680</strong></td><td><strong>680</strong></td><td><strong>680.00</strong></td><td><strong>680.00</strong></td><td>0.84</td><td><strong>680.00</strong></td><td>0.84</td><td>680</td><td><u>680</u></td><td><strong>680</strong></td><td><strong>680</strong></td></tr><tr><td>D10</td><td>(60,82)</td><td><strong>910</strong></td><td><strong>910</strong></td><td><strong>910</strong></td><td><strong>910.00</strong></td><td><strong>910.00</strong></td><td>0.26</td><td><strong>910.00</strong></td><td>0.26</td><td>910</td><td><u>910</u></td><td><strong>910</strong></td><td><strong>910</strong></td></tr><tr><td>D11</td><td>(83,118)</td><td>930</td><td>960</td><td>935</td><td>935.20</td><td>930.00</td><td>38.38</td><td>925.33</td><td>286.78</td><td>920</td><td><u>920</u></td><td><strong>920</strong></td><td><strong>920</strong></td></tr><tr><td>D12</td><td>(62,88)</td><td><strong>680</strong></td><td><strong>680</strong></td><td><strong>680</strong></td><td><strong>680.00</strong></td><td><strong>680.00</strong></td><td>4.94</td><td><strong>680.00</strong></td><td>4.94</td><td>680</td><td><u>680</u></td><td><strong>680</strong></td><td><strong>680</strong></td></tr><tr><td>D13</td><td>(40,60)</td><td><strong>690</strong></td><td><strong>690</strong></td><td><strong>690</strong></td><td>691.00</td><td><strong>690.00</strong></td><td>6.70</td><td><strong>690.00</strong></td><td>6.70</td><td>690</td><td><u>690</u></td><td><strong>690</strong></td><td><strong>690</strong></td></tr><tr><td>D14</td><td>(58,79)</td><td><strong>930</strong></td><td>940</td><td><strong>930</strong></td><td>931.00</td><td><strong>930.00</strong></td><td>0.40</td><td><strong>930.00</strong></td><td>0.40</td><td>930</td><td><u>930</u></td><td><strong>930</strong></td><td><strong>930</strong></td></tr><tr><td>D15</td><td>(97,140)</td><td><strong>910</strong></td><td>950</td><td>920</td><td>919.00</td><td>910.50</td><td>115.49</td><td><strong>910.00</strong></td><td>141.87</td><td>910</td><td><u>910</u></td><td><strong>910</strong></td><td><strong>910</strong></td></tr><tr><td>D16</td><td>(32,42)</td><td><strong>170</strong></td><td><strong>170</strong></td><td><strong>170</strong></td><td><strong>170.00</strong></td><td><strong>170.00</strong></td><td>0.13</td><td><strong>170.00</strong></td><td>0.13</td><td>170</td><td><u>170</u></td><td><strong>170</strong></td><td><strong>170</strong></td></tr><tr><td>D17</td><td>(43,56)</td><td><strong>675</strong></td><td><strong>675</strong></td><td><strong>675</strong></td><td><strong>675.00</strong></td><td><strong>675.00</strong></td><td>0.17</td><td><strong>675.00</strong></td><td>0.17</td><td>675</td><td><u>675</u></td><td><strong>675</strong></td><td><strong>675</strong></td></tr><tr><td>D18</td><td>(93,133)</td><td><strong>930</strong></td><td><strong>930</strong></td><td><strong>930</strong></td><td>934.20</td><td><strong>930.00</strong></td><td>3.69</td><td><strong>930.00</strong></td><td>3.69</td><td>930</td><td><u>930</u></td><td><strong>930</strong></td><td><strong>930</strong></td></tr><tr><td>D19</td><td>(62,84)</td><td><strong>680</strong></td><td><strong>690</strong></td><td><strong>680</strong></td><td><strong>680.00</strong></td><td><strong>680.00</strong></td><td>0.64</td><td><strong>680.00</strong></td><td>0.64</td><td>680</td><td><u>680</u></td><td><strong>680</strong></td><td><strong>680</strong></td></tr><tr><td>D20</td><td>(45,64)</td><td><strong>415</strong></td><td><strong>415</strong></td><td><strong>415</strong></td><td>415.20</td><td><strong>415.00</strong></td><td>0.32</td><td><strong>415.00</strong></td><td>0.32</td><td>415</td><td><u>415</u></td><td><strong>415</strong></td><td><strong>415</strong></td></tr><tr><td>D21</td><td>(60,84)</td><td><strong>805</strong></td><td><strong>825</strong></td><td><strong>810</strong></td><td>834.20</td><td>805.17</td><td>79.37</td><td><strong>805.00</strong></td><td>93.50</td><td>760</td><td><u>805</u></td><td><strong>805</strong></td><td><strong>805</strong></td></tr><tr><td>D22</td><td>(56,76)</td><td><strong>690</strong></td><td><strong>690</strong></td><td><strong>690</strong></td><td><strong>690.00</strong></td><td><strong>690.00</strong></td><td>0.24</td><td><strong>690.00</strong></td><td>0.24</td><td>690</td><td><u>690</u></td><td><strong>690</strong></td><td><strong>690</strong></td></tr><tr><td>D23</td><td>(78,109)</td><td><strong>735</strong></td><td><strong>735</strong></td><td><strong>735</strong></td><td>748.20</td><td><strong>735.00</strong></td><td>33.69</td><td><strong>735.00</strong></td><td>33.69</td><td>735</td><td><u>735</u></td><td><strong>735</strong></td><td><strong>735</strong></td></tr><tr><td>D24</td><td>(77,115)</td><td><strong>670</strong></td><td><strong>670</strong></td><td><strong>670</strong></td><td>683.50</td><td><strong>670.00</strong></td><td>2.88</td><td><strong>670.00</strong></td><td>2.88</td><td>665</td><td><u>670</u></td><td><strong>670</strong></td><td><strong>670</strong></td></tr><tr><td>D25</td><td>(37,50)</td><td><strong>410</strong></td><td><strong>410</strong></td><td><strong>410</strong></td><td><strong>410.00</strong></td><td><strong>410.00</strong></td><td>0.19</td><td><strong>410.00</strong></td><td>0.19</td><td>410</td><td><u>410</u></td><td><strong>410</strong></td><td><strong>410</strong></td></tr><tr><td>AvgGap</td><td></td><td>0.04</td><td>0.66</td><td>0.34</td><td>0.79</td><td>0.17</td><td></td><td>0.10</td><td></td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>AvgTime (scaled)</td><td></td><td>17.36</td><td>19.20</td><td>51.88</td><td>219.53</td><td>14.65</td><td></td><td>35.13</td><td></td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>
<caption>Table A.6</caption>

Detailed comparative results of HMA algorithm with 4 state-of-the-art algorithms on the 25 instances of Set E. The average results of all algorithms and the best results of HMA₁ (500 generations) and HMA₂ (2000 generations) are highlighted in bold if they match the BKRs. The optimal BKRs are underlined.

<table><caption>Table A.7</caption><thead><tr><th rowspan="2">INST</th><th rowspan="2">(|N|, |E|)</th><th colspan="8">Average (median) results</th><th colspan="4">Best results</th></tr><tr><th>GLS<br>1 run</th><th>TSA2<br>1 run</th><th>Ant.12<br>10 runs</th><th>MAENS<br>30 runs</th><th>HMA1<br>30 runs</th><th>Time</th><th>HMA2<br>30 runs</th><th>Time</th><th>LB</th><th>BKR</th><th>HMA1</th><th>HMA2</th></tr></thead><tbody><tr><td>E1</td><td>(73,105)</td><td>1940</td><td><strong>1935</strong></td><td>1945</td><td>1967.80</td><td>1936.83</td><td>102.65</td><td><strong>1935.00</strong></td><td>160.72</td><td>1925</td><td>1935</td><td><strong>1935</strong></td><td><strong>1935</strong></td></tr><tr><td>E2</td><td>(58,81)</td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610</strong></td><td>1615.50</td><td><strong>1610.00</strong></td><td>11.38</td><td><strong>1610.00</strong></td><td>11.38</td><td>1610</td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610</strong></td></tr><tr><td>E3</td><td>(46,61)</td><td><strong>750</strong></td><td><strong>750</strong></td><td><strong>750</strong></td><td>752.00</td><td><strong>750.00</strong></td><td>1.33</td><td><strong>750.00</strong></td><td>1.33</td><td>750</td><td><strong>750</strong></td><td><strong>750</strong></td><td><strong>750</strong></td></tr><tr><td>E4</td><td>(70,99)</td><td><strong>1610</strong></td><td>1615</td><td>1675</td><td>1684.30</td><td><strong>1610.00</strong></td><td>23.60</td><td><strong>1610.00</strong></td><td>23.60</td><td>1610</td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610</strong></td></tr><tr><td>E5</td><td>(68,94)</td><td>2170</td><td><strong>2160</strong></td><td>2220</td><td>2228.70</td><td>2162.33</td><td>85.64</td><td><strong>2160.00</strong></td><td>132.12</td><td>2160</td><td><strong>2160</strong></td><td><strong>2160</strong></td><td><strong>2160</strong></td></tr><tr><td>E6</td><td>(49,66)</td><td><strong>670</strong></td><td><strong>670</strong></td><td><strong>670</strong></td><td><strong>670.00</strong></td><td><strong>670.00</strong></td><td>0.24</td><td><strong>670.00</strong></td><td>0.24</td><td>670</td><td><strong>670</strong></td><td><strong>670</strong></td><td><strong>670</strong></td></tr><tr><td>E7</td><td>(73,94)</td><td><strong>1900</strong></td><td><strong>1900</strong></td><td><strong>1900</strong></td><td><strong>1900.00</strong></td><td><strong>1900.00</strong></td><td>0.63</td><td><strong>1900.00</strong></td><td>0.63</td><td>1900</td><td><strong>1900</strong></td><td><strong>1900</strong></td><td><strong>1900</strong></td></tr><tr><td>E8</td><td>(74,98)</td><td><strong>2150</strong></td><td>2155</td><td><strong>2150</strong></td><td>2150.50</td><td><strong>2150.00</strong></td><td>2.11</td><td><strong>2150.00</strong></td><td>2.11</td><td>2150</td><td><strong>2150</strong></td><td><strong>2150</strong></td><td><strong>2150</strong></td></tr><tr><td>E9</td><td>(93,141)</td><td>2250</td><td>2300</td><td>2295</td><td>2327.70</td><td>2247.50</td><td>170.23</td><td>2228.67</td><td>498.99</td><td>2220</td><td><strong>2225</strong></td><td><strong>2225</strong></td><td><strong>2225</strong></td></tr><tr><td>E10</td><td>(56,76)</td><td><strong>1690</strong></td><td><strong>1690</strong></td><td><strong>1690</strong></td><td>1691.50</td><td><strong>1690.00</strong></td><td>1.44</td><td><strong>1690.00</strong></td><td>1.44</td><td>1690</td><td><strong>1690</strong></td><td><strong>1690</strong></td><td><strong>1690</strong></td></tr><tr><td>E11</td><td>(80,113)</td><td>1850</td><td>1855</td><td>1860</td><td>1932.00</td><td>1846.67</td><td>96.44</td><td>1840.00</td><td>460.01</td><td>1830</td><td><strong>1830</strong></td><td><strong>1830</strong></td><td><strong>1830</strong></td></tr><tr><td>E12</td><td>(74,103)</td><td>1710</td><td>1730</td><td>1760</td><td>1764.30</td><td>1723.83</td><td>124.02</td><td>1707.00</td><td>341.32</td><td>1695</td><td><strong>1695</strong></td><td>1700</td><td><strong>1695</strong></td></tr><tr><td>E13</td><td>(49,73)</td><td><strong>1325</strong></td><td><strong>1325</strong></td><td><strong>1325</strong></td><td>1335.30</td><td><strong>1325.00</strong></td><td>7.97</td><td><strong>1325.00</strong></td><td>7.97</td><td>1325</td><td><strong>1325</strong></td><td><strong>1325</strong></td><td><strong>1325</strong></td></tr><tr><td>E14</td><td>(53,72)</td><td><strong>1810</strong></td><td><strong>1810</strong></td><td><strong>1810</strong></td><td>1817.00</td><td>1810.67</td><td>46.57</td><td><strong>1810.00</strong></td><td>51.25</td><td>1810</td><td><strong>1810</strong></td><td><strong>1810</strong></td><td><strong>1810</strong></td></tr><tr><td>E15</td><td>(85,126)</td><td>1610</td><td>1610</td><td>1610</td><td>1617.80</td><td>1601.00</td><td>149.37</td><td>1599.00</td><td>723.39</td><td>1590</td><td><strong>1590</strong></td><td>1600</td><td><strong>1590</strong></td></tr><tr><td>E16</td><td>(60,80)</td><td><strong>1825</strong></td><td><strong>1825</strong></td><td><strong>1825</strong></td><td><strong>1825.00</strong></td><td><strong>1825.00</strong></td><td>39.74</td><td><strong>1825.00</strong></td><td>39.74</td><td>1825</td><td><strong>1825</strong></td><td><strong>1825</strong></td><td><strong>1825</strong></td></tr><tr><td>E17</td><td>(38,50)</td><td><strong>1290</strong></td><td><strong>1290</strong></td><td><strong>1290</strong></td><td>1294.30</td><td>1291.00</td><td>18.71</td><td><strong>1290.00</strong></td><td>26.35</td><td>1290</td><td><strong>1290</strong></td><td><strong>1290</strong></td><td><strong>1290</strong></td></tr><tr><td>E18</td><td>(78,110)</td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610</strong></td><td>1612.30</td><td><strong>1610.00</strong></td><td>1.41</td><td><strong>1610.00</strong></td><td>1.41</td><td>1610</td><td><strong>1610</strong></td><td><strong>1610</strong></td><td><strong>1610</strong></td></tr><tr><td>E19</td><td>(77,103)</td><td><strong>1435</strong></td><td><strong>1435</strong></td><td><strong>1435</strong></td><td>1437.00</td><td><strong>1435.00</strong></td><td>3.54</td><td><strong>1435.00</strong></td><td>3.54</td><td>1435</td><td><strong>1435</strong></td><td><strong>1435</strong></td><td><strong>1435</strong></td></tr><tr><td>E20</td><td>(56,80)</td><td><strong>990</strong></td><td><strong>990</strong></td><td><strong>990</strong></td><td><strong>990.00</strong></td><td><strong>990.00</strong></td><td>0.64</td><td><strong>990.00</strong></td><td>0.64</td><td>990</td><td><strong>990</strong></td><td><strong>990</strong></td><td><strong>990</strong></td></tr><tr><td>E21</td><td>(57,82)</td><td><strong>1705</strong></td><td><strong>1705</strong></td><td><strong>1705</strong></td><td>1755.50</td><td><strong>1705.00</strong></td><td>51.59</td><td><strong>1705.00</strong></td><td>51.59</td><td>1705</td><td><strong>1705</strong></td><td><strong>1705</strong></td><td><strong>1705</strong></td></tr><tr><td>E22</td><td>(54,73)</td><td><strong>1185</strong></td><td><strong>1185</strong></td><td><strong>1185</strong></td><td>1187.50</td><td><strong>1185.00</strong></td><td>1.42</td><td><strong>1185.00</strong></td><td>1.42</td><td>1185</td><td><strong>1185</strong></td><td><strong>1185</strong></td><td><strong>1185</strong></td></tr><tr><td>E23</td><td>(93,130)</td><td><strong>1430</strong></td><td>1445</td><td>1435</td><td>1469.00</td><td>1432.33</td><td>88.98</td><td>1430.33</td><td>336.54</td><td>1430</td><td><strong>1430</strong></td><td><strong>1430</strong></td><td><strong>1430</strong></td></tr><tr><td>E24</td><td>(97,142)</td><td><strong>1785</strong></td><td><strong>1785</strong></td><td><strong>1785</strong></td><td>1822.20</td><td><strong>1785.00</strong></td><td>35.38</td><td><strong>1785.00</strong></td><td>35.38</td><td>1785</td><td><strong>1785</strong></td><td><strong>1785</strong></td><td><strong>1785</strong></td></tr><tr><td>E25</td><td>(26,35)</td><td><strong>655</strong></td><td><strong>655</strong></td><td><strong>655</strong></td><td><strong>655.00</strong></td><td><strong>655.00</strong></td><td>0.45</td><td><strong>655.00</strong></td><td>0.45</td><td>655</td><td><strong>655</strong></td><td><strong>655</strong></td><td><strong>655</strong></td></tr><tr><td>AvgGap</td><td></td><td>0.20</td><td>0.39</td><td>0.83</td><td>1.44</td><td>0.19</td><td></td><td>0.08</td><td></td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>AvgTime (scaled)</td><td></td><td>40.65</td><td>46.00</td><td>40.54</td><td>160.89</td><td>42.62</td><td></td><td>116.54</td><td></td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

Detailed comparative results of HMA algorithm with 4 state-of-the-art algorithms on the 25 instances of Set F. The average results of all algorithms and the best results of HMA₁ (500 generations) are highlighted in bold if they match the BKRs. The optimal BKRs are underlined.

<table><thead><tr><th rowspan="2">INST</th><th rowspan="2">(|N|, |E|)</th><th colspan="8">Average (median) results</th><th colspan="4">Best results</th></tr><tr><th>GLS<br>1 run</th><th>TSA2<br>1 run</th><th>Ant.12<br>10 runs</th><th>MAENS<br>30 runs</th><th>HMA1<br>30 runs</th><th>Time</th><th>HMA2<br>30 runs</th><th>Time</th><th>LB</th><th>BKR</th><th>HMA1</th><th>HMA2</th></tr></thead><tbody><tr><td>F1</td><td>(73,105)</td><td><strong>1065</strong></td><td>1085</td><td><strong>1065</strong></td><td>1071.00</td><td><strong>1065.00</strong></td><td>43.29</td><td></td><td></td><td>1065</td><td><strong>1065</strong></td><td><strong>1065</strong></td><td></td></tr><tr><td>F2</td><td>(58,81)</td><td><strong>920</strong></td><td><strong>920</strong></td><td><strong>920</strong></td><td><strong>920.00</strong></td><td><strong>920.00</strong></td><td>0.67</td><td></td><td></td><td>920</td><td><strong>920</strong></td><td><strong>920</strong></td><td></td></tr><tr><td>F3</td><td>(46,61)</td><td><strong>400</strong></td><td><strong>400</strong></td><td><strong>400</strong></td><td><strong>400.00</strong></td><td><strong>400.00</strong></td><td>0.25</td><td></td><td></td><td>400</td><td><strong>400</strong></td><td><strong>400</strong></td><td></td></tr><tr><td>F4</td><td>(70,99)</td><td><strong>940</strong></td><td>960</td><td>955</td><td>963.50</td><td><strong>940.00</strong></td><td>22.54</td><td></td><td></td><td>940</td><td><strong>940</strong></td><td><strong>940</strong></td><td></td></tr><tr><td>F5</td><td>(68,94)</td><td><strong>1180</strong></td><td><strong>1180</strong></td><td><strong>1180</strong></td><td>1180.30</td><td><strong>1180.00</strong></td><td>3.86</td><td></td><td></td><td>1180</td><td><strong>1180</strong></td><td><strong>1180</strong></td><td></td></tr><tr><td>F6</td><td>(49,66)</td><td><strong>490</strong></td><td><strong>490</strong></td><td><strong>490</strong></td><td><strong>490.00</strong></td><td><strong>490.00</strong></td><td>0.22</td><td></td><td></td><td>490</td><td><strong>490</strong></td><td><strong>490</strong></td><td></td></tr><tr><td>F7</td><td>(73,94)</td><td><strong>1080</strong></td><td><strong>1080</strong></td><td><strong>1080</strong></td><td>1090.70</td><td><strong>1080.00</strong></td><td>3.00</td><td></td><td></td><td>1080</td><td><strong>1080</strong></td><td><strong>1080</strong></td><td></td></tr><tr><td>F8</td><td>(74,98)</td><td><strong>1145</strong></td><td><strong>1145</strong></td><td><strong>1145</strong></td><td><strong>1145.00</strong></td><td><strong>1145.00</strong></td><td>0.41</td><td></td><td></td><td>1145</td><td><strong>1145</strong></td><td><strong>1145</strong></td><td></td></tr><tr><td>F9</td><td>(93,141)</td><td><strong>1145</strong></td><td>1170</td><td>1225</td><td>1197.80</td><td><strong>1145.00</strong></td><td>11.24</td><td></td><td></td><td>1145</td><td><strong>1145</strong></td><td><strong>1145</strong></td><td></td></tr><tr><td>F10</td><td>(56,76)</td><td><strong>1010</strong></td><td><strong>1010</strong></td><td><strong>1010</strong></td><td><strong>1010.00</strong></td><td><strong>1010.00</strong></td><td>0.23</td><td></td><td></td><td>1010</td><td><strong>1010</strong></td><td><strong>1010</strong></td><td></td></tr><tr><td>F11</td><td>(80,113)</td><td><strong>1015</strong></td><td><strong>1015</strong></td><td><strong>1015</strong></td><td>1037.50</td><td><strong>1015.00</strong></td><td>6.56</td><td></td><td></td><td>1015</td><td><strong>1015</strong></td><td><strong>1015</strong></td><td></td></tr><tr><td>F12</td><td>(74,103)</td><td><strong>910</strong></td><td><strong>910</strong></td><td><strong>910</strong></td><td>939.50</td><td><strong>910.00</strong></td><td>10.40</td><td></td><td></td><td>910</td><td><strong>910</strong></td><td><strong>910</strong></td><td></td></tr><tr><td>F13</td><td>(49,73)</td><td><strong>835</strong></td><td><strong>835</strong></td><td><strong>835</strong></td><td><strong>835.00</strong></td><td><strong>835.00</strong></td><td>0.63</td><td></td><td></td><td>835</td><td><strong>835</strong></td><td><strong>835</strong></td><td></td></tr><tr><td>F14</td><td>(53,72)</td><td><strong>1025</strong></td><td>1035</td><td><strong>1025</strong></td><td>1065.50</td><td><strong>1025.00</strong></td><td>9.62</td><td></td><td></td><td>1025</td><td><strong>1025</strong></td><td><strong>1025</strong></td><td></td></tr><tr><td>F15</td><td>(85,126)</td><td><strong>945</strong></td><td>990</td><td><strong>945</strong></td><td>951.70</td><td><strong>945.00</strong></td><td>2.41</td><td></td><td></td><td>945</td><td><strong>945</strong></td><td><strong>945</strong></td><td></td></tr><tr><td>F16</td><td>(60,80)</td><td><strong>775</strong></td><td><strong>775</strong></td><td><strong>775</strong></td><td><strong>775.00</strong></td><td><strong>775.00</strong></td><td>0.45</td><td></td><td></td><td>775</td><td><strong>775</strong></td><td><strong>775</strong></td><td></td></tr><tr><td>F17</td><td>(38,50)</td><td><strong>605</strong></td><td>630</td><td><strong>605</strong></td><td><strong>605.00</strong></td><td><strong>605.00</strong></td><td>0.15</td><td></td><td></td><td>605</td><td><strong>605</strong></td><td><strong>605</strong></td><td></td></tr><tr><td>F18</td><td>(78,110)</td><td><strong>850</strong></td><td><strong>850</strong></td><td><strong>850</strong></td><td>861.20</td><td><strong>850.00</strong></td><td>0.85</td><td></td><td></td><td>840</td><td><strong>850</strong></td><td><strong>850</strong></td><td></td></tr><tr><td>F19</td><td>(77,103)</td><td><strong>725</strong></td><td>740</td><td><strong>725</strong></td><td><strong>725.00</strong></td><td><strong>725.00</strong></td><td>3.21</td><td></td><td></td><td>715</td><td><strong>725</strong></td><td><strong>725</strong></td><td></td></tr><tr><td>F20</td><td>(56,80)</td><td><strong>610</strong></td><td><strong>610</strong></td><td><strong>610</strong></td><td>614.80</td><td><strong>610.00</strong></td><td>6.38</td><td></td><td></td><td>610</td><td><strong>610</strong></td><td><strong>610</strong></td><td></td></tr><tr><td>F21</td><td>(57,82)</td><td><strong>905</strong></td><td><strong>905</strong></td><td><strong>905</strong></td><td><strong>905.00</strong></td><td><strong>905.00</strong></td><td>2.43</td><td></td><td></td><td>905</td><td><strong>905</strong></td><td><strong>905</strong></td><td></td></tr><tr><td>F22</td><td>(54,73)</td><td><strong>790</strong></td><td><strong>790</strong></td><td><strong>790</strong></td><td><strong>790.00</strong></td><td><strong>790.00</strong></td><td>0.85</td><td></td><td></td><td>790</td><td><strong>790</strong></td><td><strong>790</strong></td><td></td></tr><tr><td>F23</td><td>(93,130)</td><td><strong>725</strong></td><td>730</td><td>730</td><td>736.30</td><td><strong>725.00</strong></td><td>27.86</td><td></td><td></td><td>725</td><td><strong>725</strong></td><td><strong>725</strong></td><td></td></tr><tr><td>F24</td><td>(97,142)</td><td><strong>975</strong></td><td>1010</td><td><strong>975</strong></td><td>1001.30</td><td><strong>975.00</strong></td><td>53.28</td><td></td><td></td><td>975</td><td><strong>975</strong></td><td><strong>975</strong></td><td></td></tr><tr><td>F25</td><td>(26,35)</td><td><strong>430</strong></td><td><strong>430</strong></td><td><strong>430</strong></td><td><strong>430.00</strong></td><td><strong>430.00</strong></td><td>0.12</td><td></td><td></td><td>430</td><td><strong>430</strong></td><td><strong>430</strong></td><td></td></tr><tr><td>AvgGap</td><td></td><td>0.00</td><td>0.90</td><td>0.77</td><td>1.01</td><td></td><td>0.00</td><td></td><td></td><td>-</td><td>-</td><td>-</td><td></td></tr><tr><td>AvgTime (scaled)</td><td></td><td>10.67</td><td>21.09</td><td>52.17</td><td>166.85</td><td></td><td>8.44</td><td></td><td></td><td>-</td><td>-</td><td>-</td><td></td></tr></tbody></table>