# Exploring Further Advantages in an Alternative Formulation for the Set Covering Problem

Authors: Jose M. Lanza-Gutierrez; N. C. Caballe; Broderick Crawford; Ricardo Soto; Juan A. Gomez-Pulido; Fernando Paredes
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The set covering problem (SCP) is an NP-complete optimization problem, fitting with many problems in engineering. The traditional SCP formulation does not directly address both solution unsatisfiability and set redundancy aspects. As a result, the solving methods have to control these aspects to avoid getting unfeasible and nonoptimized in cost solutions. In the last years, an alternative SCP formulation was proposed, directly covering both aspects. This alternative formulation received limited attention because managing both aspects is considered straightforward at this time. This paper questions whether there is some advantage in the alternative formulation, beyond addressing the two issues. Thus, two studies based on a metaheuristic approach are proposed to identify if there is any concept in the alternative formulation, which could be considered for enhancing a solving method considering the traditional SCP formulation. As a result, the authors conclude that there are concepts from the alternative formulation, which could be applied for guiding the search process and for designing heuristic feasibilit\y operators. Thus, such concepts could be recommended for designing state-of-the-art algorithms addressing the traditional SCP formulation.


---

## Body

## 1. Introduction

The set covering problem (SCP) is a classical problem shown to be NP-complete by Karp [1] and whose optimization version is NP-hard. Although this is a traditional problem, SCP is widely considered in the current scientific literature because it fits problems in relevant areas, such as engineering, vehicle routing, medical domain, and facilities allocation (see e.g., [2–6]).Most contributions in the SCP field considered the traditional SCP formulation introduced by Chvatal [7] and defined as follows. Let E be a set of m objects and let S be a collection of n subsets of E, where each subset has a non-negative cost associated. Then, the purpose of SCP is to get a minimum cost family of subsets X⊆S, such that each element of E belongs to at least one subset of the family X. This traditional formulation does not directly deal with two aspects: solution unsatisfiability and set redundancy. The solution unsatisfiability aspect is related to the possibility of generating unfeasible solutions during the search. The set redundancy aspect is related to the possibility of generating nonoptimized solutions in cost, including redundant components (subsets). The noninclusion of these two aspects in the formulation means that the solving method has to address them to ensure good performance.In the last years, Bilal et al. [8] proposed an alternative SCP formulation. Its main contribution was that both redundant sets and unfeasible solutions were directly penalized in the fitness function. Therefore, the solving method does not have to control such aspects in contrast to the traditional SCP formulation. Nevertheless, the contribution of the alternative formulation becomes questionable due to two main issues. First, Vasko et al. [9] demonstrated that the calculation effort to remove redundant components from an SCP solution is almost negligible. Thus, including a redundancy removal operator in a solving method addressing the traditional formulation does not increase excessively the computational cost. Second, there are simple methods for transforming unfeasible solutions into feasible ones, such as the one proposed by Beasley and Chu [10]. As a consequence, alternative formulation seems not to be advantageous.Analysing the work proposed in the alternative formulation in Bilal et al. [8], they compared the alternative formulation to the traditional one. To this end, they solved the standard Beasley’s OR library [11] through two algorithms: a simple descent heuristic (DH) addressing the alternative formulation and a standard greedy heuristic (GH) addressing the traditional one. As a result, DH outperformed GH, which is valuable for justifying the alternative formulation. However, Vasko et al. [9] later applied the same GH using the traditional formulation on the same instances, but included a simple redundancy removal operator, obtaining better results than the ones shown in Bilal et al. [8] for DH. Once again, the alternative formulation seems to have questionable merit. However, this comparison initiated in Bilal et al. [8] might have some limitations:(i)
The heuristic techniques considered might not be the most appropriate according to the current state of the art, in which metaheuristics, especially swarm intelligence algorithms (SIAs), provide the best results in general.(ii)
The authors independently compared the two formulations using different algorithms. This focus could be correct because the algorithm best suited for a formulation could be very different, even in type, from the algorithm for the other formulation. However, there is no study combining aspects from the two formulations that could provide some advantages for the same solving method.(iii)
The authors did not consider any statistical method for comparing both formulations. Instead, they only compare the average solution obtained.On this basis, this paper questions whether there is any advantage from the concepts involved in the alternative formulation, beyond the novel problem formulation. This idea leads us to propose two studies focused on solution quality as a way to know if there is any concept in the alternative formulation, which could be considered for enhancing a method using the traditional formulation. To this end, the authors select two different metaheuristics adequate for the studies, although other metaheuristics could have been selected without loss of generality.The only demonstration of the concept utility from the alternative formulation is valuable. This means that future solving methods could include these novel concept. This research focus implies that the authors are not focused on getting the best absolute results solving Beasley’s OR library, but they understand that the solutions obtained should be reasonable, as will be discussed later.The first study focuses on identifying if there is any concept in the alternative formulation, which could be applied for guiding the search process of a solving method addressing the traditional formulation. To this end, the authors generate two versions of the same SIA addressing the traditional formulation. In the first version, (i), the search process of SIA is guided by concepts from the traditional formulation. In the second version, (ii), the search process of SIA is guided by concepts from the alternative formulation. Further details of this first study are as follows:(i)
This study requires a solving method, whose search process is closely linked to the optimization problem. The ant colony optimization (ACO) algorithm meets this requirement, being very sensitive to the heuristic information operator designed based on the problem to solve. Thus, two heuristic information operators are considered: in (i), a usual operator based on the traditional formulation and in (ii), a novel operator based on concepts from the alternative formulation.(ii)
The two ACO approaches in (i) and (ii) include the same usual operator for removing redundant sets. No operator for transforming unfeasible solutions into feasible ones is considered because ACO does not generate them.(iii)
The two ACO approaches in (i) and (ii) are applied for solving Beasley’s OR library. The results obtained were analysed through a widely accepted statistical method. Both approaches were tuned through the automatic method iterated F-Race, preventing errors from a manual method [12].The second study focuses on identifying if there is any concept in the alternative formulation, which could be considered for designing the operators needed for transforming unfeasible solutions into feasible ones while removing redundant columns. Note that this type of operators is widely applied in most SIAs solving SCP. To this end, the authors generate two versions of the same SIA addressing the traditional formulation. In the first version, (iii), SIA considers the widely applied operator proposed in Beasley and Chu [10]. In the second version, (iv), SIA considers a novel operator inspired by concepts from the alternative formulation. Further details of this second study are as follows:(i)
The second study requires a solving method, which could generate unfeasible solutions. The artificial bee colony (ABC) is one of the many metaheuristics meeting this requirement. Thus, two different feasibility operators are considered in (iii) and (iv).(ii)
The two ABC approaches in (iii) and (iv) are applied for solving Beasley’s OR library. The results obtained were analysed through a widely accepted statistical method. In this case, the parameter configuration is taken from the literature (see [13]) because the feasibility operator is considered as an external tool.To summarize, the motivation of this research is to identify if there is any concept from the alternative formulation, which could be used to solve the traditional SCP problem. To the best of our knowledge, this is the first work performing this research. Figure1 summarizes the main tasks performed in the two studies. The contributions to the field are as follows:(i)
A first study is proposed to identify concepts of interest in the alternative SCP formulation, which could be applied for guiding a search method addressing the traditional SCP formulation. The study results in that the gain concept in the alternative SCP formulation is useful for guiding the search, outperforming the results obtained by a usual heuristic information operator from the literature.(ii)
A second study is proposed to identify concepts of interest in the alternative SCP formulation, which could be considered for designing feasibility operators. The study results in that the gain concept in the alternative SCP formulation is useful for designing this type of operators, outperforming a usual operator in the literature. This contribution is especially interesting because this type of operators is widely applied in the metaheuristic SCP field as a black-box method.Figure 1
Summary of the main tasks performed in the two studies in this paper.These two contributions are especially interesting for future works, implementing techniques for solving the traditional SCP formulation. From the first study, it is shown that the gain concept in the alternative SCP formulation is useful for guiding the search. That means that this concept could be considered during the design of novel solving methods for SCP. From the second study, it is shown that the gain concept is useful for designing feasibility operators. That means that this concept could be considered to improve techniques already shown to be useful for solving the problem, as well as proposing novel feasibility operators. As stated before, the second future scope line is especially interesting because feasibility operators are widely applied in the literature as black-box techniques outside the solving method.The rest of this paper is structured as follows. Section2 discusses related work. In Section 3, a formal statement of both SCP formulations is provided. In Section 4, the main aspects of the ACO algorithm in the first study are discussed. Section 5 discusses the main aspects of the ABC algorithm in the second study. In Section 6, the experimental methodology followed is discussed and the solution quality results are analysed. Finally, Section 7 concludes and introduces future works. Table 1 includes a summary of the notation considered throughout this work.Table 1
Notation.
⋅Cardinal of a given set.αRelative importance of pheromone trails,α≥0.αiThe set of columns that rowi∈I covers, αi⊆J.ABinary matrix of m-rows and n-columns. The rows are the elementsE of the universe and the columns are the subsets S.abcaddPercentage of columns to be added during the generation of a solution in ABC.abceliPercentage of columns to be removed during the generation of a solution in ABC.aηjtHeuristic factor of columnj∈Rt−1 at step t≥0 for the alternative formulation, ηajt>0.ai,jValue in the celli,j of A. It equals 1 if the j-th column covers the i-th row and 0 otherwise, i∈I, j∈J.argmax⋅Point/points in which a function gets its maximum value/values.argmin⋅Point/points in which a function gets its minimum value/values.aϕjtThe sum of the gains of covering the noncovered rows which could be covered by columnj∈Rt−1 at t≥0.βRelative importance of heuristic information,β≥0.CSet of costs,C=c1,c2,…,cn.cηjtHeuristic factor of columnj∈Rt−1 at step t≥0 for the classical formulation, ηcjt>0.cjCost associated to thej-th column, cj∈ℝ+,j∈J.cmineiCost of the cheapest set among the sets coveringei, cminei∈C, i∈I.cϕjtNumber of noncovered rows which could be covered by columnj∈Rt−1 at step t≥0.ΔtSolution generated by an ant at stept≥0, Δt⊆J.ΔA solution to the problem,Δ⊆J.ϵRatio coefficient,ϵ∈0,1.ηjtHeuristic factor of columnj∈Rt−1 at step t≥0, ηjt>0.EUniverse of elements,E=e1,e2,…,em.eii-th element of E, ei∈E, i∈I.evals¯Average fitness evaluations needed for reaching the best solution found during the exploration.f1Fitness function of the classical SCP formulation,f1∈ℝ+.f1′Fitness function of the alternative SCP formulation,f1′∈ℝ.giGain of covering an elementei, gi∈ℝ+, i∈I.IRow set,I=1,2,…,m.IjRow set covered by columnj∈J, Ij⊆I.ipvPercentage of improvement by considering the alternative approach of the algorithm instead of the default version.JColumn set,J=1,2,…,n.LThe best solution found from the beginning of the algorithm,L⊆J.limitThreshold value based on trials for deciding if a worker bee is transformed into a scout one in ABC,limit>0.mCardinal ofE or number of rows.nCardinal ofS or number of columns.nwNumber of worker bees in ABC,nw≤psabc.ωjAmount of pheromone put on columnj∈Rt−1, ωj≥0.ψVery small positive constant,ψ∈ℝ+.psabcPopulation size in ACO.psacoPopulation size in ABC.QMetricLandscape solution quality metric,QMetric∈0,1.qRandom number uniformly distributed in0,1.q0Parameter determining the relative importance of exploitation versus exploration,q0∈0,1.ρPheromone persistence,ρ∈0,1.RtSet of unselected columns inΔt, Rt⊆J, t≥0.rpd¯Average RPD from a distribution,rpd¯∈0,1.rpdaAverage RPD of algorithma, with a∈d−ACO,n−ACO.rpdbAverage RPD of algorithma, with b∈d−ACO,n−ACO.rpdcAverage RPD of algorithma, with c∈d−ABC,n−ABC.rpddAverage RPD of algorithma, with c∈d−ABC,n−ABC.rpdminMinimum RPD from a distribution,rpdmin∈0,1.rpdmaxMaximum RPD from a distribution,rpdmax∈0,1.SSet of subsets,S=s1,s2,…,sn, ∪S=E.sjj-th subset of S, sj∈S, sj⊆E, j∈J.SRateLandscape rate of success,SRate∈0,1.SSpeedLandscape speed of reaching a solution,SSpeed∈0,1.τjPheromone trail of columnj∈Rt−1, τj>0.tConstruction step in ACO,t≥1.times¯aAverage execution time of algorithma, with a∈d−ACO,n−ACO.times¯bAverage execution time of algorithmb, with a∈d−ACO,n−ACO.times¯cAverage execution time of algorithmc, with c∈d−ABC,n−ABC.times¯dAverage execution time of algorithmd, with d∈d−ABC,n−ABC.VNumber of uncovered rows in a solution,V≤m.VtSet of uncovered rows inΔt, Vt⊆I, t≥0.ξiNumber of columns in a solutionΔ that cover the row i∈I, ξi≤n.XAn SCP solution expressed as binary vector,X=x1,x2,…,xn.xjj-th element of X. It equals 1 if sj is part of the solution X and 0 otherwise, j∈J.yiVariable equaling 1 if the elementei is covered in X and 0 otherwise, i∈I.ζtColumn provided by SROM at stept≥0, ζt∈Rt−1.z¯Average cost obtained from a distribution,z¯∈ℝ+.zmaxMaximum cost obtained from a distribution,zmax∈ℝ+.zminMinimum cost obtained from a distribution,zmin∈ℝ+.zoptOptimum solution of a given instance,zopt∈ℝ+.ztColumn selected at stept≥0, zt∈Rt−1.


## 2. Related Work

The literature about SCP is extensive. Some authors considered exact algorithms, such as branch-and-bound and branch-and-cut techniques [14–16] or linear programming [17–19]. More recently, Caprara et al. [20] compared several exact algorithms, concluding that the best exact technique was CPLEX.It is well known that exact techniques require excessive computer resources on large problems. Therefore, much effort was focused on exploring heuristic and metaheuristic algorithms, which could find near-optimal (or even optimal) solutions for large problems in reasonable computing time.Starting from heuristic methods, Chvatal [7] applied a classical GH. Although GHs are simple and fast to implement, they seldom produce good quality solutions. Some researchers tried to improve GHs by adding randomness (see e.g., [9, 21–24]). Highly sophisticated heuristics based on Lagrangian relaxation were also considered, yielding very good solutions (see e.g., [20, 25–27]). From this brief review, it is shown that the number of proposals considering heuristic methods is limited for SCP in the last years. Note that in other optimization problems, the proposal of heuristics is usual (e.g., [28]). This situation is opposite for metaheuristics, acquiring a great relevance during the last decades [29]. Thus, metaheuristics were applied to fields as networking [30], biological ontology alignment [31], shop scheduling [32], chemical analysis [33], and image encryption [34].Metaheuristics combine effectiveness exploring the search space and basic heuristic methods. Such techniques are usually split into three large groups: evolutionary algorithms (EAs), trajectory algorithms (TAs), and SIAs. To solve SCP, some authors considered EAs (see e.g., [10, 35–37]). Other authors applied TAs (see e.g., [38, 39]). However, the most widely applied metaheuristics for solving SCP are SIAs. Some examples are the artificial bee colony (ABC) algorithm [13, 40, 41], the ant colony optimization (ACO) algorithm [42–44], the firefly algorithm (FA) [45, 46], the teaching-learning-based optimization (TLBO) algorithm [47, 48], the electromagnetism-like (EM-like) algorithm [49, 50], the shuffled frog leaping algorithm (SFLA) [51], the fruit fly optimization algorithm (FFOA) [52], the cuckoo search algorithm (CSA) [53, 54], the cat swarm optimization (CSO) algorithm [55, 56], the jumping particle swarm optimization (JPSO) method [57], the black hole optimization [54, 58], and the monkey search algorithm [59].Analysing the previous contributions according to the results obtained, exact algorithms provided excellent results, solving reduced SCP problems. Focusing on larger SCP problems addressed by approximate techniques (heuristics and metaheuristics), the authors check that heuristics do not provide as good results as the more sophisticated metaheuristics. Thus, the best results were usually obtained by SIAs. In this line, we should mention the valuable contributions of Naji-Azimi et al. [48, 49] and Balaji and Revathi [57] who got optimal or near-optimal solutions for classical SCP benchmarks.All the works listed before have in common that they considered the traditional SCP formulation. On the contrary, the alternative formulation received limited attention. As far as the authors know, there are only two works considering the alternative formulation. In Bilal et al. [60], they solved an SCP variant through an iterated tabu-search metaheuristic. In Crawford et al. [61], they compared the results obtained solving the traditional and alternative formulations through the ACO algorithm.The research presented in this paper was inspired by a very preliminary work discussed before (see Crawford et al. [61]). In this contribution, there is no study regarding the existence of concepts in the alternative formulation, which could be considered for solving methods addressing the traditional formulation. In Lanza-Gutierrez et al. [56], the authors applied an SIA to solve SCP by a CSO algorithm but with a completely different approach.


## 3. Set Covering Problem Statements

LetI=1,2,…,m and J=1,2,…,n be the row and column sets, respectively. Let E=e1,e2,…,em be a universe of m elements and let S=s1,s2,…,sn be a collection of n subsets of E, such that sj⊆E and ∪S=E, with j∈J. Each subset sj has a non-negative cost associated cj∈C, where C=c1,c2,…,cn.The optimization problem is formally defined by assuming a binary matrixA of m-rows and n-columns, where the rows are the elements of the universe and the columns are the subsets. Let aij be the value in the cell i,j of A given by(1)aij=1,ifei∈sj,0,otherwise,for i∈I and j∈J, where ei∈E. Thus,(2)A=a11…a1n⋮⋱⋮am1…amn.The objective of SCP is to find a subset of S covering (containing) all the elements ofE at a minimal cost. A solution to SCP is usually expressed as a binary vector X=x1,x2,…,xn, where(3)xj=1,if the setsjis part of the solution,0,otherwise.Then, the cost of the solutionX is(4)∑j∈Jcjxj.Next, we give a formal statement of the two SCP formulations.


### 3.1. Traditional Formulation

The SCP fitness function is(5)f1=∑j∈Jcjxj,f1∈ℝ+.Then, givenm elements and n subsets, the objective is to find a collection of subsets to(6)minf1,subject to(7)∑j∈Jaijxj≥1,∀i∈I,(8)xj∈0,1,∀j∈J.The constraint in equation (7) ensures that each row is covered by at least one column. If this constraint is not satisfied, the solution is considered unfeasible. The constraint in equation (8) is only for the integrity of the mathematical programming. Hence, this equation does not need to be addressed as a constraint in heuristic approaches.


### 3.2. Alternative Formulation

In this formulation, covering an element is identified with collecting a gain at a given cost. Letcminei∈C be the cost of the cheapest set among the sets covering the element ei given by(9)cminei=argmincj∈Caijxjcj>0,∀j∈J,where argmin⋅ provides the point/points in which a function gets its minimum value/values. Then, the gain gi∈ℝ+ of covering an element ei is(10)gi=cminei+ψ,where ψ∈ℝ+ is a very small positive constant. Based on this gain concept, the SCP fitness function is(11)f1′=∑i∈Igiyi−∑j∈Jcjxj,f1′∈ℝ,where(12)yi=1,ifeiis covered in the solutionX,0,otherwise.Then, givenm elements and n subsets, the objective is to find a collection of subsets to(13)maxf1′,subject to(14)yi≤∑j∈Jai,jxj,∀i∈I,(15)xj,yi∈0,1,∀i∈I,∀j∈J.The constraints in equations (14) and (15) are only for the integrity of the mathematical programming. According to this formulation, there are no unfeasible solutions as happens with the traditional formulation. Note that unfeasible solutions still exist for the problem. However, the alternative formulation penalizes such issue instead of discarding the solution. Moreover, it also penalizes directly redundant sets beyond having a higher cost as occurs for the traditional formulation. Thus, the use of redundancy removal operators is not needed, in contrast to the traditional formulation, where it is highly recommended.


## 3.1. Traditional Formulation

The SCP fitness function is(5)f1=∑j∈Jcjxj,f1∈ℝ+.Then, givenm elements and n subsets, the objective is to find a collection of subsets to(6)minf1,subject to(7)∑j∈Jaijxj≥1,∀i∈I,(8)xj∈0,1,∀j∈J.The constraint in equation (7) ensures that each row is covered by at least one column. If this constraint is not satisfied, the solution is considered unfeasible. The constraint in equation (8) is only for the integrity of the mathematical programming. Hence, this equation does not need to be addressed as a constraint in heuristic approaches.


## 3.2. Alternative Formulation

In this formulation, covering an element is identified with collecting a gain at a given cost. Letcminei∈C be the cost of the cheapest set among the sets covering the element ei given by(9)cminei=argmincj∈Caijxjcj>0,∀j∈J,where argmin⋅ provides the point/points in which a function gets its minimum value/values. Then, the gain gi∈ℝ+ of covering an element ei is(10)gi=cminei+ψ,where ψ∈ℝ+ is a very small positive constant. Based on this gain concept, the SCP fitness function is(11)f1′=∑i∈Igiyi−∑j∈Jcjxj,f1′∈ℝ,where(12)yi=1,ifeiis covered in the solutionX,0,otherwise.Then, givenm elements and n subsets, the objective is to find a collection of subsets to(13)maxf1′,subject to(14)yi≤∑j∈Jai,jxj,∀i∈I,(15)xj,yi∈0,1,∀i∈I,∀j∈J.The constraints in equations (14) and (15) are only for the integrity of the mathematical programming. According to this formulation, there are no unfeasible solutions as happens with the traditional formulation. Note that unfeasible solutions still exist for the problem. However, the alternative formulation penalizes such issue instead of discarding the solution. Moreover, it also penalizes directly redundant sets beyond having a higher cost as occurs for the traditional formulation. Thus, the use of redundancy removal operators is not needed, in contrast to the traditional formulation, where it is highly recommended.


## 4. Ant Colony Optimization

The ACO algorithm is inspired by ant colony behaviours. The ACO process is focused on the search of the optimal path in a graph based on an artificial ant colony. Thus, ants work cooperatively and communicate through heuristic information depending on the problem and pheromone trails. Pheromone trails are a type of distributed information, which is dynamically updated by the ants. Pheromones keep the experience gained during the search process while remarking promising areas of the search space.LetΔt−1⊆J be the solution generated by an ant at construction step t−1≥0. Let Vt−1⊆I be the set of uncovered rows in Δt−1. Let Rt−1⊆J be the set of unselected columns in Δt−1. Reviewing the scientific literature [42, 62], a usual heuristic information expression for a column j∈Rt−1 at step t is(16)cηjt=cϕjtcj,where cϕjt is the number of noncovered rows in Δt−1, which could be covered by column j at step t. This value is(17)cϕjt=Ij∩Vt−1,where ⋅ is the cardinal of a set and Ij denotes the row set covered by column j, for j∈J and Ij⊆I.In this work, we propose a heuristic information inspired by the gain concept from the alternative formulation introduced inSection 3.2 as(18)aηjt=aϕjtcj,where aϕjt is the sum of the gains of covering the noncovered rows in Δt−1 by column j at step t. Thus,(19)aϕjt=∑i∈Ij∩Vt−1gi,where gi is given in equation (10).To simplify the notation, we define the heuristic information for a columnj at step t based on whether we consider the traditional formulation or the alternative one. That is,(20)ηjt=cηjt,if traditional formulation,aηjt,if alternative formulation.Algorithm1 shows the procedure of a general ACO. Next, the main steps are detailed.(1)
Initialization: in the beginning, we propose to preprocess the SCP instances by using column domination and column inclusion [18]. Next, the algorithm parameters are initialized. Traditionally, ACO algorithms do not include an initialization step to generate the psaco solutions in the population. Instead, pheromone trails are randomly assigned and then solutions are generated according to this random information. That means that the algorithm could need to run some iterations before having the right information about the solution component quality. At this point, we propose to include a greedy population initialization step in ACO based on Lu and Vasko [48]. This step corresponds to line 1 of Algorithm 1.(2)
Solution construction method: each ant starts with an empty solution where columns are added iteratively until all rows are covered. Consequently, this strategy causes all solutions generated to be feasible. Most ACO-based algorithms consider a similar state transition rule, preferring solution components with high pheromone and heuristic values (see e.g., [42, 62]. A possible way to generate solutions is the single row oriented method (SROM) proposed by Ren et al. [43]. In that work, it was demonstrated that SROM reduces the computation burden compared to other methods. Thus, SROM is used in this paper as the solution construction method. Additionally, we also consider the ant colony system (ACS) proposed by Dorigo and Gambardella [63] as an extension of the ACO algorithm. ACS includes a pseudo-random-proportional rule, providing a direct way to balance between exploration and exploitation during the selection of the solution component. If zt∈Rt−1 denotes the column selected at step t, then the ACS rule is(21)zt=argmaxj∈Rt−1τjαηjtβ,ifq≤qoexploitation,ζt,otherwiseexploration,whereq is a random number uniformly distributed in 0,1, q0∈0,1 is a parameter determining the relative importance of exploitation versus exploration, ζt∈Rt−1 is the column provided by SROM at step t, and argmax⋅ provides the point/points in which a function gets its maximum value/values. Thus, if q≤q0, then it returns the nonselected column having the highest value of τjαηjtβ at step t, where τj>0 denotes the pheromone trail of column j and α≥0 and β≥0 denote the relative importance of pheromone trails and heuristic information, respectively. This step corresponds to line 4 of Algorithm 1.(3)
Local search: it is well known that local search is effective to improve ACO performance. We consider the local search proposed by Ren et al. [43], where for each column in Δt, the algorithm determines if the column should be removed or replaced by one or more columns while keeping solution feasibility. This step corresponds to line 5 of Algorithm 1.(4)
Update pheromone trails: we consider that pheromone trails are updated based on the max-min ant system (MMAS) approach proposed by Stützle and Hoos [64]. In this method, after each ant generates a full solution, all pheromone trails are decreased uniformly to simulate evaporation, forgetting part of the historical experience. Next, a small amount of pheromone is deposited on the columns corresponding to the best solution found. To this end, MMAS considers the best solution found in the current iteration, instead of the best solution found from the beginning of the algorithm. We opted for the second option as did Ren et al. [43]. Thus, the search can concentrate fast around the best solution found. This strategy could result in a bad performance if the algorithm is trapped in bad solution areas. However, this risk is reduced due to the ACS strategy detailed in Step 2. Formally, pheromone trails are updated following(22)τj=ρτj+ωj,∀j∈J,where ρ∈0,1 is the pheromone persistence and ωj≥0 is the amount of pheromone put on column j provided in Stützle and Hoos [64]. Additionally, they also proposed that the range of pheromone trails is in 1/1−ρ∑j∈Lcj,ϵ/1−ρ∑j∈Lcj, where ϵ∈0,1 denotes a ratio coefficient and L is the best solution found from the beginning of the algorithm, L⊆J. This step corresponds to line 7 of Algorithm 1.Algorithm 1: The ACO algorithm.
Initializewhile not stop condition dofor each ant in the nest dogenerate a new solutionapply local search to the new solutionend forupdate pheromone trailsend whilereturn the best solution found


## 5. Artificial Bee Colony

The ABC algorithm is inspired by honey bee behaviours, the search process being guided by three types of artificial bees: workers, onlookers, and scouts. The general procedure of ABC is shown in Algorithm2. It starts by generating an initial population of psabc solutions. For every row, a random column with covering possibilities is selected until all rows are covered. Next, along iterations, the population is managed by nw−psabc workers and 1−nw onlookers, which are randomly recruited in each iteration. The behaviour of each bee is as follows:(i)
A worker takes a random solution from the population to generate a new solution by adding a random number of columns between 0 andabcadd (in percentage) of columns in the SCP instance. This step is followed by an elimination of random columns between 0 and abceli (in percentage) of columns in the SCP instance. The fitness value of the individual generated by the worker is obtained. In the case that the fitness value of the new individual is better than the previous individual assigned to the worker, then the new individual replaces the previous one. In the opposite case, the counter is increased for the number of trials for improving the current solution. Otherwise, the counter is set to zero. If such counter reaches the limit threshold, the worker is transformed into a scout bee.(ii)
An onlooker generates a new solution following a similar procedure as for workers, but selecting the solution with probability to its quality, instead of randomly. The concept of thelimit threshold is not used in onlookers.(iii)
A scout discards its current solution and generates a new one by following the same strategy as for generating the initial population. As expected, the counter of trials is initialized to zero.Algorithm 2: ABC algorithm.
Generatepsabc initial solutionswhile not stop condition doRecruitnw−psabc worker beesRecruit1−nw onlooker beesrecruit scout bees if neededupdate the best solution foundend whilereturn the best solution foundAs both workers and onlookers can generate unfeasible solutions because of the random elimination of columns, it is mandatory to manage this issue. Crawford et al. [13] proposed to consider the usual heuristic by Beasley and Chu [10] for transforming unfeasible solutions into feasible ones while reducing the cost of the solution in a later step. This heuristic is shown in Algorithm 3. Here, the first stage in lines 3−7 transforms an unfeasible solution into a feasible one. The second stage in lines 8−12 removes redundant columns. In this algorithm, note that Δ, αi, and ξi are the set of columns in a solution, the set of columns that row i∈I covers, and the number of columns in Δ that cover the row i, respectively.Algorithm 3: Heuristic operator for solution feasibility in ABC.
initializeξi=Δ∩αi,∀i∈IinitializeV=i|ξi=0,∀i∈Ifor each row i∈V in increasing order of idofind the first columnj in αi minimizing equation (23)-default or (24)-proposaladdj to Δsetξi=ξi+1,∀i∈Ij, and V=V−Ijend forfor each column j∈Δ in decreasing order of jdoifξi≥2,∀i∈IjthensetΔ=Δ−j and ξi=ξi−1,∀i∈Ijend ifend forreturnΔ, which is a feasible SCP solution, without redundant columnsFocusing on the first stage, the steps required to make a solution feasible include the identification of uncovered rows and the addition of columns to the solution so that all rows are covered. The search for the missing columns in the proposal of Beasley and Chu [10] is guided by(23)mincjIj∩V,where V is the number of noncovered rows in the solution, i.e., the ratio between the cost of a column and the number of noncovered rows, which could be covered by such column.As an alternative strategy, this paper proposes to guide the search based on the concepts from the alternative SCP formulation, that is,(24)mincj∑i∈Ij∪Vgi,i.e., the ratio between the cost of a column and the sum of the gains of covering the noncovered rows by such column.


## 6. Experimentation

This section discusses the experimental methodology and analyses the results obtained in the first and second studies.


### 6.1. Experimental Methodology

We apply the two approaches in each study for ACO and ABC algorithms to solve Beasley’s OR library. This dataset is widely used to report empirical results in the current literature (see e.g. [9, 40, 48]). This library includes 65 non-unicost instances generated randomly, as detailed in Table 2. For further details about the random generation of these instances, see [18, 65]. For each instance in the library, the number of rows, the number of columns, and the cost of each column are provided. Additionaly, for each row, the number of columns that covers and also the list of columns which cover that row are also provided. For a complexity study of the search space in this benchmark, we refer readers to the work by Finger et al. [66], which considered the fitness-distance correlation landscape metric to this end. In Table 2, “Density (%)” contains the percentage of 1′s in the A matrix in equation (2). “Optimal solution” shows two possible values, known and unknown, according to whether the instances have a solution tested to be optimal, or instead it could not be checked because of problem complexity. Thus, we only know the best historical solutions found for the sets nrg and nrh.Table 2
Beasley’s OR library description.
Instance setNumber of instancesmnCost rangeDensity (%)Optimal solution4102001,000[1, 100]2.00Known5102002,000[1, 100]2.00Known652001,000[1, 100]5.00Knowna53003,000[1, 100]2.00Knownb53003,000[1, 100]5.00Knownc54004,000[1, 100]2.00Knownd54004,000[1, 100]5.00Knownnre55005,000[1, 100]10.00Knownnrf55005,000[1, 100]20.00Knownnrg5100010,000[1, 100]2.00Unknownnrh5100010,000[1, 100]5.00UnknownWe combine two stop condition criteria for performing the experimentation: reaching a given number of fitness evaluations or getting the optimal solution. If at least a condition holds, the algorithm ends. For ACO, we assume 10,000 fitness evaluations as a stop condition. As we will discuss later, this value is enough for performing the experimentation. For ABC, we consider 500 iterations based on Crawford et al. [13].Before running the experimentation, we should configure both algorithms. In the case of ABC, we can assume the parameters provided in Crawford et al. [13] for the two approaches of ABC considered here because (i) the authors also solved SCP and (ii) the approach based on the alternative formulation only modifies the heuristic operator for solution feasibility and the operators guiding the search are not modified. In the case of ACO, we should configure the two approaches of ACO considered here because (i) we do not have any set of parameters from previous works for the approach of ACO used and (ii) the approach based on the alternative formulation modifies how the search is performed in comparison to the traditional one, and then we should configure the two approaches independently.Thus, for the first study, we considerpsabc=200, nw=100, limit=50, abcadd=0.5%, and abceli=1.2% of Crawford et al. [13]. For the second study, we get the parameters of the two ACO approaches using F-Race. This method configures a metaheuristic starting with a set of candidate values for each parameter. Then, it discards bad performance configurations as soon as statistically sufficient evidence is reached against them, focusing on the most promising ones.Concretely, we consider the iterated F-Race implementation for R software by López-Ibáñez et al. [67]. Following the authors’ recommendations, we divided the benchmark into three groups according to the problem size (m×n) to get a consistent configuration. Thus, Group A includes instance sets 4, 5, and 6; Group B includes instance sets a, b, c, and d; and, finally, Group C includes instance sets nre, nrf, nrg, and nrh. Table 3 shows the candidate values for each parameter based on previous works [43] and the configurations obtained for each group and ACO approach. Note that d-ACO denotes ACO with the traditional heuristic information expression and n-ACO denotes ACO with the alternative heuristic information expression.Table 3
F-Race settings and configurations obtained for each ACO approach.
ParameterCandidate valuesd-ACOn-ACOABCABCα0.25, 0.50, 1.00, 2.00, 5.00, 8.001.001.001.001.001.001.00β1.00, 2.00, 5.00, 8.00, 10.00, 13.008.008.005.008.008.008.00ρ0.80, 0.85, 0.90, 0.95, 0.98, 0.99, 0.995, 0.9990.950.900.900.980.990.90q00.10, 0.25, 0.50, 0.75, 0.90, 0.95, 0.990.500.750.500.900.900.25ϵ0.0001, 0.0005, 0.001, 0.002, 0.005, 0.0100.0010.0050.0050.0050.0050.001psaco5, 10, 20, 50, 100, 150, 200, 250201010015015050Once both ACO approaches are configured, 30 independent runs are performed for each instance and algorithm. Next, we analyse if there are significant differences between the behaviour of the two algorithms regarding solution quality and execution time for each instance. To this end, the authors consider the Wilcoxon–Mann–Whitney test [68] to validate several hypotheses. The implementation of this test is the one provided in the assessment performance tool described in Knowles et al. [69] and available in Fonseca et al. [70].However, indirectly the RPD metrics used for the assessment evaluation consider the optimal solution for the instances, which can be considered as the solutions provided by the corresponding exact techniques. Thus, the RPD metric evaluates how far the solution found by the metaheuristic is from the optimal solution provided by an exact technique.As a solution quality metric, we consider the relative percentage deviation (RPD), which evaluates how far the solution found by the metaheuristic is from the optimal solution known in the literature. The lower the RPD value, the better the solution obtained. Thus, indirectly, this metric evaluates the performance of the technique in comparison with the corresponding generic exact technique solving the same problem instance. Three RPD metrics are included: the average RPD,rpd¯∈0,1; the minimum RPD, rpdmin∈0,1; and the maximum RPD, rpdmax∈0,1. They are calculated as(25)rpd¯=z¯−zoptzopt,(26)rpdmin=zmin−zoptzopt,(27)rpdmax=zmax−zoptzopt,where z¯, zmin, and zmax denote the average solution cost, the minimum solution cost, the maximum solution cost from a distribution of 30 samples solving a instance, respectively, and zopt is the optimum solution cost of the instance. Note that the cost of the best solution found during one run is given by equation (4). Thus, although both SCP fitness formulations are different, we can compare the results obtained without loss of generality.Regarding the computing platform considered to perform the experimentation, the authors used two computing nodes in a computing cluster. Each node has two 2.33 GHz Intel Xeon E5410 with four cores each and a 1600 MHz DDR3 16 GB RAM, running a Linux operating system. All executions were performed in a single core without parallelism because the goal of this paper is not to explore parallelism. The reason for considering such unconventional infrastructure is the possibility of performing many independent executions because of the needs for the statistical test required to validate the proposal. That means that for a single execution or a reduced set of them, a conventional computer could be considered. To avoid the operating system tasks affecting the total computing time obtained during the experimentation, one core in each computing node was idle. Additionally, the authors also checked that the RAM in the computing node was enough to not apply memory swap. As expected, the computing power capacity of the processor definitively affects the time required to find the solution to the problem, most of the operations being related to CPU computing and accessing the principal memory (RAM). Note the same computing nodes are considered for all the experiments in this work to not bias the conclusions reached regarding computing time.Regarding programming languages, ACO algorithm was fully implemented in Java for Java Development Kit (JDK) 1.7. ABC algorithm was fully implemented in C. The scripts for managing the executions and collecting the results were implemented in bash. Note that the usage of two different programming languages for implementing ABC and ACO does not affect the conclusions reached in computing time. This fact is because ABC and ACO computing times are not compared in this work.


### 6.2. Analysis of the Experimental Results

Tables4 and 5 show for each instance and case study, the RPD metrics (rpd, rpdmin, rpdmax), average execution time reaching the stop condition (times), and average fitness evaluations needed for reaching the best solution found during the exploration (evals). In both tables, lower rpd¯ and times values are given in bold for each instance. In Table 5, d-ABC denotes ABC with the default heuristic feasibility operator and n-ABC denotes ABC with the heuristic feasibility operator based on the alternative SCP formulation.Table 4
RPD metrics, the average total execution time, and average number of evaluations obtained during the first study for ACO algorithm.
Instancezoptd-ACOn-ACOevals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)evals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)4_142918808450.230.230.2313501090.000.000.004_251239509000.200.000.5927002240.000.000.004_351616009160.970.191.1642007040.190.000.784_449448508800.400.200.8121008290.200.200.204_551219506800.100.000.396003400.000.000.394_656037805740.000.000.3626252400.000.000.004_743014308580.700.001.1614251180.000.000.004_849224404150.000.000.201350970.000.000.004_964151209321.250.312.3455508480.310.000.784_1051413901150.000.000.00750600.000.000.005_125348608910.400.001.5830005260.000.001.195_230249709451.490.662.3227008701.320.331.995_322620807530.220.001.3317251250.000.000.005_424227802450.000.000.0015001100.000.000.005_521111608570.470.470.477502230.000.000.475_6213640590.000.000.00300250.000.000.005_729354909010.510.341.0215758370.340.340.345_828838206530.350.000.6916501220.000.000.005_9279208230.000.000.36975780.000.000.005_1026523706170.380.000.7513501120.000.000.006_113830508021.450.001.4521753320.000.001.456_214611801220.000.000.0020251640.000.000.006_314515301280.000.000.00900700.000.000.006_4131930700.000.000.00300220.000.000.006_516111308311.240.002.4820253780.000.001.86a_125327259040.790.790.7948759760.400.400.40a_225247009081.191.191.1930009670.400.000.79a_323229259030.430.430.4357009710.430.430.43a_423415758950.430.430.4331504440.000.000.43a_523618159020.420.420.4236754780.000.000.85b_169360450.000.000.00450450.000.000.00b_276370370.000.000.00900930.000.000.00b_380320340.000.000.00300330.000.000.00b_479380380.000.000.00450440.000.000.00b_5721010.000.000.00150160.000.000.00c_122726909731.320.881.76622510340.880.880.88c_221927809790.910.910.91397510560.910.910.91c_324333059931.650.822.47577510670.820.411.23c_421924002350.000.000.0039003800.000.000.00c_521513059790.470.000.93292510520.470.470.47d_16041511741.670.001.6720254730.000.000.00d_26616752360.000.000.0018003500.000.000.00d_37277511981.391.391.3997510191.390.001.39d_462235250.000.000.00150200.000.000.00d_561600630.000.000.00675750.000.000.00nre_129100290.000.000.0050180.000.000.00nre_23016509020.000.003.3314004230.000.000.00nre_3279002160.000.000.007001700.000.000.00nre_42812004520.000.003.5710002600.000.000.00nre_528200490.000.000.00100310.000.000.00nrf_1142001180.000.000.002001120.000.000.00nrf_215100640.000.000.0075400.000.000.00nrf_31410054647.140.007.145049667.140.007.14nrf_4145002710.000.000.002001220.000.000.00nrf_51310055117.697.697.6910056147.697.697.69nrg_1176575019050.280.002.27535012500.000.000.00nrg_2154480021661.951.951.95342521711.300.651.95nrg_3166435022533.613.014.82277522533.012.414.22nrg_4168525022072.681.193.57410022172.381.192.98nrg_5168645022580.600.600.60550018300.000.000.60nrh_163365054993.171.594.76352557683.173.173.17nrh_263330054373.173.173.17210057063.173.173.17nrh_359420055113.393.393.39275057763.393.393.39nrh_458360054343.451.723.45220056643.451.723.45nrh_555425023290.000.000.00297517080.000.000.00Table 5
RPD metrics, average total execution time, and average number of evaluations obtained during the second study for ABC algorithm.
Instancezoptd-ABCn-ABCevals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)evals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)4_1429125,8084850.820.230.93124,1224470.230.230.234_25129998930.000.000.008194760.000.000.004_3516560273900.000.000.1911,1911030.000.000.004_4494128,3995350.200.000.61126,2094880.200.200.204_551211,1611020.000.000.00118,9613540.390.000.394_6560127,9885370.360.000.5428,4282540.000.000.364_7430110,9222070.930.001.16110,2241940.700.470.704_8492126,1174910.200.200.2034,2922830.000.000.204_9641128,3225260.940.002.18128,2765230.470.000.784_1051418,1621640.000.000.0055,6703330.000.000.585_1253125,02017970.400.001.58123,79217060.400.000.405_2302127,19319561.991.662.98125,85918560.990.001.325_3226123,81217131.331.331.33123,62716960.880.880.885_424217,7516500.000.000.0067602390.000.000.005_521114,9455210.000.000.0079272770.000.000.005_621319,2996840.000.000.0055752000.000.000.005_7293126,40119240.340.341.0214,7535470.000.000.005_828817,1536520.000.000.0023,5348140.000.000.005_9279124,77017540.360.360.3689613160.000.000.005_1026586,53911490.190.001.1312,4314070.000.000.006_1138124,41711981.450.002.1791,2699160.360.001.456_214687842170.000.000.0063811560.000.000.006_314514,6993590.000.000.0047761150.000.000.006_413116,9284000.000.000.003961950.000.000.006_516113,7603380.000.000.0043771060.000.000.00a_1253123,57357290.400.400.79122,22253810.400.400.40a_2252126,01663091.390.792.38126,21263460.790.001.19a_3232126,10363341.290.861.72125,82661890.430.000.86a_4234125,90862870.430.430.43124,89760040.430.430.43a_5236124,78559480.420.420.4211,14413460.000.000.00b_169120,83213,0121.450.001.45397012280.000.000.00b_276696220540.000.000.00337210430.000.000.00b_380417012960.000.000.00357211060.000.000.00b_479616619320.000.000.00396512270.000.000.00b_57231729880.000.000.0027748570.000.000.00c_1227121,97812,5890.880.441.76116,55194310.880.880.88c_2219110,30913,8990.230.001.3721,66464920.000.000.00c_3243126,72815,2461.650.412.47126,01814,8810.820.002.06c_4219126,19614,9510.460.001.8328,35576580.000.000.00c_521519,07554340.000.000.0014,54640860.000.000.00d_160597044550.000.000.00757256030.000.000.00d_266121,27231,5551.521.521.5211,34383710.000.000.00d_372122,82934,0631.391.392.7818,80813,5100.000.000.00d_462121,97632,3831.611.611.61476835100.000.000.00d_561109,45714,0771.641.641.64509036900.000.000.00nre_12927,68468,0660.000.000.00347996340.000.000.00nre_230119,319111,2136.676.676.6718,66651,9820.000.003.33nre_327120,070115,0287.417.417.4119,33953,4700.000.000.00nre_428119,063109,81210.713.5714.2910,55930,0550.000.000.00nre_528118,585106,7813.573.577.14405311,2030.000.000.00nrf_114119,200230,41714.2914.2914.29235313,7410.000.000.00nrf_215119,831238,70513.3313.3313.33195011,3370.000.000.00nrf_314119,332236,61114.2914.2921.43392923,1230.000.000.00nrf_414119,910241,66614.2914.2914.29274616,0740.000.000.00nrf_513106,58079,14115.3815.3823.08120,731248,0337.697.697.69nrg_1176128,776257,6642.842.273.41126,471235,6361.140.571.70nrg_2154128,678253,5643.252.603.90126,160233,1681.951.302.60nrg_3166134,516243,5673.613.014.22124,477217,7812.411.813.01nrg_4168135,789223,4563.572.984.17125,268224,7571.791.192.38nrg_5168126,782227,3464.173.574.76126,077232,0472.382.382.98nrh_163126,421228,3263.173.174.76145,678253,4671.591.593.17nrh_263134,282217,4563.174.764.76155,671243,4571.591.593.17nrh_359123,481237,2223.395.085.08132,451233,2451.691.693.39nrh_458143,562242,4563.453.455.17142,457231,0021.721.723.45nrh_555134,612232,2163.643.643.64143,417224,4521.821.823.64Analysing both tables regarding RPD metrics, we check that (i) n-ACO seems to outperform or match d-ACO in most instances and (ii) n-ABC seems to outperform or match d-ABC in most instances. Focusing on computing times, we reach a similar behaviour, where n-ACO appears to need a shorter time than d-ACO, except for b, c, and nrh instances, and n-ABC appears to need a shorter time than d-ABC in general. Focusing on evaluations, theevals¯ field is related to the number of iterations reached as follows. In ACO, psaco evaluations are performed for each iteration. In ABC, a number of evaluations varying between psabc and two times psabc are performed for each iteration. Thus, for ABC, the maximum number of evaluations will be a value in the range 100,000,200,000. For ACO, the maximum number of evaluations will be 10,000 as defined before. Analysing the evals¯ field, the authors reach that the number of evaluations needed is distant from the stop condition defined, and then the stop condition is adequate in both studies.Table6 shows the average RPD metrics for each instance group, where “ipv” field denotes the percentage of improvement by considering the alternative approach of the algorithm instead of the default version. Analysing this table, it is observed that (i) n-ACO provides better RPD values than d-ACO for all the groups and (ii) n-ABC also provides better RPD values than its default version. The RPD metrics obtained are in line with other works from the literature, with RPD values lower than 1.0%. In this regard, Table 7 shows the values of some recent successful approaches solving the problem. However, we should remark that the purpose of this work is not to outperform other techniques solving the standard SCP benchmark.Table 6
RPD metrics for each instance group and algorithm in both studies.
Instance grouprpd¯rpdminrpdmaxd-ACO (%)n-ACO (%)ipvd-ACO (%)n-ACO (%)ipvd-ACO (%)n-ACO (%)ipvFirst studyA0.430.0881.800.080.0363.830.790.4346.03B0.530.2846.600.360.1751.890.620.3937.24C1.861.746.541.221.173.742.491.8924.06ALL0.940.7025.690.550.4617.201.300.9030.60Second studyInstance grouprpd¯rpdminrpdmaxd-ABC (%)n-ABC (%)ipvd-ABC (%)n-ABC (%)ipvd-ABC (%)n-ABC (%)ipv (%)A0.380.1951.250.160.0756.650.660.3054.25B0.740.1974.560.500.0982.811.110.2973.77C10.711.0790.019.910.9090.9512.751.4888.39ALL3.940.4887.803.520.3590.044.840.6985.73Table 7
Review of recent approaches solving Beasley’s OR library.
Author/sSIArpd¯ (%)rpdmin (%)rpdmax (%)Farahani et al. [41]ABC0.160.01—Ren et al. [43]ACO0.200.030.39Lu and Vasko [48]TLBO20—0.06—Lu and Vasko [48]TLBO10—0.09—Naji-Azimi et al. [49]EM-like—0.20—Lu and Vasko [48]TLBO—0.28—At this point, it seems that the alternative approach of the algorithms provides better performance in both cases. However, we do not know if the differences observed are significant. To this end, the statistical methodology procedure described by Lanza-Gutierrez et al. [56] was applied. First, we removed all possible outliers. Then, we analysed the normality of data, obtaining that we cannot assume normal distribution in any case. Consequently, the median should be considered as average value for calculating z¯ in equation (25).Next, we study if there are significant differences in the solution quality of the algorithms. Starting with the first study, we consider the Wilcoxon–Mann–Whitney test with hypothesesH0: rpd¯a≥rpd¯b and H1: rpd¯a<rpd¯b, ∀a,b∈d­ACO,n­ACO with a≠b, where rpd¯a and rpd¯b are the average RPD of the algorithm a and b for a given instance, respectively. The p values obtained for each instance and ACO approach are shown in Table 8 under the title RPD analysis, where p values lower than the significance level α=0.05 are given in bold, i.e., the confidence level is 0.95. Note that the unilateral test performed between the two possibilities was the one that matches with the descriptive analysis, the other test being marked with a dash in the table. Also note that in case of equality between the average RPD values, the two unilateral tests are performed. For the second study, we consider the Wilcoxon–Mann–Whitney test with similar hypotheses as before H0: rpd¯c≥rpd¯d and H1: rpd¯c<rpd¯d, ∀c,d∈d­ABC,n­ABC with c≠d. The p values obtained are also shown in Table 9 with the same notation as in Table 8.Table 8
p values obtained analysing the differences observed regarding execution time and solution quality during the first study for the ACO algorithm.
RPD analysis (H1)Execution time analysis (H1)d-ACO< n-ACOn-ACO< d-ACOd-ACO< n-ACOn-ACO< d-ACOInst4_1—≤0.001—≤0.0014_2—≤0.001—≤0.0014_3—≤0.001—≤0.0014_4—≤0.001—≤0.0014_5—0.003—0.0064_6—≤0.001—≤0.0014_7—≤0.001—≤0.0014_8—≤0.001—≤0.0014_9—≤0.001—≤0.0014_100.5000.500—≤0.0015_1—0.004—≤0.0015_2—0.131—≤0.0015_3—≤0.001—≤0.0015_40.5000.500—≤0.0015_5—≤0.001—≤0.0015_60.5000.500—≤0.0015_7—≤0.001—≤0.0015_8—≤0.001—≤0.0015_9—0.060—≤0.0015_10—≤0.001—≤0.0016_1—0.002—0.1506_20.5000.5000.117—6_30.5000.500—≤0.0016_40.5000.500—≤0.0016_5—0.005—0.054a_1—≤0.001≤0.001—a_2—≤0.0010.006—a_30.5000.500≤0.001—a_4—≤0.001—0.001a_5—≤0.001—≤0.001b_10.5000.5000.291—b_20.5000.500≤0.001—b_30.5000.500—0.565b_40.5000.5000.106—b_50.5000.500≤0.001—c_1—≤0.001≤0.001—c_20.5000.500≤0.001—c_3—≤0.001≤0.001—c_40.5000.5000.013—c_5—0.002≤0.001—d_1—≤0.001—0.002d_20.5000.5000.124—d_3—≤0.001—0.003d_40.5000.500—0.017d_50.5000.5000.059—nre_10.5000.500—≤0.001nre_2—≤0.001—≤0.001nre_30.5000.500—0.112nre_4—0.002—0.006nre_50.5000.500—≤0.001nrf_10.5000.500—0.108nrf_20.5000.500—≤0.001nrf_30.5000.500—0.292nrf_40.5000.500—≤0.001nrf_50.5000.500≤0.001—nrg_1—≤0.001—≤0.001nrg_2—≤0.0010.261—nrg_3—≤0.0010.378—nrg_4—0.0380.574—nrg_5—≤0.001—≤0.001nrh_1—0.001≤0.001—nrh_20.5000.500≤0.001—nrh_30.5000.500≤0.001—nrh_4—0.261≤0.001—nrh_50.5000.500—0.003Table 9
p values obtained analysing the differences observed regarding execution time and solution quality during the second study for the ABC algorithm.
InstRPD analysis (H1)Execution time analysis (H1)d-ABC< n-ABCn-ABC< d-ABCd-ABC< n-ABCn-ABC< d-ABC4_1—≤0.001—≤0.0014_20.5000.500—≤0.0014_3—≤0.001—≤0.0014_40.037——0.0544_5≤0.001—≤0.001—4_6—≤0.001—≤0.0014_7—≤0.001—≤0.0014_8—≤0.001—≤0.0014_9—≤0.001—0.4594_10≤0.001—≤0.001—5_1—≤0.001—0.0015_2—≤0.001—≤0.0015_3—≤0.0010.415—5_40.5000.500—≤0.0015_50.5000.500—≤0.0015_60.5000.500—≤0.0015_7—≤0.001—≤0.0015_80.5000.5000.348—5_9—≤0.001—≤0.0015_10—≤0.001—≤0.0016_1—0.001—≤0.0016_20.5000.500—≤0.0016_30.5000.500—≤0.0016_40.5000.500—≤0.0016_50.5000.500—≤0.001a_1—0.001—≤0.001a_2—≤0.0010.479—a_3—≤0.001—0.135a_40.5000.500—0.025a_5—≤0.001—≤0.001b_1—≤0.001—≤0.001b_20.5000.500—≤0.001b_30.5000.500—0.012b_40.5000.500—≤0.001b_50.5000.500—≤0.001c_1—0.001—≤0.001c_2—≤0.001—≤0.001c_3—≤0.001—0.022c_4—≤0.001—≤0.001c_50.5000.500—0.001d_10.5000.5000.097—d_2—≤0.001—≤0.001d_3—≤0.001—≤0.001d_4—≤0.001—≤0.001d_5—≤0.001—≤0.001nre_10.5000.500—≤0.001nre_2—≤0.001—0.003nre_3—≤0.001—≤0.001nre_4—≤0.001—≤0.001nre_5—≤0.001x0.001—nrf_1—≤0.001—≤0.001nrf_2—≤0.001—≤0.001nrf_3—≤0.001—≤0.001nrf_4—≤0.001—≤0.001nrf_5—≤0.001≤0.001—nrg_1—≤0.0010.5000.500nrg_2—≤0.0010.5000.500nrg_3—≤0.0010.5000.500nrg_4—≤0.0010.5000.500nrg_5—≤0.0010.5000.500nrh_1—≤0.0010.5000.500nrh_2—≤0.0010.5000.500nrh_3—≤0.0010.5000.500nrh_4—≤0.0010.5000.500nrh_5—≤0.0010.5000.500Through the Wilcoxon–Mann–Whitney test, the differences observed regarding execution time for both algorithms are also analysed. For the first study, we define the hypothesesH0: times¯a≥times¯b and H1: times¯a<times¯b, ∀a,b∈d­ACO,n­ACO with a≠b, where times¯a and times¯b are the average execution time of the algorithm a and b for a given instance, respectively. The p values obtained for each instance and algorithm are shown in Table 8 under the title Execution time analysis, where p values are given in bold with the same criterion as before. For the second study, we consider the Wilcoxon–Mann–Whitney test with similar hypotheses as before H0: times¯c≥times¯d and H1: times¯c<times¯d, ∀c,d∈d­ABC,n­ABC with c≠d. The p values obtained are also shown in Table 9.Based on the previous statistical analysis, Table10 shows the percentage of cases where an algorithm provides the best significant performance compared to another for each study in terms of RPD and execution time. Focusing on the first study and RPD values, we verify that n-ACO provides better behaviour than d-ACO in 52.31% of cases. However, it is important to remark that d-ACO never provides better results than n-ACO, meaning that n-ACO clearly outperforms d-ACO. For execution time, n-ACO needs lower execution times than d-ACO in 55.38% of cases and d-ACO needs lower execution times than n-ACO in 23.08% of cases. This fact could mean that the alternative heuristic information needs higher execution times under certain conditions. However, most cases in which d-ACO needs lower execution times correspond with instances whose optimal solution is not reached, and then the 10,000 evaluations are performed for each algorithm, e.g., for instances a_1, a_2, a_3, c_1, c_2, c_3, c_5, nrh_1, nrh_2, nrh_3, and nrh_4. In such unfavourable cases, the differences observed are not of concern as shown in Figure 2(a). On the other hand, most cases in which n-ACO needs lower execution times correspond with instances whose optimal solution is reached. In such cases, a greater difference is observed favoring n-ACO. This fact is because n-ACO reaches the stop condition before d-ACO, e.g., for instance sets 4, 5, 6, d, nre, and nrg. Focusing on the second study, we verify that n-ABC provides better behaviour than d-ABC in 63.64% of cases, where d-ABC outperforms n-ABC in 7.27% of cases. This unfavourable situation occurs in small instances, where the search space is reduced. For execution time, n-ABC needs lower execution times than d-ABC in 69.23% of cases and d-ABC needs lower execution times than n-ABC in 4.62% of cases. As before, this unfavourable situation mainly occurs when n-ABC does not reach the optimal solution, penalizing the additional computation of the gain concept in the alternative SCP formulation. This behaviour is shown in Figure 2(b).Table 10
Percentage of cases where an algorithm provides the best significant performance compared to the other regarding solution quality and execution time.
RPD analysisExecution time analysisA (%)B (%)C (%)ALL (%)A (%)B (%)C (%)ALL (%)First studyn-ACO > d-ACO26.1513.8512.3152.31n-ACO > d-ACO33.857.6913.8555.38d-ACO > n-ACO0.000.000.000.00d-ACO > n-ACO0.0015.387.6923.08n-ACO = d-ACO12.3116.9218.4647.69n-ACO = d-ACO4.627.699.2321.54Percentage38.4630.7730.77100.00Percentage38.4630.7730.77100.00Second studyn-ABC > d-ABC23.6423.6416.3663.64n-ABC > d-ABC29.2326.1513.8569.23d-ABC > n-ABC5.450.001.827.27d-ABC > n-ABC3.080.001.544.62n-ABC = d-ABC16.3612.730.0029.09n-ABC = d-ABC6.154.6215.3826.15Percentage45.4536.3618.18100.00Percentage38.4630.7730.77100.00Figure 2
Analysis for the average execution times in each study. (a) Average execution time for each ACO approach and instance set. (b) Average execution time for each ABC approach and instance set.
(a)(b)The previous analysis is completed with the landscape study in Tables11 and 12 for the solutions obtained solving the instances through ACO and ABC, respectively. The metrics in such tables quantify solution quality (QMetric ∈0,1), the rate of success (SRate ∈0,1), and speed of reaching a solution (SSpeed ∈0,1). QMetric follows an exponential formulation which allows distinguishing between the performance of two algorithms, which obtained solutions close to the optimum fitness. SRate is defined as the number of successful runs that the algorithm reaches the optimum fitness divided by the total number of runs. SSpeed quantifies the number of evaluations taken to reach the optimum fitness. For the three metrics, the value 1 indicates the highest quality. More details about the three metrics, as well as formulation, are listed in [71]. Analysing Tables 11 and 12, we check that, in general, both n-ACO and n-ABC provide a higher or equal QMetric than d-ACO and d-ABC approaches. For SSpeed, we check that both d-ACO and d-ABC need a lower or equal number of evaluations than n-ACO and d-ABC to reach the optimum fitness. For SRate, we check that both d-ACO and d-ABC reach the optimum fitness a greater or equal number of times than n-ACO and d-ABC. That means that n-ACO and n-ABC obtained better quality solutions, are better in convergence, and provide a more robust performance than the default approaches.Table 11
Landscape metrics for each instance and ACO approach.
Instd-ACOn-ACOQMetricSSpeedSRateQMetricSSpeedSRate4_10.00080.51070.10001.00000.83660.96674_20.17770.42480.16671.00000.71901.00004_30.00190.00000.00000.44670.51190.43334_40.00270.00000.00000.01140.63000.10004_50.50290.61510.50000.56950.79790.56674_60.64730.54450.63331.00000.69310.86674_70.06690.83100.06671.00000.83820.93334_80.67510.61440.66671.00000.84251.00004_90.00050.00000.00000.10450.44000.10004_101.00000.84971.00001.00000.90801.00005_10.33360.46220.33330.63350.59030.63335_20.00000.00000.00000.00070.00000.00005_30.43340.59650.43331.00000.80980.93335_41.00000.69871.00001.00000.86501.00005_50.00000.86400.03330.63330.80660.63335_61.00000.91831.00001.00000.96151.00005_70.00090.00000.00000.00170.78000.20005_80.53400.54480.53331.00000.82151.00005_90.40170.55280.40001.00000.87751.00005_100.46690.64160.46671.00000.82160.96676_10.23590.48030.23330.56960.71150.56676_21.00000.82680.86671.00000.74770.93336_31.00000.79020.96671.00000.91301.00006_41.00000.87911.00001.00000.96451.00006_50.23550.78400.23330.53500.75160.5333a_10.00370.00000.00000.05170.00000.0000a_20.00010.00000.00000.22020.70750.2000a_30.03370.00000.00000.03370.00000.0000a_40.03060.06100.03330.67690.54400.6667a_50.03500.59550.06670.67720.61530.6667b_11.00000.91801.00001.00000.95101.0000b_21.00000.95841.00001.00000.88101.0000b_31.00000.95311.00001.00000.95951.0000b_41.00000.94871.00001.00000.94251.0000b_51.00000.99901.00001.00000.98501.0000c_10.00210.00000.00000.00860.97000.0333c_20.01200.00000.00000.01200.00000.0000c_30.00550.00000.00000.07850.00000.0000c_41.00000.69530.96671.00000.62301.0000c_50.09250.68100.03330.09180.89500.0333d_10.50690.53340.30001.00000.66350.7667d_21.00000.68610.93331.00000.72750.8000d_30.32800.80200.10000.59680.67750.4000d_41.00000.97681.00001.00000.98501.0000d_51.00000.92881.00001.00000.91151.0000nre_11.00000.99001.00001.00000.99501.0000nre_20.93190.72680.63331.00000.79060.8333nre_31.00000.86290.93331.00000.89471.0000nre_40.94990.83360.73331.00000.80860.9667nre_51.00000.98001.00001.00000.98771.0000nrf_11.00000.97171.00001.00000.97821.0000nrf_21.00000.98471.00001.00000.98981.0000nrf_30.96210.87700.33330.96210.76200.3333nrf_41.00000.94070.96671.00000.96831.0000nrf_50.94410.69800.16670.94410.86500.0667nrg_10.75280.36130.50001.00000.47600.8667nrg_20.24630.00000.00000.35550.00000.0000nrg_30.08080.00000.00000.11230.00000.0000nrg_40.17620.00000.00000.20260.00000.0000nrg_50.63740.23500.20000.85500.32030.6000nrh_10.78800.00000.00000.81350.00000.0000nrh_20.81360.00000.00000.83980.00000.0000nrh_30.81480.00000.00000.81480.27000.0333nrh_40.83920.00000.00000.84840.59000.0333nrh_51.00000.54070.96671.00000.66701.0000Table 12
Landscape metrics for each instance and ABC approach.
Instd-ABCn-ABCQMetricSSpeedSRateQMetricSSpeedSRate4_10.00010.00000.00000.00080.78730.13334_21.00000.94861.00001.00000.95981.00004_30.57910.83660.56671.00000.94541.00004_40.30680.82380.30000.01140.84410.13334_51.00000.94821.00000.43370.86420.43334_60.08460.89850.06670.74320.86560.73334_70.03330.91870.03330.00000.00000.00004_80.02540.00000.00000.70760.86620.70004_90.03350.82150.03330.06710.88490.06674_101.00000.90501.00000.53850.85140.53335_10.03490.80710.03330.33380.89120.33335_20.00000.00000.00000.10130.81830.10005_30.00000.00000.00000.00000.90690.10005_41.00000.88480.90001.00000.96741.00005_51.00000.91341.00001.00000.95751.00005_61.00000.91081.00001.00000.97271.00005_70.00110.00000.00001.00000.90680.96675_81.00000.89520.93331.00000.86980.86675_90.00290.00000.00001.00000.95171.00005_100.50020.88880.50001.00000.92960.83336_10.23350.92740.23330.50080.86860.50006_21.00000.95091.00001.00000.96811.00006_31.00000.92390.90001.00000.97641.00006_41.00000.91931.00001.00000.98071.00006_51.00000.92061.00001.00000.97781.0000a_10.03730.00000.00000.05170.00000.0000a_20.00060.00000.00000.21090.84960.2000a_30.00060.00000.00000.14760.80560.1333a_40.03060.85440.23330.03060.85770.1667a_50.03500.00000.00001.00000.92981.0000b_10.54150.87580.46671.00000.97921.0000b_21.00000.96461.00001.00000.98291.0000b_31.00000.97911.00001.00000.98241.0000b_41.00000.96821.00001.00000.97961.0000b_51.00000.98431.00001.00000.98711.0000c_10.00750.00000.00000.00860.79750.0333c_20.52500.77520.50001.00000.88520.9000c_30.00940.00000.00000.10690.59730.0667c_40.13010.75860.06671.00000.86010.7667c_51.00000.90491.00001.00000.92391.0000d_11.00000.96531.00001.00000.95781.0000d_20.32850.00000.00001.00000.93891.0000d_30.26650.00000.00001.00000.90940.8333d_40.28200.57370.06671.00000.97161.0000d_50.29630.91760.03331.00000.97361.0000nre_11.00000.88740.80001.00000.98181.0000nre_20.66840.00000.00000.93810.89120.6667nre_30.67120.00000.00001.00000.87030.8000nre_40.55550.00000.00001.00000.92280.9667nre_50.00000.00000.00001.00000.97961.0000nrf_10.88800.00000.00001.00000.98751.0000nrf_20.76320.00000.00001.00000.99001.0000nrf_30.65780.00000.00001.00000.97991.0000nrf_40.73540.00000.00001.00000.98521.0000nrf_50.76240.00000.00000.94410.97020.0333nrg_10.21340.00000.00000.40130.00000.0000nrg_20.21000.00000.00000.22950.00000.0000nrg_30.13450.00000.00000.21220.00000.0000nrg_40.12340.00000.00000.25290.00000.0000nrg_50.12450.00000.00000.23430.00000.0000nrh_10.18760.00000.00000.23420.00000.0000nrh_20.19840.00000.00000.23110.00000.0000nrh_30.19760.00000.00000.25420.00000.0000nrh_40.17640.00000.00000.21030.00000.0000nrh_50.16480.00000.00000.22310.00000.0000Up to this point, we know that the concepts included in the alternative formulation positively affect the search process in the first study, where the concepts from the alternative formulation are considered for guiding purposes. A mapping of the solutions visited by n-ACO and d-ACO could help to effectively show how the two approaches explore the search space. To this end, we consider the mapping method (MaM) proposed by Autuori et al. [72], where a mapping function converts a multidimensional space solution in one dimensional space through two steps: (i) a binary conversion is applied to the solution (for SCP, the binary encoding is straightforward, where a column takes the value 1 if it is considered in the solution and 0 otherwise) and (ii) the binary Hamming distance is calculated between such binary solution and a reference solution randomly generated, resulting in a new representation of the solution. This representation is used for identifying the different zones explored by the algorithms. Note that the number of zones corresponds with the number of elements in the binary encoding (the number of columns). To this end, all the binary representations are added, resulting in a frequency diagram, showing how usually the algorithm includes a column in a solution.Table13 shows three metrics analysing the frequency diagrams previously generated for each ACO approach and an instance from each group 4, 5, 6, a, b, c, d, nre, nrf, nrg, and nrh. Note that the frequency diagrams were generated using all the solutions built in the 30 runs for each algorithm. The metrics used were also proposed by Autuori et al. [72] and are (i) the number of unexplored zones (“uz”), the number of explored zones (“ez”), and the number of large explored zones (“lez”). The metrics are related as follows. Convergence is considered high if lez is few in number. Diversity is considered good if the number of ez is large. Analysing Table 13, we check that ez is usually higher for n-ACO than for d-ACO, meaning that d-ACO improves diversity during the search compared to the traditional approach. This fact is especially relevant for large instances, as occurs for nrg_1 and nrh_1, where ez metric is significantly large. Focusing on lez, we check that the differences observed between both approaches are not as pronounced as for ez. However, such differences could mean that d-ACO has a lack of convergence during the search, and then future authors should manage this fact.Table 13
Mapping analysis of the two ACO approaches, when solving a instance from each group.
Instn-ACOd-ACOuzezlezuzezlez4_1511224150123435_1521715849174646_158174465118150a_11092975911329371b_13292357635121360c_11294179915039697d_15692998158628260nre_12286164912197253106nrf_1465814581454326098nrg_114339151727281620200nrh_1440860214038261184163From these two studies solving the traditional SCP, we verify that (i) the concepts from the alternative formulation are useful in guiding the search process of a metaheuristic and (ii) the concepts from the alternative formulation are useful in updating a usual heuristic feasibility operator from the literature. The improvement in both studies was observed in terms of the solution quality, the rate of success, and the speed of reaching a solution. The conclusion in (ii) is especially interesting because this type of operators is generically applied in metaheuristics (generating unfeasible solutions), and the proposal could be directly incorporated into many solving methods.


## 6.1. Experimental Methodology

We apply the two approaches in each study for ACO and ABC algorithms to solve Beasley’s OR library. This dataset is widely used to report empirical results in the current literature (see e.g. [9, 40, 48]). This library includes 65 non-unicost instances generated randomly, as detailed in Table 2. For further details about the random generation of these instances, see [18, 65]. For each instance in the library, the number of rows, the number of columns, and the cost of each column are provided. Additionaly, for each row, the number of columns that covers and also the list of columns which cover that row are also provided. For a complexity study of the search space in this benchmark, we refer readers to the work by Finger et al. [66], which considered the fitness-distance correlation landscape metric to this end. In Table 2, “Density (%)” contains the percentage of 1′s in the A matrix in equation (2). “Optimal solution” shows two possible values, known and unknown, according to whether the instances have a solution tested to be optimal, or instead it could not be checked because of problem complexity. Thus, we only know the best historical solutions found for the sets nrg and nrh.Table 2
Beasley’s OR library description.
Instance setNumber of instancesmnCost rangeDensity (%)Optimal solution4102001,000[1, 100]2.00Known5102002,000[1, 100]2.00Known652001,000[1, 100]5.00Knowna53003,000[1, 100]2.00Knownb53003,000[1, 100]5.00Knownc54004,000[1, 100]2.00Knownd54004,000[1, 100]5.00Knownnre55005,000[1, 100]10.00Knownnrf55005,000[1, 100]20.00Knownnrg5100010,000[1, 100]2.00Unknownnrh5100010,000[1, 100]5.00UnknownWe combine two stop condition criteria for performing the experimentation: reaching a given number of fitness evaluations or getting the optimal solution. If at least a condition holds, the algorithm ends. For ACO, we assume 10,000 fitness evaluations as a stop condition. As we will discuss later, this value is enough for performing the experimentation. For ABC, we consider 500 iterations based on Crawford et al. [13].Before running the experimentation, we should configure both algorithms. In the case of ABC, we can assume the parameters provided in Crawford et al. [13] for the two approaches of ABC considered here because (i) the authors also solved SCP and (ii) the approach based on the alternative formulation only modifies the heuristic operator for solution feasibility and the operators guiding the search are not modified. In the case of ACO, we should configure the two approaches of ACO considered here because (i) we do not have any set of parameters from previous works for the approach of ACO used and (ii) the approach based on the alternative formulation modifies how the search is performed in comparison to the traditional one, and then we should configure the two approaches independently.Thus, for the first study, we considerpsabc=200, nw=100, limit=50, abcadd=0.5%, and abceli=1.2% of Crawford et al. [13]. For the second study, we get the parameters of the two ACO approaches using F-Race. This method configures a metaheuristic starting with a set of candidate values for each parameter. Then, it discards bad performance configurations as soon as statistically sufficient evidence is reached against them, focusing on the most promising ones.Concretely, we consider the iterated F-Race implementation for R software by López-Ibáñez et al. [67]. Following the authors’ recommendations, we divided the benchmark into three groups according to the problem size (m×n) to get a consistent configuration. Thus, Group A includes instance sets 4, 5, and 6; Group B includes instance sets a, b, c, and d; and, finally, Group C includes instance sets nre, nrf, nrg, and nrh. Table 3 shows the candidate values for each parameter based on previous works [43] and the configurations obtained for each group and ACO approach. Note that d-ACO denotes ACO with the traditional heuristic information expression and n-ACO denotes ACO with the alternative heuristic information expression.Table 3
F-Race settings and configurations obtained for each ACO approach.
ParameterCandidate valuesd-ACOn-ACOABCABCα0.25, 0.50, 1.00, 2.00, 5.00, 8.001.001.001.001.001.001.00β1.00, 2.00, 5.00, 8.00, 10.00, 13.008.008.005.008.008.008.00ρ0.80, 0.85, 0.90, 0.95, 0.98, 0.99, 0.995, 0.9990.950.900.900.980.990.90q00.10, 0.25, 0.50, 0.75, 0.90, 0.95, 0.990.500.750.500.900.900.25ϵ0.0001, 0.0005, 0.001, 0.002, 0.005, 0.0100.0010.0050.0050.0050.0050.001psaco5, 10, 20, 50, 100, 150, 200, 250201010015015050Once both ACO approaches are configured, 30 independent runs are performed for each instance and algorithm. Next, we analyse if there are significant differences between the behaviour of the two algorithms regarding solution quality and execution time for each instance. To this end, the authors consider the Wilcoxon–Mann–Whitney test [68] to validate several hypotheses. The implementation of this test is the one provided in the assessment performance tool described in Knowles et al. [69] and available in Fonseca et al. [70].However, indirectly the RPD metrics used for the assessment evaluation consider the optimal solution for the instances, which can be considered as the solutions provided by the corresponding exact techniques. Thus, the RPD metric evaluates how far the solution found by the metaheuristic is from the optimal solution provided by an exact technique.As a solution quality metric, we consider the relative percentage deviation (RPD), which evaluates how far the solution found by the metaheuristic is from the optimal solution known in the literature. The lower the RPD value, the better the solution obtained. Thus, indirectly, this metric evaluates the performance of the technique in comparison with the corresponding generic exact technique solving the same problem instance. Three RPD metrics are included: the average RPD,rpd¯∈0,1; the minimum RPD, rpdmin∈0,1; and the maximum RPD, rpdmax∈0,1. They are calculated as(25)rpd¯=z¯−zoptzopt,(26)rpdmin=zmin−zoptzopt,(27)rpdmax=zmax−zoptzopt,where z¯, zmin, and zmax denote the average solution cost, the minimum solution cost, the maximum solution cost from a distribution of 30 samples solving a instance, respectively, and zopt is the optimum solution cost of the instance. Note that the cost of the best solution found during one run is given by equation (4). Thus, although both SCP fitness formulations are different, we can compare the results obtained without loss of generality.Regarding the computing platform considered to perform the experimentation, the authors used two computing nodes in a computing cluster. Each node has two 2.33 GHz Intel Xeon E5410 with four cores each and a 1600 MHz DDR3 16 GB RAM, running a Linux operating system. All executions were performed in a single core without parallelism because the goal of this paper is not to explore parallelism. The reason for considering such unconventional infrastructure is the possibility of performing many independent executions because of the needs for the statistical test required to validate the proposal. That means that for a single execution or a reduced set of them, a conventional computer could be considered. To avoid the operating system tasks affecting the total computing time obtained during the experimentation, one core in each computing node was idle. Additionally, the authors also checked that the RAM in the computing node was enough to not apply memory swap. As expected, the computing power capacity of the processor definitively affects the time required to find the solution to the problem, most of the operations being related to CPU computing and accessing the principal memory (RAM). Note the same computing nodes are considered for all the experiments in this work to not bias the conclusions reached regarding computing time.Regarding programming languages, ACO algorithm was fully implemented in Java for Java Development Kit (JDK) 1.7. ABC algorithm was fully implemented in C. The scripts for managing the executions and collecting the results were implemented in bash. Note that the usage of two different programming languages for implementing ABC and ACO does not affect the conclusions reached in computing time. This fact is because ABC and ACO computing times are not compared in this work.


## 6.2. Analysis of the Experimental Results

Tables4 and 5 show for each instance and case study, the RPD metrics (rpd, rpdmin, rpdmax), average execution time reaching the stop condition (times), and average fitness evaluations needed for reaching the best solution found during the exploration (evals). In both tables, lower rpd¯ and times values are given in bold for each instance. In Table 5, d-ABC denotes ABC with the default heuristic feasibility operator and n-ABC denotes ABC with the heuristic feasibility operator based on the alternative SCP formulation.Table 4
RPD metrics, the average total execution time, and average number of evaluations obtained during the first study for ACO algorithm.
Instancezoptd-ACOn-ACOevals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)evals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)4_142918808450.230.230.2313501090.000.000.004_251239509000.200.000.5927002240.000.000.004_351616009160.970.191.1642007040.190.000.784_449448508800.400.200.8121008290.200.200.204_551219506800.100.000.396003400.000.000.394_656037805740.000.000.3626252400.000.000.004_743014308580.700.001.1614251180.000.000.004_849224404150.000.000.201350970.000.000.004_964151209321.250.312.3455508480.310.000.784_1051413901150.000.000.00750600.000.000.005_125348608910.400.001.5830005260.000.001.195_230249709451.490.662.3227008701.320.331.995_322620807530.220.001.3317251250.000.000.005_424227802450.000.000.0015001100.000.000.005_521111608570.470.470.477502230.000.000.475_6213640590.000.000.00300250.000.000.005_729354909010.510.341.0215758370.340.340.345_828838206530.350.000.6916501220.000.000.005_9279208230.000.000.36975780.000.000.005_1026523706170.380.000.7513501120.000.000.006_113830508021.450.001.4521753320.000.001.456_214611801220.000.000.0020251640.000.000.006_314515301280.000.000.00900700.000.000.006_4131930700.000.000.00300220.000.000.006_516111308311.240.002.4820253780.000.001.86a_125327259040.790.790.7948759760.400.400.40a_225247009081.191.191.1930009670.400.000.79a_323229259030.430.430.4357009710.430.430.43a_423415758950.430.430.4331504440.000.000.43a_523618159020.420.420.4236754780.000.000.85b_169360450.000.000.00450450.000.000.00b_276370370.000.000.00900930.000.000.00b_380320340.000.000.00300330.000.000.00b_479380380.000.000.00450440.000.000.00b_5721010.000.000.00150160.000.000.00c_122726909731.320.881.76622510340.880.880.88c_221927809790.910.910.91397510560.910.910.91c_324333059931.650.822.47577510670.820.411.23c_421924002350.000.000.0039003800.000.000.00c_521513059790.470.000.93292510520.470.470.47d_16041511741.670.001.6720254730.000.000.00d_26616752360.000.000.0018003500.000.000.00d_37277511981.391.391.3997510191.390.001.39d_462235250.000.000.00150200.000.000.00d_561600630.000.000.00675750.000.000.00nre_129100290.000.000.0050180.000.000.00nre_23016509020.000.003.3314004230.000.000.00nre_3279002160.000.000.007001700.000.000.00nre_42812004520.000.003.5710002600.000.000.00nre_528200490.000.000.00100310.000.000.00nrf_1142001180.000.000.002001120.000.000.00nrf_215100640.000.000.0075400.000.000.00nrf_31410054647.140.007.145049667.140.007.14nrf_4145002710.000.000.002001220.000.000.00nrf_51310055117.697.697.6910056147.697.697.69nrg_1176575019050.280.002.27535012500.000.000.00nrg_2154480021661.951.951.95342521711.300.651.95nrg_3166435022533.613.014.82277522533.012.414.22nrg_4168525022072.681.193.57410022172.381.192.98nrg_5168645022580.600.600.60550018300.000.000.60nrh_163365054993.171.594.76352557683.173.173.17nrh_263330054373.173.173.17210057063.173.173.17nrh_359420055113.393.393.39275057763.393.393.39nrh_458360054343.451.723.45220056643.451.723.45nrh_555425023290.000.000.00297517080.000.000.00Table 5
RPD metrics, average total execution time, and average number of evaluations obtained during the second study for ABC algorithm.
Instancezoptd-ABCn-ABCevals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)evals¯times¯rpd¯ (%)rpdmin (%)rpdmax (%)4_1429125,8084850.820.230.93124,1224470.230.230.234_25129998930.000.000.008194760.000.000.004_3516560273900.000.000.1911,1911030.000.000.004_4494128,3995350.200.000.61126,2094880.200.200.204_551211,1611020.000.000.00118,9613540.390.000.394_6560127,9885370.360.000.5428,4282540.000.000.364_7430110,9222070.930.001.16110,2241940.700.470.704_8492126,1174910.200.200.2034,2922830.000.000.204_9641128,3225260.940.002.18128,2765230.470.000.784_1051418,1621640.000.000.0055,6703330.000.000.585_1253125,02017970.400.001.58123,79217060.400.000.405_2302127,19319561.991.662.98125,85918560.990.001.325_3226123,81217131.331.331.33123,62716960.880.880.885_424217,7516500.000.000.0067602390.000.000.005_521114,9455210.000.000.0079272770.000.000.005_621319,2996840.000.000.0055752000.000.000.005_7293126,40119240.340.341.0214,7535470.000.000.005_828817,1536520.000.000.0023,5348140.000.000.005_9279124,77017540.360.360.3689613160.000.000.005_1026586,53911490.190.001.1312,4314070.000.000.006_1138124,41711981.450.002.1791,2699160.360.001.456_214687842170.000.000.0063811560.000.000.006_314514,6993590.000.000.0047761150.000.000.006_413116,9284000.000.000.003961950.000.000.006_516113,7603380.000.000.0043771060.000.000.00a_1253123,57357290.400.400.79122,22253810.400.400.40a_2252126,01663091.390.792.38126,21263460.790.001.19a_3232126,10363341.290.861.72125,82661890.430.000.86a_4234125,90862870.430.430.43124,89760040.430.430.43a_5236124,78559480.420.420.4211,14413460.000.000.00b_169120,83213,0121.450.001.45397012280.000.000.00b_276696220540.000.000.00337210430.000.000.00b_380417012960.000.000.00357211060.000.000.00b_479616619320.000.000.00396512270.000.000.00b_57231729880.000.000.0027748570.000.000.00c_1227121,97812,5890.880.441.76116,55194310.880.880.88c_2219110,30913,8990.230.001.3721,66464920.000.000.00c_3243126,72815,2461.650.412.47126,01814,8810.820.002.06c_4219126,19614,9510.460.001.8328,35576580.000.000.00c_521519,07554340.000.000.0014,54640860.000.000.00d_160597044550.000.000.00757256030.000.000.00d_266121,27231,5551.521.521.5211,34383710.000.000.00d_372122,82934,0631.391.392.7818,80813,5100.000.000.00d_462121,97632,3831.611.611.61476835100.000.000.00d_561109,45714,0771.641.641.64509036900.000.000.00nre_12927,68468,0660.000.000.00347996340.000.000.00nre_230119,319111,2136.676.676.6718,66651,9820.000.003.33nre_327120,070115,0287.417.417.4119,33953,4700.000.000.00nre_428119,063109,81210.713.5714.2910,55930,0550.000.000.00nre_528118,585106,7813.573.577.14405311,2030.000.000.00nrf_114119,200230,41714.2914.2914.29235313,7410.000.000.00nrf_215119,831238,70513.3313.3313.33195011,3370.000.000.00nrf_314119,332236,61114.2914.2921.43392923,1230.000.000.00nrf_414119,910241,66614.2914.2914.29274616,0740.000.000.00nrf_513106,58079,14115.3815.3823.08120,731248,0337.697.697.69nrg_1176128,776257,6642.842.273.41126,471235,6361.140.571.70nrg_2154128,678253,5643.252.603.90126,160233,1681.951.302.60nrg_3166134,516243,5673.613.014.22124,477217,7812.411.813.01nrg_4168135,789223,4563.572.984.17125,268224,7571.791.192.38nrg_5168126,782227,3464.173.574.76126,077232,0472.382.382.98nrh_163126,421228,3263.173.174.76145,678253,4671.591.593.17nrh_263134,282217,4563.174.764.76155,671243,4571.591.593.17nrh_359123,481237,2223.395.085.08132,451233,2451.691.693.39nrh_458143,562242,4563.453.455.17142,457231,0021.721.723.45nrh_555134,612232,2163.643.643.64143,417224,4521.821.823.64Analysing both tables regarding RPD metrics, we check that (i) n-ACO seems to outperform or match d-ACO in most instances and (ii) n-ABC seems to outperform or match d-ABC in most instances. Focusing on computing times, we reach a similar behaviour, where n-ACO appears to need a shorter time than d-ACO, except for b, c, and nrh instances, and n-ABC appears to need a shorter time than d-ABC in general. Focusing on evaluations, theevals¯ field is related to the number of iterations reached as follows. In ACO, psaco evaluations are performed for each iteration. In ABC, a number of evaluations varying between psabc and two times psabc are performed for each iteration. Thus, for ABC, the maximum number of evaluations will be a value in the range 100,000,200,000. For ACO, the maximum number of evaluations will be 10,000 as defined before. Analysing the evals¯ field, the authors reach that the number of evaluations needed is distant from the stop condition defined, and then the stop condition is adequate in both studies.Table6 shows the average RPD metrics for each instance group, where “ipv” field denotes the percentage of improvement by considering the alternative approach of the algorithm instead of the default version. Analysing this table, it is observed that (i) n-ACO provides better RPD values than d-ACO for all the groups and (ii) n-ABC also provides better RPD values than its default version. The RPD metrics obtained are in line with other works from the literature, with RPD values lower than 1.0%. In this regard, Table 7 shows the values of some recent successful approaches solving the problem. However, we should remark that the purpose of this work is not to outperform other techniques solving the standard SCP benchmark.Table 6
RPD metrics for each instance group and algorithm in both studies.
Instance grouprpd¯rpdminrpdmaxd-ACO (%)n-ACO (%)ipvd-ACO (%)n-ACO (%)ipvd-ACO (%)n-ACO (%)ipvFirst studyA0.430.0881.800.080.0363.830.790.4346.03B0.530.2846.600.360.1751.890.620.3937.24C1.861.746.541.221.173.742.491.8924.06ALL0.940.7025.690.550.4617.201.300.9030.60Second studyInstance grouprpd¯rpdminrpdmaxd-ABC (%)n-ABC (%)ipvd-ABC (%)n-ABC (%)ipvd-ABC (%)n-ABC (%)ipv (%)A0.380.1951.250.160.0756.650.660.3054.25B0.740.1974.560.500.0982.811.110.2973.77C10.711.0790.019.910.9090.9512.751.4888.39ALL3.940.4887.803.520.3590.044.840.6985.73Table 7
Review of recent approaches solving Beasley’s OR library.
Author/sSIArpd¯ (%)rpdmin (%)rpdmax (%)Farahani et al. [41]ABC0.160.01—Ren et al. [43]ACO0.200.030.39Lu and Vasko [48]TLBO20—0.06—Lu and Vasko [48]TLBO10—0.09—Naji-Azimi et al. [49]EM-like—0.20—Lu and Vasko [48]TLBO—0.28—At this point, it seems that the alternative approach of the algorithms provides better performance in both cases. However, we do not know if the differences observed are significant. To this end, the statistical methodology procedure described by Lanza-Gutierrez et al. [56] was applied. First, we removed all possible outliers. Then, we analysed the normality of data, obtaining that we cannot assume normal distribution in any case. Consequently, the median should be considered as average value for calculating z¯ in equation (25).Next, we study if there are significant differences in the solution quality of the algorithms. Starting with the first study, we consider the Wilcoxon–Mann–Whitney test with hypothesesH0: rpd¯a≥rpd¯b and H1: rpd¯a<rpd¯b, ∀a,b∈d­ACO,n­ACO with a≠b, where rpd¯a and rpd¯b are the average RPD of the algorithm a and b for a given instance, respectively. The p values obtained for each instance and ACO approach are shown in Table 8 under the title RPD analysis, where p values lower than the significance level α=0.05 are given in bold, i.e., the confidence level is 0.95. Note that the unilateral test performed between the two possibilities was the one that matches with the descriptive analysis, the other test being marked with a dash in the table. Also note that in case of equality between the average RPD values, the two unilateral tests are performed. For the second study, we consider the Wilcoxon–Mann–Whitney test with similar hypotheses as before H0: rpd¯c≥rpd¯d and H1: rpd¯c<rpd¯d, ∀c,d∈d­ABC,n­ABC with c≠d. The p values obtained are also shown in Table 9 with the same notation as in Table 8.Table 8
p values obtained analysing the differences observed regarding execution time and solution quality during the first study for the ACO algorithm.
RPD analysis (H1)Execution time analysis (H1)d-ACO< n-ACOn-ACO< d-ACOd-ACO< n-ACOn-ACO< d-ACOInst4_1—≤0.001—≤0.0014_2—≤0.001—≤0.0014_3—≤0.001—≤0.0014_4—≤0.001—≤0.0014_5—0.003—0.0064_6—≤0.001—≤0.0014_7—≤0.001—≤0.0014_8—≤0.001—≤0.0014_9—≤0.001—≤0.0014_100.5000.500—≤0.0015_1—0.004—≤0.0015_2—0.131—≤0.0015_3—≤0.001—≤0.0015_40.5000.500—≤0.0015_5—≤0.001—≤0.0015_60.5000.500—≤0.0015_7—≤0.001—≤0.0015_8—≤0.001—≤0.0015_9—0.060—≤0.0015_10—≤0.001—≤0.0016_1—0.002—0.1506_20.5000.5000.117—6_30.5000.500—≤0.0016_40.5000.500—≤0.0016_5—0.005—0.054a_1—≤0.001≤0.001—a_2—≤0.0010.006—a_30.5000.500≤0.001—a_4—≤0.001—0.001a_5—≤0.001—≤0.001b_10.5000.5000.291—b_20.5000.500≤0.001—b_30.5000.500—0.565b_40.5000.5000.106—b_50.5000.500≤0.001—c_1—≤0.001≤0.001—c_20.5000.500≤0.001—c_3—≤0.001≤0.001—c_40.5000.5000.013—c_5—0.002≤0.001—d_1—≤0.001—0.002d_20.5000.5000.124—d_3—≤0.001—0.003d_40.5000.500—0.017d_50.5000.5000.059—nre_10.5000.500—≤0.001nre_2—≤0.001—≤0.001nre_30.5000.500—0.112nre_4—0.002—0.006nre_50.5000.500—≤0.001nrf_10.5000.500—0.108nrf_20.5000.500—≤0.001nrf_30.5000.500—0.292nrf_40.5000.500—≤0.001nrf_50.5000.500≤0.001—nrg_1—≤0.001—≤0.001nrg_2—≤0.0010.261—nrg_3—≤0.0010.378—nrg_4—0.0380.574—nrg_5—≤0.001—≤0.001nrh_1—0.001≤0.001—nrh_20.5000.500≤0.001—nrh_30.5000.500≤0.001—nrh_4—0.261≤0.001—nrh_50.5000.500—0.003Table 9
p values obtained analysing the differences observed regarding execution time and solution quality during the second study for the ABC algorithm.
InstRPD analysis (H1)Execution time analysis (H1)d-ABC< n-ABCn-ABC< d-ABCd-ABC< n-ABCn-ABC< d-ABC4_1—≤0.001—≤0.0014_20.5000.500—≤0.0014_3—≤0.001—≤0.0014_40.037——0.0544_5≤0.001—≤0.001—4_6—≤0.001—≤0.0014_7—≤0.001—≤0.0014_8—≤0.001—≤0.0014_9—≤0.001—0.4594_10≤0.001—≤0.001—5_1—≤0.001—0.0015_2—≤0.001—≤0.0015_3—≤0.0010.415—5_40.5000.500—≤0.0015_50.5000.500—≤0.0015_60.5000.500—≤0.0015_7—≤0.001—≤0.0015_80.5000.5000.348—5_9—≤0.001—≤0.0015_10—≤0.001—≤0.0016_1—0.001—≤0.0016_20.5000.500—≤0.0016_30.5000.500—≤0.0016_40.5000.500—≤0.0016_50.5000.500—≤0.001a_1—0.001—≤0.001a_2—≤0.0010.479—a_3—≤0.001—0.135a_40.5000.500—0.025a_5—≤0.001—≤0.001b_1—≤0.001—≤0.001b_20.5000.500—≤0.001b_30.5000.500—0.012b_40.5000.500—≤0.001b_50.5000.500—≤0.001c_1—0.001—≤0.001c_2—≤0.001—≤0.001c_3—≤0.001—0.022c_4—≤0.001—≤0.001c_50.5000.500—0.001d_10.5000.5000.097—d_2—≤0.001—≤0.001d_3—≤0.001—≤0.001d_4—≤0.001—≤0.001d_5—≤0.001—≤0.001nre_10.5000.500—≤0.001nre_2—≤0.001—0.003nre_3—≤0.001—≤0.001nre_4—≤0.001—≤0.001nre_5—≤0.001x0.001—nrf_1—≤0.001—≤0.001nrf_2—≤0.001—≤0.001nrf_3—≤0.001—≤0.001nrf_4—≤0.001—≤0.001nrf_5—≤0.001≤0.001—nrg_1—≤0.0010.5000.500nrg_2—≤0.0010.5000.500nrg_3—≤0.0010.5000.500nrg_4—≤0.0010.5000.500nrg_5—≤0.0010.5000.500nrh_1—≤0.0010.5000.500nrh_2—≤0.0010.5000.500nrh_3—≤0.0010.5000.500nrh_4—≤0.0010.5000.500nrh_5—≤0.0010.5000.500Through the Wilcoxon–Mann–Whitney test, the differences observed regarding execution time for both algorithms are also analysed. For the first study, we define the hypothesesH0: times¯a≥times¯b and H1: times¯a<times¯b, ∀a,b∈d­ACO,n­ACO with a≠b, where times¯a and times¯b are the average execution time of the algorithm a and b for a given instance, respectively. The p values obtained for each instance and algorithm are shown in Table 8 under the title Execution time analysis, where p values are given in bold with the same criterion as before. For the second study, we consider the Wilcoxon–Mann–Whitney test with similar hypotheses as before H0: times¯c≥times¯d and H1: times¯c<times¯d, ∀c,d∈d­ABC,n­ABC with c≠d. The p values obtained are also shown in Table 9.Based on the previous statistical analysis, Table10 shows the percentage of cases where an algorithm provides the best significant performance compared to another for each study in terms of RPD and execution time. Focusing on the first study and RPD values, we verify that n-ACO provides better behaviour than d-ACO in 52.31% of cases. However, it is important to remark that d-ACO never provides better results than n-ACO, meaning that n-ACO clearly outperforms d-ACO. For execution time, n-ACO needs lower execution times than d-ACO in 55.38% of cases and d-ACO needs lower execution times than n-ACO in 23.08% of cases. This fact could mean that the alternative heuristic information needs higher execution times under certain conditions. However, most cases in which d-ACO needs lower execution times correspond with instances whose optimal solution is not reached, and then the 10,000 evaluations are performed for each algorithm, e.g., for instances a_1, a_2, a_3, c_1, c_2, c_3, c_5, nrh_1, nrh_2, nrh_3, and nrh_4. In such unfavourable cases, the differences observed are not of concern as shown in Figure 2(a). On the other hand, most cases in which n-ACO needs lower execution times correspond with instances whose optimal solution is reached. In such cases, a greater difference is observed favoring n-ACO. This fact is because n-ACO reaches the stop condition before d-ACO, e.g., for instance sets 4, 5, 6, d, nre, and nrg. Focusing on the second study, we verify that n-ABC provides better behaviour than d-ABC in 63.64% of cases, where d-ABC outperforms n-ABC in 7.27% of cases. This unfavourable situation occurs in small instances, where the search space is reduced. For execution time, n-ABC needs lower execution times than d-ABC in 69.23% of cases and d-ABC needs lower execution times than n-ABC in 4.62% of cases. As before, this unfavourable situation mainly occurs when n-ABC does not reach the optimal solution, penalizing the additional computation of the gain concept in the alternative SCP formulation. This behaviour is shown in Figure 2(b).Table 10
Percentage of cases where an algorithm provides the best significant performance compared to the other regarding solution quality and execution time.
RPD analysisExecution time analysisA (%)B (%)C (%)ALL (%)A (%)B (%)C (%)ALL (%)First studyn-ACO > d-ACO26.1513.8512.3152.31n-ACO > d-ACO33.857.6913.8555.38d-ACO > n-ACO0.000.000.000.00d-ACO > n-ACO0.0015.387.6923.08n-ACO = d-ACO12.3116.9218.4647.69n-ACO = d-ACO4.627.699.2321.54Percentage38.4630.7730.77100.00Percentage38.4630.7730.77100.00Second studyn-ABC > d-ABC23.6423.6416.3663.64n-ABC > d-ABC29.2326.1513.8569.23d-ABC > n-ABC5.450.001.827.27d-ABC > n-ABC3.080.001.544.62n-ABC = d-ABC16.3612.730.0029.09n-ABC = d-ABC6.154.6215.3826.15Percentage45.4536.3618.18100.00Percentage38.4630.7730.77100.00Figure 2
Analysis for the average execution times in each study. (a) Average execution time for each ACO approach and instance set. (b) Average execution time for each ABC approach and instance set.
(a)(b)The previous analysis is completed with the landscape study in Tables11 and 12 for the solutions obtained solving the instances through ACO and ABC, respectively. The metrics in such tables quantify solution quality (QMetric ∈0,1), the rate of success (SRate ∈0,1), and speed of reaching a solution (SSpeed ∈0,1). QMetric follows an exponential formulation which allows distinguishing between the performance of two algorithms, which obtained solutions close to the optimum fitness. SRate is defined as the number of successful runs that the algorithm reaches the optimum fitness divided by the total number of runs. SSpeed quantifies the number of evaluations taken to reach the optimum fitness. For the three metrics, the value 1 indicates the highest quality. More details about the three metrics, as well as formulation, are listed in [71]. Analysing Tables 11 and 12, we check that, in general, both n-ACO and n-ABC provide a higher or equal QMetric than d-ACO and d-ABC approaches. For SSpeed, we check that both d-ACO and d-ABC need a lower or equal number of evaluations than n-ACO and d-ABC to reach the optimum fitness. For SRate, we check that both d-ACO and d-ABC reach the optimum fitness a greater or equal number of times than n-ACO and d-ABC. That means that n-ACO and n-ABC obtained better quality solutions, are better in convergence, and provide a more robust performance than the default approaches.Table 11
Landscape metrics for each instance and ACO approach.
Instd-ACOn-ACOQMetricSSpeedSRateQMetricSSpeedSRate4_10.00080.51070.10001.00000.83660.96674_20.17770.42480.16671.00000.71901.00004_30.00190.00000.00000.44670.51190.43334_40.00270.00000.00000.01140.63000.10004_50.50290.61510.50000.56950.79790.56674_60.64730.54450.63331.00000.69310.86674_70.06690.83100.06671.00000.83820.93334_80.67510.61440.66671.00000.84251.00004_90.00050.00000.00000.10450.44000.10004_101.00000.84971.00001.00000.90801.00005_10.33360.46220.33330.63350.59030.63335_20.00000.00000.00000.00070.00000.00005_30.43340.59650.43331.00000.80980.93335_41.00000.69871.00001.00000.86501.00005_50.00000.86400.03330.63330.80660.63335_61.00000.91831.00001.00000.96151.00005_70.00090.00000.00000.00170.78000.20005_80.53400.54480.53331.00000.82151.00005_90.40170.55280.40001.00000.87751.00005_100.46690.64160.46671.00000.82160.96676_10.23590.48030.23330.56960.71150.56676_21.00000.82680.86671.00000.74770.93336_31.00000.79020.96671.00000.91301.00006_41.00000.87911.00001.00000.96451.00006_50.23550.78400.23330.53500.75160.5333a_10.00370.00000.00000.05170.00000.0000a_20.00010.00000.00000.22020.70750.2000a_30.03370.00000.00000.03370.00000.0000a_40.03060.06100.03330.67690.54400.6667a_50.03500.59550.06670.67720.61530.6667b_11.00000.91801.00001.00000.95101.0000b_21.00000.95841.00001.00000.88101.0000b_31.00000.95311.00001.00000.95951.0000b_41.00000.94871.00001.00000.94251.0000b_51.00000.99901.00001.00000.98501.0000c_10.00210.00000.00000.00860.97000.0333c_20.01200.00000.00000.01200.00000.0000c_30.00550.00000.00000.07850.00000.0000c_41.00000.69530.96671.00000.62301.0000c_50.09250.68100.03330.09180.89500.0333d_10.50690.53340.30001.00000.66350.7667d_21.00000.68610.93331.00000.72750.8000d_30.32800.80200.10000.59680.67750.4000d_41.00000.97681.00001.00000.98501.0000d_51.00000.92881.00001.00000.91151.0000nre_11.00000.99001.00001.00000.99501.0000nre_20.93190.72680.63331.00000.79060.8333nre_31.00000.86290.93331.00000.89471.0000nre_40.94990.83360.73331.00000.80860.9667nre_51.00000.98001.00001.00000.98771.0000nrf_11.00000.97171.00001.00000.97821.0000nrf_21.00000.98471.00001.00000.98981.0000nrf_30.96210.87700.33330.96210.76200.3333nrf_41.00000.94070.96671.00000.96831.0000nrf_50.94410.69800.16670.94410.86500.0667nrg_10.75280.36130.50001.00000.47600.8667nrg_20.24630.00000.00000.35550.00000.0000nrg_30.08080.00000.00000.11230.00000.0000nrg_40.17620.00000.00000.20260.00000.0000nrg_50.63740.23500.20000.85500.32030.6000nrh_10.78800.00000.00000.81350.00000.0000nrh_20.81360.00000.00000.83980.00000.0000nrh_30.81480.00000.00000.81480.27000.0333nrh_40.83920.00000.00000.84840.59000.0333nrh_51.00000.54070.96671.00000.66701.0000Table 12
Landscape metrics for each instance and ABC approach.
Instd-ABCn-ABCQMetricSSpeedSRateQMetricSSpeedSRate4_10.00010.00000.00000.00080.78730.13334_21.00000.94861.00001.00000.95981.00004_30.57910.83660.56671.00000.94541.00004_40.30680.82380.30000.01140.84410.13334_51.00000.94821.00000.43370.86420.43334_60.08460.89850.06670.74320.86560.73334_70.03330.91870.03330.00000.00000.00004_80.02540.00000.00000.70760.86620.70004_90.03350.82150.03330.06710.88490.06674_101.00000.90501.00000.53850.85140.53335_10.03490.80710.03330.33380.89120.33335_20.00000.00000.00000.10130.81830.10005_30.00000.00000.00000.00000.90690.10005_41.00000.88480.90001.00000.96741.00005_51.00000.91341.00001.00000.95751.00005_61.00000.91081.00001.00000.97271.00005_70.00110.00000.00001.00000.90680.96675_81.00000.89520.93331.00000.86980.86675_90.00290.00000.00001.00000.95171.00005_100.50020.88880.50001.00000.92960.83336_10.23350.92740.23330.50080.86860.50006_21.00000.95091.00001.00000.96811.00006_31.00000.92390.90001.00000.97641.00006_41.00000.91931.00001.00000.98071.00006_51.00000.92061.00001.00000.97781.0000a_10.03730.00000.00000.05170.00000.0000a_20.00060.00000.00000.21090.84960.2000a_30.00060.00000.00000.14760.80560.1333a_40.03060.85440.23330.03060.85770.1667a_50.03500.00000.00001.00000.92981.0000b_10.54150.87580.46671.00000.97921.0000b_21.00000.96461.00001.00000.98291.0000b_31.00000.97911.00001.00000.98241.0000b_41.00000.96821.00001.00000.97961.0000b_51.00000.98431.00001.00000.98711.0000c_10.00750.00000.00000.00860.79750.0333c_20.52500.77520.50001.00000.88520.9000c_30.00940.00000.00000.10690.59730.0667c_40.13010.75860.06671.00000.86010.7667c_51.00000.90491.00001.00000.92391.0000d_11.00000.96531.00001.00000.95781.0000d_20.32850.00000.00001.00000.93891.0000d_30.26650.00000.00001.00000.90940.8333d_40.28200.57370.06671.00000.97161.0000d_50.29630.91760.03331.00000.97361.0000nre_11.00000.88740.80001.00000.98181.0000nre_20.66840.00000.00000.93810.89120.6667nre_30.67120.00000.00001.00000.87030.8000nre_40.55550.00000.00001.00000.92280.9667nre_50.00000.00000.00001.00000.97961.0000nrf_10.88800.00000.00001.00000.98751.0000nrf_20.76320.00000.00001.00000.99001.0000nrf_30.65780.00000.00001.00000.97991.0000nrf_40.73540.00000.00001.00000.98521.0000nrf_50.76240.00000.00000.94410.97020.0333nrg_10.21340.00000.00000.40130.00000.0000nrg_20.21000.00000.00000.22950.00000.0000nrg_30.13450.00000.00000.21220.00000.0000nrg_40.12340.00000.00000.25290.00000.0000nrg_50.12450.00000.00000.23430.00000.0000nrh_10.18760.00000.00000.23420.00000.0000nrh_20.19840.00000.00000.23110.00000.0000nrh_30.19760.00000.00000.25420.00000.0000nrh_40.17640.00000.00000.21030.00000.0000nrh_50.16480.00000.00000.22310.00000.0000Up to this point, we know that the concepts included in the alternative formulation positively affect the search process in the first study, where the concepts from the alternative formulation are considered for guiding purposes. A mapping of the solutions visited by n-ACO and d-ACO could help to effectively show how the two approaches explore the search space. To this end, we consider the mapping method (MaM) proposed by Autuori et al. [72], where a mapping function converts a multidimensional space solution in one dimensional space through two steps: (i) a binary conversion is applied to the solution (for SCP, the binary encoding is straightforward, where a column takes the value 1 if it is considered in the solution and 0 otherwise) and (ii) the binary Hamming distance is calculated between such binary solution and a reference solution randomly generated, resulting in a new representation of the solution. This representation is used for identifying the different zones explored by the algorithms. Note that the number of zones corresponds with the number of elements in the binary encoding (the number of columns). To this end, all the binary representations are added, resulting in a frequency diagram, showing how usually the algorithm includes a column in a solution.Table13 shows three metrics analysing the frequency diagrams previously generated for each ACO approach and an instance from each group 4, 5, 6, a, b, c, d, nre, nrf, nrg, and nrh. Note that the frequency diagrams were generated using all the solutions built in the 30 runs for each algorithm. The metrics used were also proposed by Autuori et al. [72] and are (i) the number of unexplored zones (“uz”), the number of explored zones (“ez”), and the number of large explored zones (“lez”). The metrics are related as follows. Convergence is considered high if lez is few in number. Diversity is considered good if the number of ez is large. Analysing Table 13, we check that ez is usually higher for n-ACO than for d-ACO, meaning that d-ACO improves diversity during the search compared to the traditional approach. This fact is especially relevant for large instances, as occurs for nrg_1 and nrh_1, where ez metric is significantly large. Focusing on lez, we check that the differences observed between both approaches are not as pronounced as for ez. However, such differences could mean that d-ACO has a lack of convergence during the search, and then future authors should manage this fact.Table 13
Mapping analysis of the two ACO approaches, when solving a instance from each group.
Instn-ACOd-ACOuzezlezuzezlez4_1511224150123435_1521715849174646_158174465118150a_11092975911329371b_13292357635121360c_11294179915039697d_15692998158628260nre_12286164912197253106nrf_1465814581454326098nrg_114339151727281620200nrh_1440860214038261184163From these two studies solving the traditional SCP, we verify that (i) the concepts from the alternative formulation are useful in guiding the search process of a metaheuristic and (ii) the concepts from the alternative formulation are useful in updating a usual heuristic feasibility operator from the literature. The improvement in both studies was observed in terms of the solution quality, the rate of success, and the speed of reaching a solution. The conclusion in (ii) is especially interesting because this type of operators is generically applied in metaheuristics (generating unfeasible solutions), and the proposal could be directly incorporated into many solving methods.


## 7. Conclusions and Future Scope

Traditionally, SCP is formulated without addressing two issues: solution unsatisfiability and set redundancy, meaning that the solving method has to implement mechanisms to control such aspects. In recent years, an alternative SCP formulation was proposed, whose main contribution was that both issues were directly addressed by including penalties in the fitness function.Reviewing the current scientific literature, we check that the alternative SCP formulation has received limited attention. Hence, we question whether there is any advantage of using this formulation beyond addressing set redundancy and feasibility aspects. This idea led us to propose two studies based on a metaheuristic approach. The aim is to identify if there is any concept in the alternative formulation, which could be considered for enhancing a solving method using the traditional formulation. The first study considers an ACO algorithm in two contexts: (i) solving the problem by addressing the traditional SCP formulation and (ii) solving SCP addressing the traditional formulation but using concepts from the alternative one for guiding the search. The second study considers an ABC algorithm in two contexts: (i) solving SCP addressing the traditional formulation and (ii) solving SCP addressing the traditional formulation but including concepts from the alternative one for updating a usual heuristic feasibility operator from the literature.As a result of the first study, the authors conclude that it is possible to consider the gain concept from the alternative SCP formulation to successfully guide ACO search addressing the traditional SCP formulation. The benefits of the novel guide are shown in terms of solution quality, convergence, execution time, and diversity. From the second study, the authors conclude that it is possible to consider the gain concept from the alternative SCP formulation to update a feasibility operator from the literature. The benefits of the novel feasibility operator are shown in terms of solution quality, execution time, and convergence.The first conclusion is interesting for designing novel guide strategies for solving the traditional SCP formulation. The second conclusion is especially interesting because feasibility operators are widely considered in metaheuristic approaches solving the SCP because of the usual generation of unfeasible solutions. This type of operators is integrated into the solving method as black-box methods. That means that it is straightforward to interchange one method for another. This situation implies that the feasibility operator based on the alternative SCP formulation presented here could be integrated with a reduced effort in already published works from the literature, as well as in future works to evaluate each specific use case.As future lines of research, it would be interesting to consider additional metaheuristics to this study, as well as a larger dataset with bigger problems. Additionally, it could be interesting to extend this work by taking into account the performance of the solving methods and the search space complexity of the instances based on the landscape metrics.



---

*Source: 5473501-2020-07-15.xml*