An efficient ACO+RVND for solving the resource-constrained deliveryman problem
Research and Development on Information and Communication Technology
An Efficient ACO+RVND for Solving the
Resource-Constrained Deliveryman Problem
Ha-Bang Ban
School of Information and Communication Technology
Hanoi University of Science and Technology
Email: [email protected]; [email protected].vn
Communication: received 20 December 2019, revised 21 February 2020, accepted 17 April 2020
Digital Object Identifier: 10.32913/mic-ict-research.v2020.n1.911
Abstract: In this paper, Resource-Constrained Deliveryman
Problem (RCDMP) is introduced. The RCDMP problem deals
with finding a tour with minimum waiting time sum so that
푣 푗, there exists a cost 푐(푣푖, 푣 푗) and resource consumption
푟(푣푖, 푣 푗). Suppose that 푇 = (푣 , . . . , 푣푘, . . . , 푣푛) is a tour
1
in 퐾푛. Denote 푃(푣 , 푣푘) is the path from 푣 to 푣푘 on the
1
1
it consumes not more than 푅
units of resources, where
푚푎푥
tour 푇 and 푙(푃(푣 , 푣푘)) is its length. The waiting time of
1
푅
is some constant. Recently, an algorithm developed in a
푚푎푥
a vertex 푣푘 (1 < 푘 ≤ 푛) on 푇 is the length of the path from
trajectory-based metaheuristic has been proposed. Since the
search space of the problem is a combinatorial explosion,
the trajectory-based sequential can only explore a subset of
the search space, therefore, they easily fall into local optimal
in some cases. To overcome the drawback of the current
algorithms, we propose a population-based algorithm that
combines an Ant Colony Algorithm (ACO), and Random
Variable Neighborhood Descent (RVND). In the algorithm, the
ACO explores the promising solution areas while the RVND
exploits them with the hope of improving a solution. Extensive
numerical experiments and comparisons with the state-of-the-
art metaheuristic algorithms in the literature show that the
proposed algorithm reaches better solutions in many cases.
starting vertex 푣 to 푣푘:
1
푘−1
∑
푤(푣푘) =
푐(푣푖, 푣푖+1).
푖=1
The total waiting time of tour 푇 is defined as the sum of
waiting time of all vertices:
푛
∑
퐿(푇) =
푤(푣푘).
푘=2
The resource consumption of a tour is the sum of the
resource consumption of its edges. Tour 푇 must satisfy the
following resource constraint:
Keywords: RCDMP, ACO, GA, metaheuristic.
푛−1
∑
푟(푣푖, 푣푖+1) ≤ 푅푚푎푥
.
(1)
푖=1
I. INTRODUCTION
The RCDMP asks for a tour with minimum waiting time
sum so that it consumes not more than 푅푚푎푥 units of
resource.
The Resource-Constrained Deliveryman Problem
(RCDMP) has not been studied much in literature.
Informally, the RCDMP aims to find a tour with minimum
waiting time sum so that it consumes no more than
푅푚푎푥 units of resources, where 푅푚푎푥 is some constant.
The resource consumption of a tour is the sum of the
resource consumptions of its edges. In the special case,
since resource-constraint is ignored, the RCDMP becomes
the Deliveryman Problem (DMP) or Traveling Repairman
Problem (TRP). The problem has applications in reality,
e.g., disk head scheduling [1, 5, 6, 8, 17, 19].
The RCDMP is a NP-hard problem; thus, a metaheuristic
algorithm is a suitable approach for it in short computa-
tion time. Previously, the only algorithm was developed
in a trajectory-based metaheuristic approach to solve the
solution and, at each step of the search, the current solution
is replaced by another solution found in its neighborhood.
However, this algorithm may implement a strong intensi-
fication strategy. However, its diversification may not be
good enough. As a result, it gets stuck in local optima in
some cases. Another approach is population-based which
performs a search with multiple promising solutions, thus,
its exploring search space is extended. As a result, the
chance to obtain better solutions is higher.
The RCDMP is at least as hard as DMP, therefore it is a
NP-hard problem. The RCDMP is formulated as followings:
Given a complete graph 퐾푛 = (푉, 퐸) where 푉 = 1, 2, . . . 푛
is a set of vertices, and E is the set of edges. For each
edge (푣푖, 푣 푗) ∈ 퐸, which connects the two vertices 푣푖 and
32
Vol. 2020, No. 01, September
Algorithm 1 ACO-RVND
In this paper, we propose a population-based algorithm
Random Variable Neighborhood Descent (RVND) [16].
The two important features in our algorithm are that:
Input: 퐾푛, 푆푝, and 휏 are the graph, the cost matrix,
0
the size of ant population, and the initial amount of
pheromone deposited, respectively.
Output: The best solution 푇∗.
• Two kinds of ants coexist in the ACO. In a com-
the feeding behavior by using intelligent ants, which
can trail the pheromone exactly, and dull ants which
cannot trail the pheromone. From results, the ant group
that includes the dull ants can obtain more foods than
the group consisting of only the intelligent ants. The
dull ants are regarded as having a task that finds
the new food sources by dawdle. It means that the
coexistence of the intelligent and dull ant improves
the effectiveness of the feeding behavior.
while (The termination criterion of the ACO-RNVD is
not satisfied) do
{Step 1: The ACO step}
Initiate pheromone;
while (|푃| < 푆푝) do
{Choose the type of ant. If the value of rd is less
than 80, the ant depends on the intelligent type.
Otherwise, it fails into dull type}
푟푑 = random(100);
푇푘 = 푇푘 ∪ 푣 ;
1
푣 = 푣 ; {푣 is a next vertex}
1
• To be successful, a search algorithm needs to establish
a good ratio between exploration and exploitation.
In our algorithm, the ACO explores the promising
solution areas while the RVND exploits them with
the hope of improving a solution. Extensive numerical
experiments and comparisons with the state-of-the-art
metaheuristic algorithms on 320 instances show that
the proposed algorithm reaches better solutions in 303
cases.
while | 푇푘 |≤ 푛 do
푁푘 = {푣 푗 | 푣 푗 ∉ 푇푘 and 푣 푗 ∈ 퐾푛};
푣 = Pick-Forward-Vertex(푣, 푟푑, 푁푘);
푇푘 = 푇푘 ∪ 푣;
end while
Update phernomone 휏푖 푗 according to (4), (5);
푃 = 푃 ∪ 푇푘; {Add 푇푘 to the ant population P}
end while
{Step 2: The RVND step}
The rest of this paper is organized as follows. Section 2
presents the proposed algorithm. Computational evaluations
are reported in section 3. Sections 4, 5 discuss and conclude
the paper, respectively.
for 푇 ∈ 푃 do
푇0 = RVND(푇);
if (퐿(푇0 ) < 퐿(푇∗)) and (푇0 is feasible)) then
푇∗ = 푇0;
improved=True;
end if
II. THE PROPOSED ALGORITHM
end for
In this paper, we propose an algorithm which utilizes
“ants" coexist, and the ants drop pheromone on the path
connecting the locations. Pheromone trails are updated
depending on the behavior of the ants. The ants find a
food source through paths having strong pheromone. By
communicating with other ants according to the pheromone
strength, the algorithm tries to find the optimal solution.
systematic switches between different neighborhoods.
{Step 3: Update pheronome}
if (improved==True) then
Update pheronome information by (6), and (7);
end if
end while
return 푇∗;
1. Penalty on infeasible solution
Our search is not constrained to feasible solutions. Dur-
ing the search we penalize infeasible solutions by incorpo-
rating a penalty term. For each solution 푇, let 퐿(푇) denote
the total latency and let 푉(푇) denote the total violation of
the constraint. The total latency violation 푉(푇) is computed
on a tour basis with respect to the value 푅푚푎푥. Specifically,
it is equal to
A pseudocode of our algorithm is given in Algorithm 1.
Our algorithm is repeated a number of times, and the best
solution found is reported. In Step 1, the ACO is used to
generate an initial ant population that is an input for the
RVND in Step 2. In Step 2, to exploit promising solution
spaces, the RVND is implemented with the best solution
from the ACO. Our algorithm stops after 푚 iterations. If
the best solution has not been improved. In the remaining
of this section, more details about the three steps of our
algorithm are given in Algorithm 1.
max{퐿푅 − 푅푚푎푥, 0},
where LR is the resource consumption value in the current
solution (feasible or infeasible).
33
Research and Development on Information and Communication Technology
Algorithm 2 Pick-Forward-Vertex(푣푖, 푟푑, 푁푘)
2. Step 1: ACO
Input: 푣푖, 푟푑, 푁푘 are the current vertex, a random number,
and a set of unvisited vertices, respectively.
Output: A next vertex v.
Step 1 includes some small steps as follows:
- Encoding for ants: We simply use the natural encoding,
in which an ant individual is represented as a list of 푛
vertices (푣 , 푣 , ..., 푣푘, ..., 푣푛), where 푣푘 is the 푘−th vertex
푝푟표푆푢푚 = 0;
1
2
if (푟푑 ≤ 푎푛푡_푡푦푝푒) then
to be visited. Each individual represents one possible tour.
- Initializing parameters for the ACO: Let 휏푘−1푖 푗 be the
amount of pheromone on the edge (푣푖, 푣 푗) so that the 푘−th
ant uses to trail (푘 = 1, 2, ..., 푆푝). Initially, 휏 is set to 휏 ,
{The second only uses the amount of phernomone as
(2)}
for (푣 푗 ∈ 푁푘) do
0푖 푗
0
푝푟표푆푢푚
=
푝푟표푆푢푚 + 푝표푤(휏[푖, 푗], 훽휏) ×
respectively.
푝표푤(훽[푖, 푗], 훽휇);
- Selecting for the next vertex: Assume that, 푘−th ant
needs to be chosen to go from vertex 푣푖 to a next vertex
in an unvisited vertex set 푁푘. Our algorithm maintains two
types of ant:
The first uses the amount of phernomone thus, its proba-
bility equation is as follows:
end for
for (푣 푗 ∈ 푁푘) do
푝[푖, 푗] =
푝표푤 (휏[푖, 푗],훽휏)×푝표푤 (휂[푖, 푗],훽휇)
;
푝푟표푆푢푚
end for
푟푑 = random(푝푟표푆푢푚);
for (푣 푗 ∈ 푁푘 ) do
푤ℎ푒푒푙푆푢푚 = 푤ℎ푒푒푙푆푢푚 + 푝[푖, 푗];
if (푤ℎ푒푒푙푆푢푚 > 푟푑) then
break;
훽푟
훽휂
[휏푘−1푖 푗
푣푗 ∈푁푘
]
[휂푘−1푖 푗
]
푝2푘푖 푗
=
(2)
Í
훽휂
훽푟
[휏푘−1푖 푗
]
[휂푘−1푖 푗
]
The last does not use either the phernomone or genetic
information, therefore its probability equation is as follows:
end if
푣 = 푣 푗;
end for
end if
1
푝3푘푖 푗
=
(3)
|푁푘 |
where 훽푟 , 훽휂, and 훽푔 are parameters, 휂푘푖 푗
and |푁푘 | are the position of edge (푣푖, 푣 푗), and number of
vertices in the tour, respectively). The selection of 푣 푗 is
choosing a next vertex until all vertices are visited. The
detail in this step is given in Algorithm 2.
- Updating Pheromone of 푘−ant: After 푘−ant has com-
pleted the tour 푇푘, its deposited pheromone on 푇푘 is
updated. We should note that the dull ants can deposit
the pheromone although they cannot trail the pheromone.
The mount of pheromone which an ant deposits on 푇푘 is
calculated as follows:
{The third cannot trail the pheromone as (3)}
if (푟푑 > 푎푛푡_푡푦푝푒) then
Select randomly vertex 푣 ∈ 푁푘;
end if
1
=
(휌,
휌×푐푖 푗
Algorithm 3 RVND(T)
Input: 푇 is a tour.
Output: A new solution 푇.
Initialize the Neighborhood List NL;
while 푁퐿 ≠ 0 do
Choose a neighborhood 푁 in NL at random
푇0 ← arg min 푁(푇); {Neighborhood search}
if ((퐿(푇0 ) < 퐿(푇)) then
푇 ← 푇0
(
휎
,
if (푣푖, 푣 푗) ∈ 푇푘
otherwise
퐿(푇푘)
Δ휏푘푖 푗
=
Update NL;
else
0,
(4)
where 휎 is a parameter. Since the k-ant finishes its tours,
we update 휏푖 푗 of each edge (푣푖, 푣 푗) depending on Δ휏푘푖 푗 as
follows:
Remove N from the NL;
end if
end while
휏푘푖 푗 = (1 − 푝) × 휏푘−1푖 푗 + Δ휏푘푖 푗
(5)
where 푝 ∈ (0, 1) is the pheromone trail decay coefficient.
Solutions are then evaluated according to the weighted
fitness function 퐿0 = 퐿+푃퐹×푉(푇), where PF is the penalty
factor. If the obtained solution is feasible then LR ≤ 푅푚푎푥
and 퐿0 = 퐿.
3. Step 2: RVND
To be successful, a search algorithm needs to estab-
lish a good ratio between exploration and exploitation. In
the proposed algorithm, the ACO is also combined with
the RVND to keep a balance between exploration and
34
Vol. 2020, No. 01, September
exploitation. In this combination, the ACO explores the
promising solution spaces while the RVND bases on a
simple principle of systematically switches between differ-
ent neighborhoods to exploit these spaces. In the RVND
step, several neighborhoods are used such as remove-insert,
reinsertion, swap-adjacent, swap, 2-opt, and or-opt in [16].
In THE RCDMP, by using the known cost of the current
solution, this operation can be done in constant time [4].
Therefore, the running time of exploring the neighborhoods
can be sped up. Six neighborhoods used in the step are
described as followings: 1) Swap-adjacent: It swaps each
pair of adjacent vertices. The complexity of exploring the
neighborhood is 푂(푛); 2) Remove-insert moves each vertex
in the solution at the end of it. The complexity of exploring
the neighborhood is 푂(푛); 3) Reinsertion: One vertex is
relocated to another position of the tour. The complexity
of exploring the neighborhood is 푂(푛); 4) Swap: It tries
to swap the positions of each pair of vertices in the single
tour 푇. The complexity of exploring the neighborhood is
푂(푛2); 5) 2-opt: It removes each pair of edges from the
tour and reconnects them. The complexity of exploring
the neighborhood is 푂(푛2); 6) Or-opt: Three adjacent
vertices are reallocated to another position of the tour.
The complexity of exploring the neighborhood is 푂(푛2). A
pseudocode of the RVND algorithm is given in Algorithm
3.
are independent and uniformly chosen random integers
in the range [0, 200]. Resource matrix elements, 푟푖 푗,
are independent and uniformly chosen integers in the
range [0, 200 - 푐푖 푗]. The cost matrix 퐶 = [푐푖 푗] and 푅 =
[푟푖 푗] are generally symmetric and metric. Maximum
resource usage, 푅푚푎푥, is computed using the following
formula:
∑ ∑
∑ ∑
푅푚푎푥 = d훼 ×
푟푖 푗푥푖푐푗 + (1 − 훼) ×
푟푖 푗푥푖푟푗e
푖∈푉 푗 ∈푉
푖∈푉 푗 ∈푉
In the above formula, 푥푖푐푗 represent the optimal solution
of the unconstrained DMP with the cost matrix 푐푖 푗.
Similarly, 푥푖푟푗 represent the optimal solution of the
problem
푛−1
∑
푟(푣푖, 푣푖+1) → min,
푖=1
where the cost matrix is defined by the matrix 푟푖 푗. For
the problem, we choose the Concorde tool to solve
exactly the problem. In the equation, 훼 is a parameter,
that provides means for controlling tightness of the
resource constraint. When 훼 = 0, the resource con-
straint is very tight. On the other hand, when 훼 = 1,
the resource constraint has no effect on the optimal
solution. We choose 훼 = 0, 0.5, 0.75 and 1 and vary the
size of the instances between 30 to 100 vertices with
the different values of 훼 to create 320 instances. For
unconstrained DMP with a small number of instances
to solve. Currently, there is no exact algorithm in
the literature that can solve the problem with up to
100 vertices. Therefore, we use the metaheuristic in
[3] to obtain near-optimal solutions. All instances are
4. Step 3: Update pheromone
If the new best solution is found, we use it to update
pheromone value. The pheromone information Δ휏푖∗푗 be-
queathed to the ACO in the next iteration is calculated as
follows:
(
휎
퐿(푇∗)
if (푣푖, 푣 푗) ∈ 푇∗
otherwise;
,
available in the online supplement to this paper at .
Δ휏푖∗푗
=
are generated by Salehipour et al., where each of them
is composed of 20 instances with 10, 20, 50, 100,
and 200 customers, respectively. In total, there are 100
instances.
to 150 vertices are selected. The optimal solutions
instances.
0,
(6)
where 휎, 퐿(푇∗) are parameter, and the cost of 푇∗, respec-
tively. Therefore, the pheromone information on each edge
(푣푖, 푣 푗) is updated by Δ휏푖∗푗 as follows:
휏푖 푗 = 휏푖 푗 + Δ휏푖∗푗
(7)
III. COMPUTATIONAL RESULTS
The experiments are conducted on a personal computer,
which is equipped with an Intel Pentium core i7 duo 2.10
Ghz CPU and 8 GB bytes RAM memory.
The selection of pheromone-related parameters are
conducted in preliminary experiments. The parameter
푎푛푡_푡푦푝푒 is set to 80 because it has been reported that
about 20 percent of the dull ant and 80 percent of the
intelligent ant live in the real ant’s world in [10]. For the
1. Benchmark Instances
The numerical analysis was performed on a set of bench-
marks described in [4, 19, 23]. In our experiments, two
types of dataset are selected as followings:
1http://www.math.princeton.edu/tsp/concorde.html
2https://drive.google.com/drive/u/2/folders/1M_
35
Research and Development on Information and Communication Technology
7DEOHꢀꢁꢂꢀ7KHꢀH[SHULPHQWꢀUHVXOWVꢀIRUꢀWKHꢀ5&'03ꢃLQVWDQFHVꢀꢄn ꢀꢅꢆꢇꢀ
Įꢀ ꢀꢆꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.5ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.75ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢈꢀ
2XUꢀDOJRULWKPꢀ
76ꢀ
76ꢀ
76ꢀ
76ꢀ
,QVWDQFHVꢀ
Best.Sol
Best.Sol
Aver.Sol
gapꢁ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢁ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢁ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢁ
T
WHVWꢃꢈꢀ
WHVWꢃꢁꢀ
ꢉꢉꢊꢋꢀ
ꢍꢈꢅꢆꢀ
ꢉꢊꢋꢉꢀ
ꢉꢎꢉꢉꢀ
ꢉꢉꢈꢌꢀ
ꢉꢉꢊꢁꢀ
ꢍꢈꢎꢌꢀ
ꢊꢎꢎꢎꢀ
ꢉꢆꢉꢅꢀ
ꢉꢋꢍꢊꢀ
ꢍꢋꢁꢋꢀ
ꢉꢅꢍꢈꢀ
ꢉꢆꢁꢌꢀ
ꢉꢈꢉꢆꢀ
ꢉꢅꢎꢍꢀ
ꢉꢍꢍꢁꢀ
ꢉꢊꢌꢈꢀ
ꢉꢌꢋꢅꢀ
ꢍꢉꢁꢁꢀ
ꢉꢋꢍꢁꢀ
ꢀꢀ
ꢀꢁꢂꢃꢄ
ꢀꢊꢂꢅꢄ
ꢀꢇꢅꢁꢄ
ꢀꢈꢈꢊꢄ
ꢀꢉꢁꢅꢄ
ꢀꢂꢁꢂꢄ
ꢀꢊꢇꢅꢄ
ꢂꢂꢀꢃꢄ
ꢂꢊꢀꢁꢄ
ꢀꢇꢅꢆꢄ
ꢀꢃꢂꢁꢄ
ꢂꢆꢃꢀꢄ
ꢂꢀꢆꢉꢄ
ꢂꢀꢉꢈꢄ
ꢂꢊꢉꢇꢄ
ꢀꢂꢈꢁꢄ
ꢀꢂꢇꢃꢄ
ꢀꢅꢀꢇꢄ
ꢆꢁꢂꢊꢄ
ꢂꢊꢅꢊꢄ
ꢀꢀ
ꢉꢁꢊꢌꢀ ꢃꢊꢂꢌꢋꢀ ꢆꢂꢈꢅꢀ
ꢉꢎꢊꢋꢀ ꢃꢅꢂꢎꢍꢀ ꢆꢂꢈꢈꢀ
ꢉꢆꢋꢁꢀ ꢃꢍꢂꢍꢆꢀ ꢆꢂꢈꢋꢀ
ꢉꢅꢅꢎꢀ ꢃꢍꢂꢉꢌꢀ ꢆꢂꢈꢈꢀ
ꢉꢈꢁꢋꢀ ꢃꢍꢂꢋꢎꢀ ꢆꢂꢈꢅꢀ
ꢉꢊꢁꢊꢀ ꢃꢈꢂꢌꢈꢀ ꢆꢂꢈꢈꢀ
ꢉꢎꢆꢋꢀ ꢃꢊꢂꢅꢉꢀ ꢆꢂꢈꢁꢀ
ꢊꢊꢉꢌꢀ ꢃꢊꢂꢋꢁꢀ ꢆꢂꢈꢅꢀ
ꢊꢎꢉꢁꢀ ꢃꢅꢂꢅꢁꢀ ꢆꢂꢈꢋꢀ
ꢉꢆꢋꢍꢀ ꢃꢉꢂꢉꢈꢀ ꢆꢂꢈꢆꢀ
ꢉꢌꢊꢁꢀ ꢃꢉꢂꢅꢉꢀ ꢆꢂꢈꢊꢀ
ꢊꢍꢌꢉꢀ ꢃꢌꢂꢆꢅꢀ ꢆꢂꢈꢋꢀ
ꢊꢉꢍꢈꢀ ꢃꢊꢂꢌꢋꢀ ꢆꢂꢈꢁꢀ
ꢊꢉꢈꢅꢀ ꢃꢎꢂꢎꢎꢀ ꢆꢂꢈꢁꢀ
ꢊꢎꢈꢆꢀ ꢃꢌꢂꢆꢅꢀ ꢆꢂꢈꢁꢀ
ꢉꢊꢅꢁꢀ ꢃꢅꢂꢊꢋꢀ ꢆꢂꢈꢁꢀ
ꢉꢊꢆꢌꢀ ꢃꢈꢂꢁꢋꢀ ꢆꢂꢈꢅꢀ
ꢉꢋꢉꢆꢀ ꢃꢉꢂꢌꢉꢀ ꢆꢂꢈꢅꢀ
ꢍꢁꢊꢎꢀ ꢃꢋꢂꢍꢎꢀ ꢆꢂꢈꢋꢀ
ꢊꢎꢋꢎꢀ ꢃꢌꢂꢉꢋꢀ ꢆꢂꢈꢋꢀ
ꢉꢉꢈꢈꢀ
ꢍꢁꢎꢌꢀ
ꢉꢋꢋꢈꢀ
ꢉꢎꢍꢌꢀ
ꢉꢊꢊꢈꢀ
ꢉꢍꢎꢆꢀ
ꢍꢁꢉꢌꢀ
ꢊꢌꢊꢉꢀ
ꢉꢁꢁꢎꢀ
ꢉꢁꢉꢅꢀ
ꢍꢋꢌꢌꢀ
ꢉꢈꢈꢆꢀ
ꢉꢆꢎꢅꢀ
ꢊꢊꢋꢊꢀ
ꢉꢁꢅꢍꢀ
ꢉꢎꢈꢎꢀ
ꢍꢆꢉꢌꢀ
ꢉꢎꢊꢉꢀ
ꢍꢁꢎꢌꢀ
ꢉꢅꢊꢁꢀ
ꢀꢀ
ꢀꢅꢆꢇꢄ
ꢀꢃꢊꢈꢄ
ꢂꢃꢈꢃꢄ
ꢀꢁꢀꢇꢄ
ꢀꢉꢉꢉꢄ
ꢀꢅꢅꢊꢄ
ꢀꢃꢉꢊꢄ
ꢂꢆꢉꢈꢄ
ꢂꢆꢉꢊꢄ
ꢀꢇꢊꢇꢄ
ꢀꢊꢆꢉꢄ
ꢂꢊꢇꢆꢄ
ꢂꢆꢈꢀꢄ
ꢂꢀꢆꢊꢄ
ꢂꢊꢈꢁꢄ
ꢀꢅꢇꢃꢄ
ꢀꢂꢅꢀꢄ
ꢀꢀꢂꢆꢄ
ꢀꢃꢅꢁꢄ
ꢂꢃꢊꢂꢄ
ꢀꢀ
ꢉꢋꢍꢆꢀ
ꢉꢌꢎꢅꢀ
ꢊꢌꢅꢌꢀ
ꢉꢁꢉꢆꢀ
ꢉꢈꢈꢈꢀ
ꢉꢋꢋꢎꢀ
ꢉꢌꢈꢎꢀ
ꢊꢍꢈꢅꢀ
ꢊꢍꢈꢎꢀ
ꢉꢆꢎꢆꢀ
ꢉꢎꢍꢈꢀ
ꢊꢎꢆꢍꢀ
ꢊꢍꢅꢉꢀ
ꢊꢉꢍꢎꢀ
ꢊꢎꢅꢁꢀ
ꢉꢋꢆꢌꢀ
ꢉꢊꢋꢉꢀ
ꢉꢉꢊꢍꢀ
ꢉꢌꢋꢁꢀ
ꢊꢌꢎꢊꢀ
ꢀꢀ
ꢃꢁꢂꢈꢅꢀ ꢆꢂꢈꢅꢀ
ꢃꢋꢂꢁꢆꢀ ꢆꢂꢈꢁꢀ
ꢃꢍꢂꢍꢌꢀ ꢆꢂꢈꢋꢀ
ꢃꢌꢂꢆꢆꢀ ꢆꢂꢈꢅꢀ
ꢃꢉꢂꢍꢁꢀ ꢆꢂꢈꢁꢀ
ꢃꢋꢂꢌꢆꢀ ꢆꢂꢈꢊꢀ
ꢃꢋꢂꢎꢅꢀ ꢆꢂꢈꢋꢀ
ꢃꢋꢂꢆꢎꢀ ꢆꢂꢈꢅꢀ
ꢃꢎꢂꢈꢌꢀ ꢆꢂꢈꢅꢀ
ꢃꢁꢂꢌꢁꢀ ꢆꢂꢈꢅꢀ
ꢃꢎꢂꢅꢍꢀ ꢆꢂꢈꢈꢀ
ꢃꢋꢂꢌꢉꢀ ꢆꢂꢈꢁꢀ
ꢃꢊꢂꢍꢆꢀ ꢆꢂꢈꢁꢀ
ꢁꢂꢋꢆꢀ ꢆꢂꢈꢈꢀ
ꢃꢉꢂꢋꢌꢀ ꢆꢂꢈꢋꢀ
ꢃꢉꢂꢆꢆꢀ ꢆꢂꢈꢈꢀ
ꢃꢍꢂꢋꢆꢀ ꢆꢂꢈꢈꢀ
ꢃꢁꢂꢌꢆꢀ ꢆꢂꢈꢈꢀ
ꢃꢋꢂꢍꢉꢀ ꢆꢂꢈꢈꢀ
ꢃꢊꢂꢍꢎꢀ ꢆꢂꢈꢁꢀ
ꢃꢊꢂꢁꢋꢀ ꢆꢂꢈꢁꢀ
ꢉꢅꢌꢈꢀ
ꢍꢆꢊꢆꢀ
ꢉꢋꢅꢆꢀ
ꢉꢍꢈꢊꢀ
ꢉꢉꢍꢋꢀ
ꢉꢉꢌꢆꢀ
ꢍꢋꢊꢍꢀ
ꢊꢎꢅꢆꢀ
ꢉꢆꢊꢈꢀ
ꢉꢁꢊꢍꢀ
ꢍꢊꢌꢆꢀ
ꢉꢅꢊꢍꢀ
ꢉꢈꢅꢋꢀ
ꢊꢌꢉꢆꢀ
ꢉꢆꢈꢅꢀ
ꢉꢍꢌꢋꢀ
ꢉꢌꢎꢎꢀ
ꢉꢍꢅꢉꢀ
ꢍꢅꢊꢋꢀ
ꢉꢋꢆꢌꢀ
ꢀꢀ
ꢀꢈꢂꢉꢄ
ꢀꢆꢉꢇꢄ
ꢂꢃꢂꢊꢄ
ꢀꢅꢇꢆꢄ
ꢀꢇꢁꢉꢄ
ꢀꢂꢁꢇꢄ
ꢀꢆꢉꢇꢄ
ꢂꢆꢁꢇꢄ
ꢂꢂꢆꢅꢄ
ꢀꢁꢇꢉꢄ
ꢆꢉꢉꢀꢄ
ꢂꢃꢈꢀꢄ
ꢂꢀꢊꢇꢄ
ꢂꢀꢉꢈꢄ
ꢂꢃꢃꢈꢄ
ꢀꢅꢀꢊꢄ
ꢀꢀꢃꢃꢄ
ꢀꢂꢁꢇꢄ
ꢆꢉꢃꢅꢄ
ꢂꢃꢅꢆꢄ
ꢀꢀ
ꢉꢅꢊꢈꢀ
ꢉꢍꢈꢆꢀ
ꢊꢌꢊꢎꢀ
ꢉꢋꢆꢍꢀ
ꢉꢆꢁꢈꢀ
ꢉꢊꢁꢆꢀ
ꢉꢍꢈꢆꢀ
ꢊꢍꢁꢆꢀ
ꢊꢊꢍꢋꢀ
ꢉꢁꢆꢈꢀ
ꢍꢈꢈꢉꢀ
ꢊꢌꢅꢉꢀ
ꢊꢉꢎꢆꢀ
ꢊꢉꢈꢅꢀ
ꢊꢌꢌꢅꢀ
ꢉꢋꢉꢎꢀ
ꢉꢉꢌꢌꢀ
ꢉꢊꢁꢆꢀ
ꢍꢈꢌꢋꢀ
ꢊꢌꢋꢍꢀ
ꢀꢀ
ꢃꢆꢂꢉꢅꢀ
ꢃꢋꢂꢎꢁꢀ
ꢃꢍꢂꢅꢋꢀ
ꢃꢋꢂꢊꢌꢀ
ꢃꢌꢂꢍꢎꢀ
ꢃꢁꢂꢊꢋꢀ
ꢆꢂꢈꢁꢀ
ꢆꢂꢈꢊꢀ
ꢆꢂꢈꢁꢀ
ꢆꢂꢈꢈꢀ
ꢆꢂꢈꢊꢀ
ꢆꢂꢈꢊꢀ
ꢉꢅꢌꢈꢀ
ꢉꢉꢊꢋꢀ
ꢉꢅꢎꢈꢀ
ꢉꢉꢊꢋꢀ
ꢉꢁꢈꢊꢀ
ꢉꢉꢊꢋꢀ
ꢉꢉꢊꢋꢀ
ꢊꢎꢅꢆꢀ
ꢊꢎꢍꢎꢀ
ꢉꢁꢊꢍꢀ
ꢉꢉꢊꢋꢀ
ꢉꢈꢈꢆꢀ
ꢊꢎꢎꢊꢀ
ꢊꢊꢋꢊꢀ
ꢉꢆꢈꢅꢀ
ꢉꢉꢊꢋꢀ
ꢉꢉꢊꢋꢀ
ꢉꢉꢊꢋꢀ
ꢉꢉꢊꢋꢀ
ꢉꢅꢊꢁꢀ
ꢀꢀ
ꢀꢈꢈꢉꢄ
ꢉꢌꢆꢅꢀ
ꢀꢇꢀꢇꢄ
ꢀꢈꢈꢀꢄ
ꢀꢁꢅꢀꢄ
ꢀꢅꢈꢂꢄ
ꢉꢎꢈꢊꢀ
ꢂꢀꢈꢊꢄ
ꢂꢊꢀꢆꢄ
ꢀꢁꢇꢆꢄ
ꢀꢆꢀꢃꢄ
ꢂꢃꢇꢃꢄ
ꢂꢆꢈꢃꢄ
ꢂꢀꢇꢀꢄ
ꢉꢆꢋꢆꢀ
ꢀꢈꢅꢊꢄ
ꢉꢎꢆꢋꢀ
ꢀꢂꢆꢀꢄ
ꢆꢇꢆꢀꢄ
ꢂꢃꢈꢊꢄ
ꢀꢀ
ꢉꢅꢅꢈꢀ
ꢉꢌꢆꢅꢀ
ꢉꢆꢉꢆꢀ
ꢉꢅꢅꢉꢀ
ꢉꢁꢋꢉꢀ
ꢉꢋꢅꢊꢀ
ꢉꢎꢈꢊꢀ
ꢊꢉꢅꢎꢀ
ꢊꢎꢉꢍꢀ
ꢉꢁꢆꢍꢀ
ꢉꢍꢉꢌꢀ
ꢊꢌꢆꢌꢀ
ꢊꢍꢅꢌꢀ
ꢊꢉꢆꢉꢀ
ꢉꢆꢋꢆꢀ
ꢉꢅꢋꢎꢀ
ꢉꢎꢆꢋꢀ
ꢉꢊꢍꢉꢀ
ꢍꢆꢍꢉꢀ
ꢊꢌꢅꢎꢀ
ꢀꢀ
ꢃꢆꢂꢌꢋꢀ ꢆꢂꢈꢆꢀ
ꢅꢂꢍꢋꢀ ꢆꢂꢈꢈꢀ
ꢃꢊꢂꢆꢅꢀ ꢆꢂꢈꢋꢀ
ꢃꢋꢂꢍꢎꢀ ꢆꢂꢈꢆꢀ
ꢆꢂꢊꢆꢀ ꢆꢂꢈꢊꢀ
ꢃꢅꢂꢁꢌꢀ ꢆꢂꢈꢋꢀ
ꢁꢂꢋꢁꢀ ꢆꢂꢈꢁꢀ
ꢃꢅꢂꢁꢌꢀ ꢆꢂꢈꢅꢀ
ꢃꢆꢂꢈꢌꢀ ꢆꢂꢈꢈꢀ
ꢃꢆꢂꢎꢆꢀ ꢆꢂꢈꢁꢀ
ꢈꢂꢍꢅꢀ ꢆꢂꢈꢊꢀ
ꢃꢅꢂꢁꢌꢀ ꢆꢂꢈꢅꢀ
ꢃꢁꢂꢋꢎꢀ ꢆꢂꢈꢅꢀ
ꢈꢂꢈꢆꢀ ꢆꢂꢈꢈꢀ
ꢆꢂꢋꢊꢀ ꢆꢂꢈꢁꢀ
ꢃꢋꢂꢉꢆꢀ ꢆꢂꢈꢅꢀ
ꢁꢂꢁꢊꢀ ꢆꢂꢈꢅꢀ
ꢃꢈꢂꢈꢍꢀ ꢆꢂꢈꢁꢀ
ꢉꢂꢅꢋꢀ ꢆꢂꢈꢁꢀ
ꢃꢉꢂꢊꢁꢀ ꢆꢂꢈꢊꢀ
ꢃꢆꢂꢎꢌꢀ ꢆꢂꢈꢅꢀ
WHVWꢃꢅꢀ
WHVWꢃꢋꢀ
WHVWꢃꢊꢀ
WHVWꢃꢉꢀ
WHVWꢃꢍꢀ
ꢃꢈꢆꢂꢆꢁꢀ ꢆꢂꢈꢁꢀ
WHVWꢃꢎꢀ
ꢃꢈꢂꢎꢌꢀ
ꢃꢍꢂꢎꢎꢀ
ꢃꢆꢂꢎꢌꢀ
ꢃꢉꢂꢁꢊꢀ
ꢃꢉꢂꢉꢁꢀ
ꢃꢍꢂꢋꢆꢀ
ꢃꢊꢂꢎꢁꢀ
ꢃꢆꢂꢅꢅꢀ
ꢃꢋꢂꢎꢆꢀ
ꢃꢋꢂꢈꢋꢀ
ꢃꢅꢂꢁꢈꢀ
ꢃꢁꢂꢈꢎꢀ
ꢃꢍꢂꢁꢈꢀ
ꢃꢋꢂꢌꢁꢀ
ꢆꢂꢈꢈꢀ
ꢆꢂꢈꢈꢀ
ꢆꢂꢈꢁꢀ
ꢆꢂꢈꢅꢀ
ꢆꢂꢈꢈꢀ
ꢆꢂꢈꢅꢀ
ꢆꢂꢈꢋꢀ
ꢆꢂꢈꢈꢀ
ꢆꢂꢈꢈꢀ
ꢆꢂꢈꢈꢀ
ꢆꢂꢈꢁꢀ
ꢆꢂꢈꢁꢀ
ꢆꢂꢈꢅꢀ
ꢆꢂꢈꢁꢀ
WHVWꢃꢌꢀ
WHVWꢃꢈꢆꢀ
WHVWꢃꢈꢈꢀ
WHVWꢃꢈꢁꢀ
WHVWꢃꢈꢅꢀ
WHVWꢃꢈꢋꢀ
WHVWꢃꢈꢊꢀ
WHVWꢃꢈꢉꢀ
WHVWꢃꢈꢍꢀ
WHVWꢃꢈꢎꢀ
WHVWꢃꢈꢌꢀ
WHVWꢃꢁꢆꢀ
$YHUꢀ
ꢀꢀ
ꢃꢉꢂꢆꢅꢀ ꢆꢂꢈꢅꢀ
,PSURYHGꢀVROXWLRQVꢀDUHꢀKLJKOLJKWHGꢀLQꢀEROGIDFHꢀ
7DEOHꢀꢁꢂꢀ7KHꢀH[SHULPHQWꢀUHVXOWVꢀIRUꢀWKHꢀ5&'03ꢃLQVWDQFHVꢀꢄn ꢀꢅꢆꢇꢀ
Įꢀ ꢀꢆꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.5ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.75ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢈꢀ
76ꢀ
76ꢀ
76ꢀ
76ꢀ
2XUꢀDOJRULWKPꢀ
,QVWDQFHVꢀ
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
WHVWꢃꢈꢀ
ꢈꢆꢊꢅꢋꢀ
ꢍꢍꢁꢅꢀ
ꢀꢁꢂꢁꢂꢃ
ꢇꢅꢈꢇꢃ
ꢇꢉꢁꢁꢃ
ꢀꢁꢈꢀꢊꢃ
ꢇꢉꢀꢈꢃ
ꢇꢄꢊꢄꢃ
ꢆꢆꢄꢉꢃ
ꢆꢊꢆꢊꢃ
ꢀꢁꢉꢊꢁꢃ
ꢆꢆꢆꢉꢃ
ꢇꢊꢊꢈꢃ
ꢇꢀꢄꢈꢃ
ꢀꢁꢄꢉꢂꢃ
ꢇꢊꢊꢇꢃ
ꢇꢅꢀꢈꢃ
ꢀꢁꢉꢉꢁꢃ
ꢀꢁꢁꢁꢅꢃ
ꢇꢅꢉꢂꢃ
ꢆꢇꢅꢂꢃ
ꢈꢆꢌꢆꢌꢀ
ꢍꢋꢁꢍꢀ
ꢍꢅꢆꢆꢀ
ꢈꢆꢁꢈꢊꢀ
ꢍꢅꢈꢁꢀ
ꢍꢉꢊꢉꢀ
ꢃꢈꢂꢉꢍꢀ
ꢃꢁꢂꢍꢎꢀ
ꢃꢅꢂꢆꢎꢀ
ꢃꢎꢂꢆꢌꢀ
ꢃꢊꢂꢎꢆꢀ
ꢃꢎꢂꢁꢋꢀ
ꢆꢂꢉꢋꢀ
ꢆꢂꢉꢋꢀ
ꢆꢂꢉꢆꢀ
ꢆꢂꢉꢅꢀ
ꢆꢂꢉꢈꢀ
ꢆꢂꢉꢉꢀ
ꢈꢆꢊꢌꢅꢀ
ꢍꢍꢉꢋꢀ
ꢀꢁꢂꢄꢄꢃ
ꢇꢈꢄꢉꢃ
ꢇꢅꢊꢄꢃ
ꢀꢁꢀꢂꢊꢃ
ꢇꢉꢄꢈꢃ
ꢇꢉꢀꢄꢃ
ꢇꢁꢆꢂꢃ
ꢆꢆꢊꢉꢃ
ꢀꢁꢉꢇꢀꢃ
ꢆꢆꢉꢊꢃ
ꢇꢆꢀꢀꢃ
ꢇꢀꢆꢂꢃ
ꢀꢁꢄꢈꢉꢃ
ꢇꢆꢆꢄꢃ
ꢇꢂꢂꢆꢃ
ꢀꢁꢈꢁꢅꢃ
ꢇꢉꢆꢊꢃ
ꢇꢀꢊꢉꢃ
ꢇꢈꢅꢉꢃ
ꢈꢆꢌꢉꢉꢀ ꢃꢈꢂꢁꢉꢀ ꢆꢂꢉꢆꢀ
ꢍꢁꢉꢅꢀ ꢃꢌꢂꢆꢌꢀ ꢆꢂꢉꢁꢀ
ꢍꢋꢊꢉꢀ ꢃꢌꢂꢅꢆꢀ ꢆꢂꢉꢅꢀ
ꢈꢆꢈꢌꢊꢀ ꢃꢎꢂꢆꢉꢀ ꢆꢂꢉꢁꢀ
ꢍꢅꢉꢁꢀ ꢃꢁꢂꢉꢎꢀ ꢆꢂꢉꢈꢀ
ꢍꢅꢈꢉꢀ ꢃꢉꢂꢎꢈꢀ ꢆꢂꢉꢉꢀ
ꢍꢆꢎꢌꢀ ꢃꢎꢂꢉꢈꢀ ꢆꢂꢉꢉꢀ
ꢎꢎꢊꢅꢀ ꢃꢌꢂꢆꢁꢀ ꢆꢂꢉꢋꢀ
ꢈꢆꢅꢍꢈꢀ ꢃꢅꢂꢅꢋꢀ ꢆꢂꢉꢈꢀ
ꢎꢎꢅꢊꢀ ꢃꢍꢂꢎꢈꢀ ꢆꢂꢉꢅꢀ
ꢍꢎꢈꢈꢀ ꢃꢁꢂꢎꢎꢀ ꢆꢂꢉꢁꢀ
ꢍꢈꢎꢌꢀ ꢃꢊꢂꢋꢈꢀ ꢆꢂꢉꢉꢀ
ꢈꢆꢉꢁꢅꢀ ꢃꢈꢂꢌꢌꢀ ꢆꢂꢉꢈꢀ
ꢍꢎꢎꢉꢀ ꢃꢅꢂꢌꢍꢀ ꢆꢂꢉꢉꢀ
ꢍꢌꢌꢎꢀ ꢃꢌꢂꢆꢁꢀ ꢆꢂꢉꢉꢀ
ꢈꢆꢁꢆꢋꢀ ꢃꢋꢂꢉꢉꢀ ꢆꢂꢉꢈꢀ
ꢍꢅꢎꢊꢀ ꢃꢌꢂꢆꢍꢀ ꢆꢂꢉꢁꢀ
ꢍꢈꢊꢅꢀ ꢃꢅꢂꢍꢅꢀ ꢆꢂꢉꢈꢀ
ꢍꢁꢋꢅꢀ ꢃꢌꢂꢋꢅꢀ ꢆꢂꢉꢉꢀ
ꢎꢋꢎꢍꢀ ꢃꢎꢂꢊꢊꢀ ꢆꢂꢉꢁꢀ
ꢈꢆꢎꢋꢈꢀ
ꢍꢎꢌꢊꢀ
ꢀꢁꢅꢄꢅꢃ
ꢇꢉꢇꢀꢃ
ꢇꢈꢅꢄꢃ
ꢇꢆꢆꢂꢃ
ꢇꢈꢀꢁꢃ
ꢇꢄꢉꢈꢃ
ꢇꢄꢀꢇꢃ
ꢇꢁꢈꢉꢃ
ꢀꢁꢉꢇꢀꢃ
ꢇꢁꢉꢈꢃ
ꢇꢉꢊꢆꢃ
ꢇꢄꢉꢅꢃ
ꢀꢁꢀꢇꢁꢃ
ꢀꢁꢁꢅꢊꢃ
ꢇꢉꢈꢉꢃ
ꢀꢁꢀꢁꢇꢃ
ꢀꢁꢁꢊꢅꢃ
ꢇꢄꢀꢁꢃ
ꢇꢉꢀꢁꢃ
ꢈꢆꢋꢉꢋꢀ
ꢍꢅꢍꢈꢀ
ꢍꢁꢋꢉꢀ
ꢃꢁꢂꢆꢆꢀ
ꢃꢁꢂꢎꢈꢀ
ꢃꢁꢂꢊꢅꢀ
ꢆꢂꢉꢈꢀ
ꢈꢆꢊꢅꢋꢀ
ꢍꢌꢆꢋꢀ
ꢍꢊꢈꢋꢀ
ꢈꢆꢊꢅꢋꢀ
ꢍꢊꢅꢁꢀ
ꢍꢌꢎꢅꢀ
ꢍꢌꢉꢍꢀ
ꢍꢉꢌꢊꢀ
ꢈꢆꢊꢅꢋꢀ
ꢍꢋꢋꢁꢀ
ꢍꢌꢉꢈꢀ
ꢍꢊꢁꢋꢀ
ꢈꢆꢉꢁꢉꢀ
ꢈꢆꢈꢈꢈꢀ
ꢈꢆꢈꢉꢆꢀ
ꢈꢆꢊꢆꢅꢀ
ꢈꢆꢈꢆꢉꢀ
ꢍꢌꢋꢈꢀ
ꢍꢊꢈꢅꢀ
ꢀꢁꢅꢁꢆꢃ
ꢇꢄꢅꢄꢃ
ꢇꢄꢈꢆꢃ
ꢀꢁꢄꢉꢆꢃ
ꢇꢂꢁꢊꢃ
ꢇꢄꢊꢂꢃ
ꢇꢄꢂꢄꢃ
ꢆꢆꢄꢄꢃ
ꢀꢁꢈꢀꢊꢃ
ꢆꢊꢆꢁꢃ
ꢍꢌꢈꢆꢀ
ꢇꢈꢂꢀꢃ
ꢇꢇꢉꢆꢃ
ꢈꢆꢈꢌꢋꢀ
ꢇꢄꢆꢆꢃ
ꢀꢁꢄꢁꢀꢃ
ꢇꢇꢀꢁꢃ
ꢇꢉꢀꢇꢃ
ꢇꢈꢈꢇꢃ
ꢈꢆꢋꢆꢎꢀ ꢃꢉꢂꢉꢈꢀ ꢆꢂꢉꢉꢀ
ꢍꢉꢋꢉꢀ ꢃꢁꢂꢌꢎꢀ ꢆꢂꢉꢆꢀ
ꢍꢉꢁꢎꢀ ꢃꢅꢂꢍꢈꢀ ꢆꢂꢉꢁꢀ
ꢈꢆꢉꢅꢎꢀ ꢃꢅꢂꢌꢁꢀ ꢆꢂꢉꢉꢀ
ꢍꢌꢆꢊꢀ ꢃꢈꢂꢅꢆꢀ ꢆꢂꢉꢁꢀ
ꢍꢉꢊꢌꢀ ꢃꢅꢂꢉꢈꢀ ꢆꢂꢉꢁꢀ
ꢍꢉꢌꢉꢀ ꢃꢁꢂꢎꢈꢀ ꢆꢂꢉꢁꢀ
ꢎꢎꢉꢉꢀ ꢃꢅꢂꢎꢆꢀ ꢆꢂꢉꢆꢀ
ꢈꢆꢁꢈꢊꢀ ꢃꢁꢂꢍꢎꢀ ꢆꢂꢉꢆꢀ
ꢎꢊꢎꢆꢀ ꢃꢎꢂꢆꢍꢀ ꢆꢂꢉꢉꢀ
ꢍꢌꢈꢆꢀ ꢃꢆꢂꢈꢈꢀ ꢆꢂꢉꢁꢀ
ꢍꢁꢌꢈꢀ ꢃꢁꢂꢎꢅꢀ ꢆꢂꢉꢁꢀ
ꢍꢍꢅꢎꢀ ꢃꢉꢂꢊꢎꢀ ꢆꢂꢉꢉꢀ
ꢈꢆꢈꢌꢋꢀ ꢆꢂꢋꢁꢀ ꢆꢂꢉꢅꢀ
ꢍꢉꢎꢎꢀ ꢃꢎꢂꢉꢉꢀ ꢆꢂꢉꢅꢀ
ꢈꢆꢉꢆꢈꢀ ꢃꢅꢂꢊꢆꢀ ꢆꢂꢉꢋꢀ
ꢍꢍꢈꢆꢀ ꢃꢈꢂꢍꢆꢀ ꢆꢂꢉꢁꢀ
ꢍꢅꢈꢍꢀ ꢃꢉꢂꢅꢆꢀ ꢆꢂꢉꢉꢀ
ꢍꢁꢁꢍꢀ ꢃꢁꢂꢎꢌꢀ ꢆꢂꢉꢈꢀ
WHVWꢃꢉꢀ
ꢆꢂꢉꢈꢀ
ꢆꢂꢉꢁꢀ
WHVWꢃꢁꢀ
ꢍꢎꢆꢆꢀ
ꢈꢆꢉꢉꢌꢀ
ꢈꢈꢆꢋꢅꢀ
ꢍꢊꢅꢁꢀ
ꢍꢊꢈꢋꢀ
WHVWꢃꢅꢀ
ꢈꢈꢉꢉꢉꢀ
ꢈꢆꢉꢆꢍꢀ
ꢈꢆꢈꢈꢊꢀ
ꢈꢆꢈꢎꢉꢀ
ꢍꢅꢋꢌꢀ
ꢈꢈꢆꢆꢉꢀ
ꢈꢆꢈꢈꢎꢀ
ꢍꢎꢍꢉꢀ
ꢍꢎꢎꢌꢀ ꢃꢈꢆꢂꢈꢅꢀ ꢆꢂꢉꢈꢀ
WHVWꢃꢋꢀ
ꢍꢁꢈꢆꢀ
ꢍꢉꢅꢁꢀ
ꢃꢊꢂꢍꢍꢀ
ꢃꢌꢂꢋꢌꢀ
ꢆꢂꢉꢅꢀ
ꢆꢂꢉꢋꢀ
WHVWꢃꢌꢀ
ꢍꢌꢎꢅꢀ
WHVWꢃꢊꢀ
ꢎꢎꢉꢅꢀ ꢃꢈꢁꢂꢁꢅꢀ ꢆꢂꢉꢁꢀ
ꢍꢎꢍꢍꢀ
ꢈꢆꢁꢁꢁꢀ
ꢍꢉꢌꢊꢀ
ꢍꢉꢈꢍꢀ ꢃꢈꢆꢂꢊꢎꢀ ꢆꢂꢉꢅꢀ
WHVWꢃꢎꢀ
ꢎꢊꢎꢊꢀ
ꢈꢆꢅꢊꢆꢀ
ꢎꢎꢎꢅꢀ
ꢍꢊꢊꢁꢀ
ꢍꢈꢉꢁꢀ
ꢈꢆꢉꢅꢌꢀ
ꢍꢊꢊꢍꢀ
ꢍꢋꢈꢁꢀ
ꢈꢆꢅꢅꢆꢀ
ꢈꢆꢆꢆꢋꢀ
ꢍꢋꢅꢌꢀ
ꢎꢍꢋꢌꢀ
ꢃꢊꢂꢆꢊꢀ
ꢃꢅꢂꢌꢁꢀ
ꢃꢊꢂꢈꢋꢀ
ꢃꢌꢂꢋꢁꢀ
ꢃꢌꢂꢉꢉꢀ
ꢃꢋꢂꢁꢎꢀ
ꢃꢊꢂꢈꢈꢀ
ꢃꢌꢂꢉꢅꢀ
ꢃꢈꢂꢊꢁꢀ
ꢃꢌꢂꢆꢎꢀ
ꢃꢋꢂꢎꢌꢀ
ꢃꢋꢂꢌꢁꢀ
ꢆꢂꢉꢋꢀ
ꢆꢂꢉꢉꢀ
ꢆꢂꢉꢋꢀ
ꢆꢂꢉꢉꢀ
ꢆꢂꢉꢅꢀ
ꢆꢂꢉꢁꢀ
ꢆꢂꢉꢁꢀ
ꢆꢂꢉꢁꢀ
ꢆꢂꢉꢁꢀ
ꢆꢂꢉꢈꢀ
ꢆꢂꢉꢈꢀ
ꢆꢂꢉꢋꢀ
ꢍꢅꢅꢁꢀ
ꢍꢆꢁꢅꢀ
ꢈꢆꢅꢍꢈꢀ
ꢍꢆꢅꢁꢀ
ꢃꢉꢂꢋꢈꢀ
ꢃꢅꢂꢈꢊꢀ
ꢃꢋꢂꢁꢅꢀ
ꢆꢂꢉꢉꢀ
ꢆꢂꢉꢁꢀ
ꢆꢂꢉꢈꢀ
WHVWꢃꢍꢀ
ꢈꢆꢍꢊꢎꢀ
ꢍꢋꢌꢎꢀ
ꢈꢆꢍꢎꢆꢀ
ꢍꢎꢆꢍꢀ
ꢈꢆꢍꢅꢎꢀ
ꢍꢋꢋꢁꢀ
WHVWꢃꢈꢆꢀ
WHVWꢃꢈꢈꢀ
WHVWꢃꢈꢉꢀ
WHVWꢃꢈꢁꢀ
WHVWꢃꢈꢅꢀ
WHVWꢃꢈꢋꢀ
WHVWꢃꢈꢌꢀ
WHVWꢃꢈꢊꢀ
WHVWꢃꢈꢎꢀ
WHVWꢃꢈꢍꢀ
ꢈꢆꢅꢋꢌꢀ
ꢍꢊꢉꢎꢀ
ꢈꢆꢉꢆꢊꢀ
ꢍꢍꢁꢉꢀ
ꢈꢆꢎꢆꢉꢀ
ꢍꢎꢌꢆꢀ
ꢍꢅꢊꢎꢀ ꢃꢈꢉꢂꢉꢌꢀ ꢆꢂꢉꢋꢀ
ꢍꢉꢅꢋꢀ
ꢈꢆꢈꢍꢆꢀ
ꢈꢆꢆꢋꢊꢀ
ꢍꢅꢁꢅꢀ
ꢃꢌꢂꢉꢅꢀ
ꢃꢆꢂꢅꢈꢀ
ꢃꢈꢂꢅꢁꢀ
ꢃꢎꢂꢋꢆꢀ
ꢃꢋꢂꢋꢌꢀ
ꢃꢋꢂꢅꢁꢀ
ꢃꢎꢂꢁꢁꢀ
ꢃꢁꢂꢈꢁꢀ
ꢆꢂꢉꢅꢀ
ꢆꢂꢉꢅꢀ
ꢆꢂꢉꢈꢀ
ꢆꢂꢉꢁꢀ
ꢆꢂꢉꢆꢀ
ꢆꢂꢉꢉꢀ
ꢆꢂꢉꢉꢀ
ꢆꢂꢉꢈꢀ
ꢈꢆꢎꢉꢍꢀ
ꢈꢆꢋꢉꢊꢀ
ꢈꢆꢈꢅꢌꢀ
ꢈꢆꢌꢉꢅꢀ
ꢈꢆꢌꢋꢁꢀ
ꢈꢆꢈꢅꢆꢀ
ꢍꢅꢍꢆꢀ
ꢈꢆꢅꢆꢊꢀ
ꢈꢆꢁꢌꢎꢀ
ꢈꢆꢉꢎꢎꢀ
ꢈꢆꢎꢊꢉꢀ
ꢈꢆꢈꢆꢉꢀ
ꢍꢌꢋꢈꢀ
ꢈꢆꢉꢁꢉꢀ
ꢈꢆꢉꢆꢁꢀ
ꢈꢆꢁꢈꢆꢀ
ꢈꢆꢊꢆꢅꢀ
ꢈꢆꢌꢋꢅꢀ
ꢈꢆꢆꢅꢊꢀ
ꢍꢊꢈꢅꢀ
ꢈꢆꢈꢆꢍꢀ
ꢈꢆꢆꢊꢋꢀ
ꢍꢉꢈꢆꢀ
ꢈꢆꢆꢆꢍꢀ
ꢍꢅꢈꢆꢀ
WHVWꢃꢉꢆꢀ
$YHUꢀ
ꢍꢋꢆꢆꢀ
ꢀꢀ
ꢆꢅꢊꢆꢃ
ꢎꢋꢊꢎꢀ
ꢀꢀ
ꢃꢍꢂꢊꢈꢀ
ꢃꢌꢂꢁꢈꢀ
ꢆꢂꢉꢈꢀ
ꢆꢂꢉꢁꢀ
ꢍꢅꢈꢋꢀ
ꢀꢀ
ꢆꢅꢆꢇꢃ
ꢍꢈꢎꢁꢀ
ꢀꢀ
ꢆꢉꢊꢆꢃ
ꢎꢅꢊꢎꢀ
ꢀꢀ
ꢃꢊꢂꢌꢎꢀ
ꢃꢋꢂꢎꢋꢀ
ꢆꢂꢉꢈꢀ
ꢆꢂꢉꢉꢀ
ꢍꢈꢎꢁꢀ
ꢀꢀ
ꢆꢉꢆꢇꢃ
ꢎꢅꢎꢍꢀ ꢃꢊꢂꢋꢌꢀ ꢆꢂꢉꢁꢀ
ꢀꢀ ꢃꢁꢂꢎꢁꢀ ꢆꢂꢉꢉꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢃꢋꢂꢋꢍꢀ ꢆꢂꢉꢉꢀ
ꢀꢀ
ꢀꢀ
,PSURYHGꢀVROXWLRQVꢀDUHꢀKLJKOLJKWHGꢀLQꢀEROGIDFHꢀ
other parameters, the best configuration is presented as
follows: As finding the best configuration by running all
instances would be computationally too expensive, we im-
plement our numerical analysis on some selected instances.
36
Vol. 2020, No. 01, September
7DEOHꢀꢁꢂꢀ7KHꢀH[SHULPHQWꢀUHVXOWVꢀIRUꢀWKHꢀ5&'03ꢃLQVWDQFHVꢀꢄn ꢀꢅꢆꢇꢀ
Įꢀ ꢀꢆꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.5ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.75ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢈꢀ
76ꢀ
76ꢀ
76ꢀ
76ꢀ
2XUꢀDOJRULWKPꢀ
,QVWDQFHVꢀ
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢉ
T
WHVWꢃꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢁꢈꢌꢀ
ꢈꢊꢎꢁꢆꢀ
ꢈꢁꢍꢁꢍꢀ
ꢈꢅꢅꢊꢌꢀ
ꢈꢁꢌꢉꢅꢀ
ꢈꢅꢋꢅꢎꢀ
ꢈꢅꢌꢋꢋꢀ
ꢈꢅꢍꢈꢅꢀ
ꢈꢉꢍꢈꢌꢀ
ꢈꢅꢉꢊꢎꢀ
ꢈꢅꢉꢆꢁꢀ
ꢈꢁꢈꢈꢌꢀ
ꢈꢁꢅꢅꢈꢀ
ꢈꢁꢋꢅꢎꢀ
ꢈꢅꢆꢅꢊꢀ
ꢈꢁꢅꢍꢎꢀ
ꢈꢊꢋꢅꢉꢀ
ꢈꢅꢍꢍꢊꢀ
ꢀꢁꢂꢁꢃꢄ ꢈꢊꢊꢅꢆꢂꢈꢀ
ꢃꢊꢂꢊꢉꢀ
ꢈꢂꢈꢊꢀ
ꢈꢁꢆꢋꢌꢀ
ꢈꢊꢊꢋꢌꢀ
ꢈꢁꢉꢈꢆꢀ
ꢈꢅꢈꢎꢍꢀ
ꢈꢁꢎꢌꢍꢀ
ꢈꢁꢁꢌꢋꢀ
ꢈꢅꢋꢅꢍꢀ
ꢈꢅꢅꢅꢅꢀ
ꢈꢋꢈꢆꢅꢀ
ꢈꢉꢋꢍꢋꢀ
ꢈꢁꢊꢎꢆꢀ
ꢈꢅꢉꢎꢅꢀ
ꢈꢁꢊꢁꢎꢀ
ꢈꢁꢌꢊꢌꢀ
ꢈꢁꢍꢁꢅꢀ
ꢈꢅꢈꢋꢅꢀ
ꢈꢁꢉꢆꢍꢀ
ꢈꢊꢍꢁꢁꢀ
ꢈꢅꢅꢉꢈꢀ
ꢀꢁꢂꢁꢂꢄ ꢈꢊꢁꢅꢊꢂꢍꢀ
ꢀꢂꢂꢅꢂꢄ ꢈꢉꢅꢆꢌꢂꢊꢀ
ꢀꢁꢆꢂꢆꢄ ꢈꢊꢉꢊꢆꢂꢋꢀ
ꢀꢉꢆꢀꢊꢄ ꢈꢁꢅꢈꢆꢂꢊꢀ
ꢀꢁꢅꢂꢇꢄ ꢈꢁꢊꢈꢌꢂꢍꢀ
ꢀꢁꢅꢈꢊꢄ ꢈꢁꢈꢊꢉꢂꢎꢀ
ꢀꢉꢀꢉꢉꢄ ꢈꢁꢁꢍꢆꢂꢊꢀ
ꢀꢉꢃꢈꢇꢄ ꢈꢁꢍꢎꢊꢂꢌꢀ
ꢀꢉꢅꢃꢉꢄ ꢈꢅꢈꢍꢎꢂꢌꢀ
ꢀꢂꢆꢃꢅꢄ ꢈꢉꢉꢍꢊꢂꢅꢀ
ꢀꢉꢀꢂꢈꢄ ꢈꢁꢊꢉꢈꢂꢍꢀ
ꢀꢉꢀꢁꢉꢄ ꢈꢁꢁꢋꢁꢂꢅꢀ
ꢃꢅꢂꢌꢅꢀ
ꢃꢍꢂꢆꢋꢀ
ꢃꢍꢂꢊꢎꢀ
ꢃꢎꢂꢋꢋꢀ
ꢃꢅꢂꢍꢍꢀ
ꢃꢊꢂꢎꢊꢀ
ꢃꢌꢂꢋꢎꢀ
ꢃꢅꢂꢈꢉꢀ
ꢃꢎꢂꢆꢉꢀ
ꢃꢁꢂꢎꢍꢀ
ꢃꢈꢂꢎꢆꢀ
ꢃꢎꢂꢁꢎꢀ
ꢆꢂꢌꢍꢀ
ꢆꢂꢌꢎꢀ
ꢈꢂꢈꢆꢀ
ꢈꢂꢈꢅꢀ
ꢈꢂꢆꢆꢀ
ꢈꢂꢈꢊꢀ
ꢈꢂꢈꢆꢀ
ꢆꢂꢌꢆꢀ
ꢈꢂꢆꢍꢀ
ꢈꢂꢆꢉꢀ
ꢈꢂꢈꢎꢀ
ꢆꢂꢌꢆꢀ
ꢈꢁꢆꢅꢅꢀ
ꢈꢉꢎꢍꢅꢀ
ꢈꢊꢅꢉꢈꢀ
ꢈꢅꢉꢋꢈꢀ
ꢈꢁꢎꢎꢆꢀ
ꢈꢁꢎꢎꢋꢀ
ꢈꢅꢆꢍꢎꢀ
ꢈꢅꢌꢆꢉꢀ
ꢈꢋꢈꢎꢋꢀ
ꢈꢉꢍꢆꢆꢀ
ꢈꢁꢋꢎꢆꢀ
ꢈꢅꢊꢌꢌꢀ
ꢈꢁꢁꢆꢋꢀ
ꢈꢁꢎꢉꢈꢀ
ꢈꢁꢆꢍꢆꢀ
ꢈꢅꢊꢈꢉꢀ
ꢈꢁꢁꢈꢊꢀ
ꢈꢁꢁꢆꢊꢀ
ꢈꢅꢌꢆꢉꢀ
ꢀꢁꢁꢅꢂꢄ ꢈꢊꢅꢊꢁꢂꢍꢀ
ꢀꢂꢈꢃꢃꢄ ꢈꢉꢋꢍꢍꢂꢈꢀ
ꢀꢂꢃꢇꢀꢄ ꢈꢊꢆꢍꢁꢂꢁꢀ
ꢀꢉꢁꢇꢆꢄ ꢈꢁꢅꢍꢅꢂꢊꢀ
ꢀꢉꢉꢊꢊꢄ ꢈꢁꢅꢌꢈꢂꢅꢀ
ꢀꢉꢆꢊꢅꢄ ꢈꢁꢉꢋꢉꢂꢎꢀ
ꢀꢁꢅꢀꢃꢄ ꢈꢁꢈꢈꢊꢂꢁꢀ
ꢀꢉꢊꢉꢊꢄ ꢈꢁꢍꢉꢌꢂꢊꢀ
ꢀꢈꢆꢆꢁꢄ ꢈꢅꢈꢅꢌꢂꢁꢀ
ꢀꢀꢇꢊꢈꢄ ꢈꢉꢉꢊꢉꢂꢁꢀ
ꢀꢁꢃꢇꢆꢄ ꢈꢁꢈꢊꢎꢂꢍꢀ
ꢀꢉꢆꢅꢁꢄ ꢈꢁꢅꢌꢍꢂꢋꢀ
ꢀꢁꢆꢂꢈꢄ ꢈꢊꢈꢌꢅꢂꢊꢀ
ꢀꢁꢃꢈꢆꢄ ꢈꢊꢌꢍꢌꢂꢈꢀ
ꢀꢁꢃꢆꢊꢄ ꢈꢁꢈꢎꢉꢂꢁꢀ
ꢀꢉꢂꢈꢃꢄ ꢈꢁꢊꢋꢆꢂꢋꢀ
ꢀꢁꢈꢊꢀꢄ ꢈꢊꢎꢁꢅꢂꢊꢀ
ꢃꢁꢂꢎꢉꢀ
ꢃꢈꢂꢋꢊꢀ
ꢃꢅꢂꢁꢎꢀ
ꢃꢅꢂꢎꢎꢀ
ꢃꢉꢂꢆꢋꢀ
ꢃꢁꢂꢎꢍꢀ
ꢃꢎꢂꢎꢋꢀ
ꢃꢎꢂꢌꢆꢀ
ꢃꢎꢂꢉꢅꢀ
ꢃꢎꢂꢊꢆꢀ
ꢃꢋꢂꢆꢎꢀ
ꢃꢍꢂꢁꢍꢀ
ꢃꢌꢂꢅꢌꢀ
ꢃꢋꢂꢋꢆꢀ
ꢃꢉꢂꢋꢋꢀ
ꢃꢋꢂꢍꢌꢀ
ꢃꢅꢂꢌꢈꢀ
ꢆꢂꢌꢅꢀ
ꢈꢂꢈꢉꢀ
ꢈꢂꢆꢁꢀ
ꢆꢂꢌꢅꢀ
ꢈꢂꢆꢆꢀ
ꢈꢂꢆꢍꢀ
ꢆꢂꢌꢋꢀ
ꢈꢂꢈꢉꢀ
ꢆꢂꢌꢎꢀ
ꢈꢂꢈꢍꢀ
ꢆꢂꢌꢍꢀ
ꢈꢂꢈꢊꢀ
ꢆꢂꢌꢋꢀ
ꢆꢂꢌꢌꢀ
ꢆꢂꢌꢊꢀ
ꢈꢂꢆꢎꢀ
ꢈꢂꢈꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢉꢎꢍꢅꢀ
ꢈꢊꢅꢉꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢉꢋꢍꢋꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢈꢊꢋꢌꢈꢀ
ꢀꢁꢀꢆꢃꢄ ꢈꢊꢊꢋꢁꢂꢌꢀ ꢃꢁꢂꢉꢎꢀ ꢈꢂꢆꢌꢀ
ꢀꢂꢂꢇꢈꢄ ꢈꢉꢋꢅꢁꢂꢊꢀ ꢃꢊꢂꢌꢈꢀ ꢈꢂꢈꢆꢀ
ꢀꢁꢆꢁꢂꢄ ꢈꢊꢈꢋꢈꢂꢅꢀ ꢃꢊꢂꢋꢉꢀ ꢈꢂꢆꢌꢀ
WHVWꢃꢉꢀ
ꢀꢀꢇꢇꢀꢄ ꢈꢉꢉꢌꢋꢂꢋꢀ ꢃꢈꢈꢂꢁꢋꢀ ꢈꢂꢆꢊꢀ
WHVWꢃꢊꢀ
ꢀꢂꢅꢀꢀꢄ ꢈꢊꢈꢆꢉꢂꢉꢀ
ꢀꢉꢈꢂꢅꢄ ꢈꢁꢋꢈꢋꢂꢌꢀ
ꢀꢉꢂꢂꢃꢄ ꢈꢁꢅꢆꢊꢂꢈꢀ
ꢀꢁꢃꢃꢇꢄ ꢈꢊꢌꢅꢌꢂꢈꢀ
ꢃꢋꢂꢆꢊꢀ
ꢃꢉꢂꢈꢅꢀ
ꢃꢍꢂꢁꢁꢀ
ꢃꢎꢂꢋꢌꢀ
ꢆꢂꢌꢊꢀ
ꢆꢂꢌꢍꢀ
ꢆꢂꢌꢅꢀ
ꢆꢂꢌꢍꢀ
WHVWꢃꢁꢀ
ꢀꢁꢊꢅꢀꢄ
ꢈꢁꢉꢁꢊꢀ
ꢀꢁꢊꢅꢀꢄ
ꢀꢁꢊꢅꢀꢄ
ꢈꢊꢋꢌꢈꢀ ꢆꢂꢆꢆꢀ ꢈꢂꢈꢍꢀ
ꢈꢁꢊꢎꢉꢀ ꢁꢂꢆꢊꢀ ꢆꢂꢌꢋꢀ
ꢈꢊꢋꢌꢈꢀ ꢆꢂꢆꢆꢀ ꢈꢂꢈꢈꢀ
ꢈꢊꢋꢌꢈꢀ ꢆꢂꢆꢆꢀ ꢆꢂꢌꢎꢀ
WHVWꢃꢅꢀ
WHVWꢃꢋꢀ
WHVWꢃꢎꢀ
ꢀꢁꢉꢂꢈꢄ ꢈꢁꢈꢁꢈꢂꢋꢀ ꢃꢈꢁꢂꢉꢋꢀ ꢈꢂꢆꢊꢀ
WHVWꢃꢍꢀ
ꢀꢉꢇꢀꢅꢄ ꢈꢅꢆꢉꢅꢂꢉꢀ
ꢀꢈꢉꢉꢊꢄ ꢈꢅꢅꢌꢌꢂꢉꢀ
ꢀꢀꢅꢈꢊꢄ ꢈꢉꢈꢉꢆꢂꢍꢀ
ꢀꢁꢅꢃꢃꢄ ꢈꢁꢉꢉꢈꢂꢎꢀ
ꢀꢉꢂꢉꢀꢄ ꢈꢁꢅꢈꢎꢂꢍꢀ
ꢀꢂꢅꢆꢇꢄ ꢈꢊꢈꢊꢁꢂꢌꢀ
ꢀꢁꢁꢊꢁꢄ ꢈꢊꢋꢅꢌꢂꢎꢀ
ꢀꢁꢅꢁꢅꢄ ꢈꢁꢈꢊꢅꢂꢈꢀ
ꢀꢉꢆꢊꢈꢄ ꢈꢁꢉꢋꢎꢂꢋꢀ
ꢀꢁꢂꢀꢁꢄ ꢈꢊꢅꢆꢊꢂꢁꢀ
ꢀꢂꢃꢂꢃꢄ ꢈꢉꢌꢉꢅꢂꢍꢀ
ꢀꢉꢊꢆꢆꢄ ꢈꢁꢎꢁꢁꢂꢉꢀ
ꢃꢎꢂꢈꢍꢀ
ꢃꢉꢂꢊꢊꢀ
ꢃꢋꢂꢎꢊꢀ
ꢃꢍꢂꢉꢎꢀ
ꢃꢋꢂꢊꢊꢀ
ꢃꢍꢂꢅꢍꢀ
ꢃꢍꢂꢈꢋꢀ
ꢃꢁꢂꢌꢆꢀ
ꢃꢋꢂꢅꢋꢀ
ꢃꢌꢂꢁꢉꢀ
ꢃꢋꢂꢎꢍꢀ
ꢃꢍꢂꢆꢍꢀ
ꢈꢂꢆꢋꢀ
ꢈꢂꢆꢁꢀ
ꢈꢂꢈꢋꢀ
ꢈꢂꢆꢋꢀ
ꢈꢂꢈꢍꢀ
ꢈꢂꢆꢌꢀ
ꢈꢂꢈꢌꢀ
ꢆꢂꢌꢎꢀ
ꢈꢂꢈꢆꢀ
ꢆꢂꢌꢌꢀ
ꢈꢂꢈꢆꢀ
ꢈꢂꢈꢈꢀ
ꢀꢉꢃꢊꢈꢄ ꢈꢁꢌꢌꢉꢂꢈꢀ ꢎꢂꢍꢁꢀ ꢆꢂꢌꢁꢀ
ꢀꢁꢊꢅꢀꢄ ꢈꢊꢋꢌꢈꢀ ꢆꢂꢆꢆꢀ ꢈꢂꢆꢍꢀ
WHVWꢃꢌꢀ
WHVWꢃꢈꢆꢀ
WHVWꢃꢈꢈꢀ
WHVWꢃꢈꢉꢀ
WHVWꢃꢈꢊꢀ
WHVWꢃꢈꢁꢀ
WHVWꢃꢈꢅꢀ
WHVWꢃꢈꢋꢀ
WHVWꢃꢈꢎꢀ
WHVWꢃꢈꢍꢀ
WHVWꢃꢈꢌꢀ
ꢀꢀꢅꢊꢀꢄ ꢈꢉꢈꢎꢎꢂꢈꢀ ꢃꢅꢂꢎꢈꢀ ꢈꢂꢆꢁꢀ
ꢀꢁꢊꢂꢆꢄ ꢈꢊꢌꢁꢈꢂꢊꢀ ꢃꢆꢂꢅꢉꢀ ꢈꢂꢆꢁꢀ
ꢈꢁꢁꢈꢎꢀ ꢈꢁꢎꢆꢅꢂꢁꢀ ꢅꢂꢊꢆꢀ ꢈꢂꢈꢆꢀ
ꢀꢁꢀꢀꢁꢄ ꢈꢊꢉꢊꢁꢂꢋꢀ ꢃꢁꢂꢉꢉꢀ ꢈꢂꢈꢊꢀ
ꢀꢁꢁꢈꢇꢄ ꢈꢊꢅꢉꢆꢂꢎꢀ ꢃꢉꢂꢁꢊꢀ ꢈꢂꢆꢈꢀ
ꢀꢂꢅꢆꢆꢄ ꢈꢊꢆꢍꢁꢂꢎꢀ ꢃꢈꢆꢂꢆꢌꢀ ꢈꢂꢆꢁꢀ
ꢀꢁꢆꢃꢆꢄ ꢈꢊꢅꢋꢋꢂꢍꢀ ꢃꢈꢉꢂꢅꢈꢀ ꢈꢂꢆꢊꢀ
ꢀꢁꢅꢊꢉꢄ ꢈꢁꢈꢊꢋꢂꢁꢀ
ꢀꢉꢀꢇꢊꢄ ꢈꢁꢉꢍꢍꢂꢁꢀ
ꢀꢁꢆꢃꢂꢄ ꢈꢊꢅꢍꢆꢂꢉꢀ
ꢀꢁꢆꢁꢈꢄ ꢈꢊꢈꢍꢎꢂꢌꢀ
ꢀꢉꢉꢅꢆꢄ ꢈꢁꢍꢁꢆꢂꢅꢀ
ꢃꢅꢂꢌꢊꢀ
ꢃꢋꢂꢁꢋꢀ
ꢃꢍꢂꢆꢆꢀ
ꢃꢅꢂꢍꢁꢀ
ꢃꢋꢂꢋꢁꢀ
ꢈꢂꢆꢁꢀ
ꢈꢂꢈꢊꢀ
ꢈꢂꢆꢆꢀ
ꢈꢂꢈꢁꢀ
ꢈꢂꢆꢁꢀ
ꢈꢊꢎꢁꢍꢀ
ꢈꢁꢈꢍꢈꢀ ꢆꢂꢁꢉꢀ ꢈꢂꢈꢆꢀ
ꢈꢁꢆꢆꢍꢀ ꢈꢁꢉꢉꢆꢂꢉꢀ ꢉꢂꢊꢉꢀ ꢈꢂꢆꢉꢀ
ꢀꢁꢂꢉꢃꢄ ꢈꢊꢅꢅꢍꢂꢁꢀ ꢃꢊꢂꢉꢁꢀ ꢈꢂꢈꢅꢀ
ꢀꢂꢇꢊꢂꢄ ꢈꢊꢆꢁꢁꢂꢊꢀ ꢃꢈꢆꢂꢎꢆꢀ ꢈꢂꢆꢋꢀ
ꢀꢂꢇꢈꢂꢄ
ꢈꢊꢆꢋꢆꢀ ꢃꢋꢂꢈꢊꢀ ꢈꢂꢈꢅꢀ
ꢀꢉꢇꢆꢇꢄ ꢈꢅꢆꢆꢆꢂꢉꢀ
ꢃꢋꢂꢍꢍꢀ
ꢈꢂꢆꢊꢀ
ꢈꢁꢌꢆꢅꢀ ꢈꢁꢌꢌꢅꢂꢌꢀ ꢍꢂꢍꢎꢀ ꢆꢂꢌꢍꢀ
ꢈꢊꢌꢊꢌꢀ ꢈꢁꢈꢆꢌꢂꢎꢀ ꢈꢂꢍꢈꢀ ꢈꢂꢆꢍꢀ
WHVWꢃꢉꢆꢀ
$YHUꢀ
ꢈꢁꢎꢎꢈꢀ
ꢀꢀ
ꢀꢁꢃꢆꢆꢄ ꢈꢊꢌꢈꢍꢂꢋꢀ
ꢃꢎꢂꢉꢅꢀ
ꢃꢎꢂꢉꢆꢀ
ꢆꢂꢌꢉꢀ
ꢈꢂꢆꢅꢀ
ꢈꢅꢉꢅꢌꢀ
ꢀꢀ
ꢀꢁꢇꢀꢈꢄ ꢈꢁꢈꢈꢈꢂꢉꢀ
ꢃꢌꢂꢁꢋꢀ
ꢃꢎꢂꢆꢉꢀ
ꢆꢂꢌꢈꢀ
ꢈꢂꢆꢁꢀ
ꢈꢁꢋꢁꢌꢀ
ꢀꢀ
ꢀꢁꢇꢇꢈꢄ ꢈꢁꢈꢊꢁꢂꢁꢀ
ꢃꢅꢂꢉꢉꢀ
ꢃꢋꢂꢈꢍꢀ
ꢈꢂꢆꢌꢀ
ꢈꢂꢆꢁꢀ
ꢈꢊꢋꢌꢈꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ ꢃꢆꢂꢈꢎꢀ ꢈꢂꢆꢎꢀ
,PSURYHGꢀVROXWLRQVꢀDUHꢀKLJKOLJKWHGꢀLQꢀEROGIDFHꢀ
7DEOHꢀꢁꢂꢀ7KHꢀH[SHULPHQWꢀUHVXOWVꢀIRUꢀWKHꢀ5&'03ꢃLQVWDQFHVꢀꢄn ꢀꢅꢆꢆꢇꢀ
Įꢀ ꢀꢆꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.5ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢆ.75ꢀ
2XUꢀDOJRULWKPꢀ
Įꢀ ꢀꢅꢀ
2XUꢀDOJRULWKPꢀ
76ꢀ
76ꢀ
76ꢀ
76ꢀ
,QVWDQFHVꢀ
Best.Sol
Best.Sol
Aver.Sol
gapꢈ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢈ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢈ
T
Best.Sol
Best.Sol
Aver.Sol
gapꢈ
T
WHVWꢃꢅꢀ
ꢉꢆꢉꢊꢋꢀ
ꢍꢊꢉꢉꢅꢀ
ꢉꢆꢆꢉꢁꢀ
ꢍꢎꢎꢎꢈꢀ
ꢉꢆꢉꢅꢉꢀ
ꢍꢎꢍꢍꢎꢀ
ꢍꢎꢌꢈꢊꢀ
ꢉꢅꢅꢉꢅꢀ
ꢍꢎꢌꢆꢁꢀ
ꢍꢎꢈꢅꢊꢀ
ꢍꢊꢅꢅꢈꢀ
ꢍꢎꢁꢅꢊꢀ
ꢉꢆꢎꢆꢊꢀ
ꢉꢆꢅꢊꢊꢀ
ꢍꢊꢌꢁꢉꢀ
ꢉꢆꢅꢋꢋꢀ
ꢍꢊꢍꢋꢍꢀ
ꢉꢆꢈꢅꢈꢀ
ꢍꢊꢎꢌꢁꢀ
ꢀꢁꢁꢂꢂꢃ ꢉꢆꢁꢋꢌꢂꢅꢀ ꢃꢅꢂꢈꢁꢀ ꢅꢅꢂꢌꢁꢀ
ꢀꢁꢈꢉꢅꢃ ꢍꢎꢊꢎꢎꢂꢍꢀ ꢃꢆꢂꢁꢊꢀ ꢅꢅꢂꢋꢈꢀ
ꢊꢉꢉꢈꢁꢃ ꢉꢆꢍꢍꢊꢂꢋꢀ ꢃꢆꢂꢆꢉꢀ ꢅꢈꢂꢋꢅꢀ
ꢀꢂꢅꢇꢈꢃ ꢍꢊꢅꢉꢊꢂꢋꢀ ꢃꢆꢂꢍꢅꢀ ꢅꢆꢂꢌꢊꢀ
ꢊꢉꢊꢉꢊꢃ ꢉꢆꢁꢁꢈꢂꢈꢀ ꢃꢆꢂꢆꢈꢀ ꢅꢆꢂꢊꢁꢀ
ꢀꢂꢈꢅꢆꢃ ꢍꢎꢁꢉꢍꢂꢈꢀ ꢃꢆꢂꢅꢌꢀ ꢅꢆꢂꢍꢋꢀ
ꢀꢂꢈꢊꢀꢃ ꢍꢎꢊꢁꢉꢂꢍꢀ ꢃꢅꢂꢈꢁꢀ ꢅꢈꢂꢎꢈꢀ
ꢍꢊꢌꢈꢊꢀ
ꢍꢎꢈꢉꢊꢀ
ꢍꢊꢎꢆꢉꢀ
ꢍꢎꢉꢆꢈꢀ
ꢉꢆꢌꢁꢈꢀ
ꢍꢊꢅꢆꢆꢀ
ꢍꢎꢆꢆꢁꢀ
ꢉꢅꢆꢎꢌꢀ
ꢍꢎꢍꢆꢎꢀ
ꢍꢎꢎꢎꢎꢀ
ꢍꢊꢍꢊꢈꢀ
ꢍꢎꢆꢊꢁꢀ
ꢍꢊꢊꢎꢋꢀ
ꢉꢆꢌꢉꢁꢀ
ꢍꢊꢊꢅꢈꢀ
ꢉꢆꢍꢁꢈꢀ
ꢍꢎꢊꢊꢅꢀ
ꢍꢊꢆꢅꢎꢀ
ꢍꢊꢉꢈꢆꢀ
ꢍꢎꢈꢆꢉꢀ
ꢀꢁꢄꢂꢄꢃ ꢍꢊꢊꢁꢆꢂꢍꢀ ꢃꢆꢂꢍꢋꢀ ꢅꢅꢂꢈꢅꢀ
ꢀꢂꢆꢈꢅꢃ ꢍꢎꢊꢎꢎꢂꢍꢀ ꢃꢆꢂꢍꢈꢀ ꢅꢅꢂꢍꢁꢀ
ꢀꢁꢇꢁꢉꢃ ꢉꢆꢅꢍꢈꢂꢎꢀ ꢃꢆꢂꢈꢊꢀ ꢅꢅꢂꢅꢆꢀ
ꢀꢂꢀꢁꢄꢃ ꢍꢎꢎꢌꢊꢂꢌꢀ ꢃꢆꢂꢆꢈꢀ ꢅꢈꢂꢈꢊꢀ
ꢊꢉꢅꢈꢇꢃ ꢉꢅꢆꢆꢍꢂꢊꢀ ꢃꢆꢂꢆꢋꢀ ꢅꢅꢂꢎꢎꢀ
ꢀꢂꢅꢊꢊꢃ ꢍꢊꢅꢋꢁꢂꢈꢀ ꢃꢆꢂꢊꢅꢀ ꢅꢈꢂꢍꢈꢀ
ꢀꢅꢁꢂꢊꢃ ꢍꢎꢁꢍꢋꢂꢈꢀ ꢃꢆꢂꢆꢋꢀ ꢅꢈꢂꢎꢆꢀ
ꢊꢆꢉꢅꢇꢃ ꢉꢅꢈꢉꢉꢂꢈꢀ ꢃꢆꢂꢆꢍꢀ ꢅꢈꢂꢊꢈꢀ
ꢉꢆꢆꢋꢌꢀ
ꢍꢊꢁꢎꢁꢀ
ꢉꢆꢅꢍꢉꢀ
ꢍꢎꢆꢋꢌꢀ
ꢉꢆꢎꢎꢁꢀ
ꢍꢎꢊꢁꢉꢀ
ꢍꢌꢎꢅꢈꢀ
ꢉꢆꢋꢋꢍꢀ
ꢍꢊꢎꢈꢉꢀ
ꢍꢊꢅꢎꢎꢀ
ꢍꢊꢈꢊꢊꢀ
ꢍꢎꢅꢆꢈꢀ
ꢉꢆꢈꢍꢍꢀ
ꢍꢊꢍꢎꢋꢀ
ꢍꢊꢍꢆꢉꢀ
ꢍꢊꢊꢋꢊꢀ
ꢍꢊꢁꢍꢅꢀ
ꢉꢆꢆꢍꢅꢀ
ꢍꢊꢋꢌꢁꢀ
ꢍꢊꢅꢍꢌꢀ
ꢀꢁꢅꢂꢆꢃ ꢉꢆꢈꢉꢁꢂꢈꢀ ꢃꢆꢂꢌꢅꢀ ꢅꢅꢂꢆꢉꢀ
ꢀꢁꢈꢇꢀꢃ ꢍꢎꢊꢎꢎꢂꢍꢀ ꢃꢆꢂꢎꢅꢀ ꢅꢆꢂꢉꢁꢀ
ꢊꢉꢉꢀꢅꢃ ꢉꢆꢍꢅꢆꢂꢍꢀ ꢃꢆꢂꢈꢉꢀ ꢅꢅꢂꢌꢋꢀ
ꢀꢅꢁꢅꢅꢃ ꢍꢎꢉꢌꢆꢂꢈꢀ ꢃꢆꢂꢈꢉꢀ ꢅꢆꢂꢌꢊꢀ
ꢊꢉꢅꢊꢆꢃ ꢉꢅꢅꢌꢅꢂꢈꢀ ꢃꢆꢂꢍꢁꢀ ꢅꢆꢂꢅꢍꢀ
ꢀꢂꢁꢆꢇꢃ ꢍꢊꢈꢊꢎꢂꢊꢀ ꢃꢆꢂꢅꢆꢀ ꢅꢈꢂꢈꢋꢀ
ꢀꢅꢅꢈꢁꢃ ꢍꢌꢊꢍꢌꢂꢅꢀ ꢃꢆꢂꢈꢈꢀ ꢅꢆꢂꢌꢍꢀ
ꢊꢉꢇꢈꢅꢃ ꢉꢆꢊꢎꢁꢂꢅꢀ ꢃꢆꢂꢆꢊꢀ ꢅꢅꢂꢍꢍꢀ
ꢀꢁꢇꢉꢈꢃ ꢍꢊꢊꢆꢊꢂꢉꢀ ꢃꢆꢂꢁꢋꢀ ꢅꢈꢂꢆꢋꢀ
ꢀꢁꢆꢅꢀꢃ ꢍꢊꢈꢎꢆꢂꢁꢀ ꢃꢆꢂꢆꢉꢀ ꢅꢅꢂꢆꢎꢀ
ꢀꢁꢈꢅꢁꢃ ꢍꢊꢁꢍꢋꢂꢁꢀ ꢃꢆꢂꢆꢁꢀ ꢅꢈꢂꢈꢅꢀ
ꢀꢂꢉꢉꢅꢃ ꢍꢎꢈꢌꢊꢂꢌꢀ ꢃꢆꢂꢈꢁꢀ ꢅꢅꢂꢅꢎꢀ
ꢊꢉꢈꢆꢁꢃ ꢉꢆꢌꢍꢎꢂꢎꢀ ꢃꢆꢂꢆꢍꢀ ꢅꢈꢂꢆꢁꢀ
ꢀꢁꢀꢀꢉꢃ ꢉꢆꢅꢈꢆꢂꢌꢀ ꢃꢆꢂꢅꢉꢀ ꢅꢈꢂꢅꢅꢀ
ꢀꢁꢈꢂꢂꢃ ꢍꢊꢋꢊꢈꢂꢌꢀ ꢃꢆꢂꢆꢉꢀ ꢅꢅꢂꢍꢍꢀ
ꢀꢁꢁꢆꢆꢃ ꢉꢆꢅꢊꢍꢂꢉꢀ ꢃꢆꢂꢅꢁꢀ ꢅꢆꢂꢆꢋꢀ
ꢀꢁꢄꢉꢄꢃ ꢍꢊꢊꢍꢈꢂꢉꢀ ꢃꢆꢂꢆꢌꢀ ꢅꢆꢂꢊꢊꢀ
ꢀꢁꢂꢀꢈꢃ ꢉꢆꢆꢊꢊꢂꢍꢀ ꢃꢆꢂꢁꢆꢀ ꢅꢅꢂꢈꢌꢀ
ꢍꢎꢎꢁꢁꢀ
ꢍꢎꢌꢉꢁꢀ
ꢉꢆꢍꢈꢍꢀ
ꢍꢊꢅꢊꢆꢀ
ꢉꢆꢈꢅꢈꢀ
ꢍꢊꢈꢁꢌꢀ
ꢍꢎꢁꢋꢌꢀ
ꢍꢊꢋꢋꢅꢀ
ꢍꢎꢊꢎꢈꢀ
ꢍꢎꢍꢅꢎꢀ
ꢍꢎꢊꢈꢅꢀ
ꢍꢎꢆꢌꢋꢀ
ꢉꢆꢋꢌꢆꢀ
ꢉꢆꢈꢊꢉꢀ
ꢍꢊꢆꢈꢋꢀ
ꢉꢆꢊꢍꢈꢀ
ꢉꢆꢆꢊꢋꢀ
ꢉꢆꢆꢎꢊꢀ
ꢍꢊꢆꢊꢅꢀ
ꢍꢌꢎꢋꢊꢀ
ꢀꢂꢇꢇꢂꢃ ꢍꢊꢅꢆꢁꢂꢊꢀ ꢃꢆꢂꢉꢎꢀ ꢅꢈꢂꢉꢌꢀ
ꢀꢂꢇꢂꢇꢃ ꢍꢎꢊꢎꢎꢂꢍꢀ ꢃꢆꢂꢅꢁꢀ ꢅꢅꢂꢈꢊꢀ
ꢊꢉꢈꢀꢁꢃ ꢉꢆꢉꢁꢅꢂꢎꢀ ꢃꢆꢂꢈꢅꢀ ꢅꢈꢂꢋꢋꢀ
ꢀꢁꢆꢂꢈꢃ ꢍꢊꢉꢊꢆꢂꢅꢀ ꢃꢆꢂꢆꢈꢀ ꢅꢅꢂꢅꢌꢀ
ꢊꢉꢆꢊꢈꢃ ꢉꢆꢉꢆꢎꢂꢊꢀ ꢃꢆꢂꢅꢌꢀ ꢅꢈꢂꢍꢅꢀ
ꢀꢁꢈꢉꢀꢃ ꢍꢊꢍꢍꢈꢂꢋꢀ ꢃꢆꢂꢅꢉꢀ ꢅꢅꢂꢅꢊꢀ
ꢀꢂꢊꢁꢈꢃ ꢍꢎꢌꢌꢁꢂꢊꢀ ꢃꢆꢂꢅꢊꢀ ꢅꢈꢂꢉꢍꢀ
ꢀꢁꢄꢂꢄꢃ ꢍꢊꢎꢍꢌꢂꢊꢀ ꢃꢆꢂꢅꢊꢀ ꢅꢈꢂꢈꢌꢀ
ꢀꢂꢁꢄꢊꢃ ꢍꢊꢍꢆꢍꢂꢈꢀ ꢃꢆꢂꢆꢌꢀ ꢅꢅꢂꢅꢍꢀ
ꢀꢂꢈꢈꢇꢃ ꢍꢎꢉꢁꢍꢂꢉꢀ ꢃꢆꢂꢈꢉꢀ ꢅꢆꢂꢋꢁꢀ
WHVWꢃꢈꢀ
WHVWꢃꢍꢀ
WHVWꢃꢉꢀ
WHVWꢃꢁꢀ
WHVWꢃꢋꢀ
WHVWꢃꢌꢀ
WHVWꢃꢎꢀ
ꢊꢆꢉꢄꢇꢃ
ꢉꢅꢈꢎꢅꢀ ꢃꢆꢂꢈꢅꢀ ꢅꢅꢂꢊꢉꢀ
WHVWꢃꢊꢀ
ꢀꢂꢀꢆꢆꢃ ꢍꢊꢅꢊꢆꢂꢍꢀ ꢃꢅꢂꢆꢈꢀ ꢅꢅꢂꢉꢉꢀ
ꢀꢂꢈꢉꢄꢃ ꢍꢎꢁꢅꢊꢂꢊꢀ ꢃꢆꢂꢆꢉꢀ ꢅꢅꢂꢊꢈꢀ
ꢀꢁꢉꢉꢁꢃ ꢍꢊꢈꢍꢉꢂꢁꢀ ꢃꢆꢂꢈꢋꢀ ꢅꢅꢂꢋꢍꢀ
ꢀꢂꢆꢉꢇꢃ
ꢍꢎꢎꢆꢉꢀ ꢃꢆꢂꢁꢍꢀ ꢅꢆꢂꢁꢎꢀ
WHVWꢃꢅꢆꢀ
WHVWꢃꢅꢅꢀ
WHVWꢃꢅꢈꢀ
WHVWꢃꢅꢍꢀ
WHVWꢃꢅꢉꢀ
WHVWꢃꢅꢁꢀ
WHVWꢃꢅꢋꢀ
WHVWꢃꢅꢌꢀ
WHVWꢃꢅꢎꢀ
WHVWꢃꢅꢊꢀ
ꢀꢂꢂꢂꢀꢃ ꢍꢊꢋꢅꢉꢂꢅꢀ ꢃꢆꢂꢆꢅꢀ ꢅꢆꢂꢉꢈꢀ
ꢀꢁꢀꢇꢇꢃ ꢍꢊꢎꢋꢆꢂꢌꢀ ꢃꢆꢂꢆꢌꢀ ꢅꢈꢂꢆꢊꢀ
ꢀꢅꢁꢅꢅꢃ ꢍꢎꢅꢋꢆꢂꢍꢀ ꢃꢆꢂꢍꢅꢀ ꢅꢆꢂꢈꢎꢀ
ꢀꢁꢅꢀꢂꢃ ꢉꢆꢉꢎꢆꢂꢅꢀ ꢃꢆꢂꢋꢈꢀ ꢅꢅꢂꢁꢎꢀ
ꢊꢉꢅꢈꢅꢃ ꢉꢅꢅꢊꢈꢂꢅꢀ ꢃꢆꢂꢆꢉꢀ ꢅꢅꢂꢁꢊꢀ
ꢀꢁꢂꢅꢇꢃ ꢍꢊꢊꢊꢆꢂꢌꢀ ꢃꢆꢂꢆꢊꢀ ꢅꢈꢂꢁꢎꢀ
ꢊꢉꢈꢆꢆꢃ ꢉꢆꢋꢆꢊꢂꢍꢀ ꢃꢆꢂꢍꢁꢀ ꢅꢅꢂꢉꢁꢀ
ꢀꢂꢂꢂꢄꢃ ꢍꢊꢉꢍꢍꢂꢊꢀ ꢃꢆꢂꢈꢌꢀ ꢅꢅꢂꢅꢎꢀ
ꢀꢂꢂꢁꢄꢃ ꢍꢊꢅꢈꢊꢂꢍꢀ ꢃꢆꢂꢍꢈꢀ ꢅꢈꢂꢆꢅꢀ
ꢀꢁꢆꢀꢅꢃ ꢍꢊꢊꢁꢎꢂꢈꢀ ꢃꢆꢂꢌꢈꢀ ꢅꢈꢂꢈꢈꢀ
ꢀꢂꢉꢂꢇꢃ ꢍꢎꢈꢊꢅꢂꢈꢀ ꢃꢆꢂꢍꢅꢀ ꢅꢅꢂꢁꢋꢀ
ꢀꢂꢅꢇꢀꢃ
ꢍꢊꢅꢎꢊꢀ ꢃꢆꢂꢉꢅꢀ ꢅꢈꢂꢍꢌꢀ
ꢀꢂꢊꢊꢅꢃ
ꢊꢉꢅꢇꢄꢃ ꢉꢅꢅꢁꢆꢂꢉꢀ ꢃꢆꢂꢅꢅꢀ ꢅꢅꢂꢋꢍꢀ
ꢀꢁꢁꢁꢀꢃ ꢉꢆꢎꢉꢊꢀ ꢃꢆꢂꢁꢅꢀ ꢅꢈꢂꢅꢋꢀ
ꢍꢎꢌꢋꢎꢀ ꢃꢆꢂꢅꢊꢀ ꢅꢅꢂꢊꢉꢀ
ꢀꢂꢉꢀꢂꢃ ꢍꢎꢅꢊꢋꢂꢉꢀ ꢃꢆꢂꢅꢆꢀ ꢅꢈꢂꢎꢁꢀ
ꢊꢉꢇꢊꢂꢃ ꢉꢆꢎꢎꢎꢂꢈꢀ ꢃꢆꢂꢆꢁꢀ ꢅꢆꢂꢊꢎꢀ
ꢊꢉꢆꢄꢅꢃ ꢉꢆꢁꢅꢎꢂꢋꢀ ꢃꢆꢂꢍꢉꢀ ꢅꢈꢂꢆꢅꢀ
ꢀꢂꢁꢂꢅꢃ ꢍꢊꢍꢋꢈꢂꢅꢀ ꢃꢆꢂꢅꢆꢀ ꢅꢅꢂꢍꢈꢀ
ꢊꢉꢂꢁꢅꢃ ꢉꢅꢆꢈꢍꢂꢊꢀ ꢃꢆꢂꢆꢊꢀ ꢅꢈꢂꢁꢆꢀ
ꢊꢉꢉꢆꢅꢃ ꢉꢆꢅꢌꢎꢂꢍꢀ ꢃꢆꢂꢈꢆꢀ ꢅꢈꢂꢍꢅꢀ
ꢀꢁꢅꢈꢂꢃ ꢉꢆꢆꢋꢈꢂꢍꢀ ꢃꢆꢂꢆꢌꢀ ꢅꢅꢂꢁꢌꢀ
ꢊꢉꢉꢇꢆꢃ ꢉꢆꢍꢁꢉꢂꢁꢀ ꢃꢆꢂꢈꢋꢀ ꢅꢈꢂꢊꢎꢀ
ꢀꢁꢈꢂꢁꢃ ꢍꢊꢋꢎꢈꢂꢁꢀ ꢃꢆꢂꢅꢊꢀ ꢅꢆꢂꢋꢋꢀ
ꢊꢉꢆꢇꢁꢃ ꢉꢆꢍꢋꢈꢂꢁꢀ ꢃꢆꢂꢅꢅꢀ ꢅꢆꢂꢍꢈꢀ
ꢀꢁꢂꢇꢆꢃ ꢉꢆꢅꢅꢅꢂꢊꢀ ꢃꢆꢂꢆꢉꢀ ꢅꢆꢂꢍꢍꢀ
ꢀꢂꢂꢆꢉꢃ ꢍꢎꢊꢅꢆꢂꢌꢀ ꢆꢂꢆꢆꢀ ꢅꢆꢂꢅꢊꢀ
ꢊꢉꢉꢅꢁꢃ
ꢉꢆꢁꢍꢈꢀ ꢃꢆꢂꢆꢈꢀ ꢅꢆꢂꢁꢆꢀ
ꢀꢁꢀꢊꢁꢃ
ꢀꢁꢆꢈꢇꢃ ꢍꢊꢈꢍꢆꢂꢋꢀ ꢃꢆꢂꢆꢍꢀ ꢅꢆꢂꢁꢊꢀ
ꢀꢀ ꢃꢆꢂꢈꢌꢀ ꢅꢅꢂꢈꢅꢀ ꢀꢀ
ꢍꢊꢊꢅꢉꢀ ꢃꢆꢂꢎꢈꢀ ꢅꢆꢂꢎꢅꢀ
ꢀꢁꢉꢇꢅꢃ ꢍꢊꢉꢋꢈꢂꢈꢀ ꢃꢆꢂꢆꢋꢀ ꢅꢈꢂꢁꢊꢀ
WHVWꢃꢈꢆꢀ
$YHUꢀ
ꢍꢎꢎꢅꢅꢀ
ꢀꢅꢂꢇꢊꢃ
ꢍꢎꢍꢉꢈꢀ ꢃꢆꢂꢆꢅꢀ ꢅꢈꢂꢊꢌꢀ
ꢀꢀ ꢃꢆꢂꢅꢋꢀ ꢅꢅꢂꢊꢆꢀ
ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢃꢆꢂꢍꢍꢀ ꢅꢅꢂꢉꢎꢀ ꢀꢀ
ꢀꢀ
ꢀꢀ
ꢃꢆꢂꢈꢎꢀ ꢅꢅꢂꢋꢌꢀ ꢀꢀ
ꢀꢀ
ꢀꢀ
,PSURYHGꢀVROXWLRQVꢀDUHꢀKLJKOLJKWHGꢀLQꢀEROGIDFHꢀ
37
Research and Development on Information and Communication Technology
7DEOHꢀꢁꢂꢀ7KHꢀDYHUDJHꢀH[SHULPHQWDOꢀUHVXOWVꢀIRUꢀ5&'03ꢃLQVWDQFHVꢀ
Įꢀ ꢀꢄꢀ Įꢀ ꢀꢄꢂꢅꢀ Įꢀ ꢀꢄꢂꢆꢅꢀ Įꢀ ꢀꢇꢀ
,QVWDQFHꢀ
gapꢀꢀ
ꢈ
>ꢉ@ꢀ
gapꢀꢀ
ꢈ
>ꢉ@ꢀ
gapꢀꢀ
ꢈ
>ꢉ@ꢀ
gapꢀꢀ
ꢈ
>ꢉ@ꢀ
Tꢀ
Tꢀ
Tꢀ
Tꢀ
ꢊꢄꢀ
ꢋꢄꢀ
ꢃꢁꢂꢄꢊꢀ
ꢃꢁꢂꢊꢇꢀ
ꢃꢆꢂꢈꢄꢀ
ꢃꢄꢂꢊꢊꢀ
ꢄꢂꢇꢊꢀ
ꢄꢂꢈꢊꢀ
ꢇꢂꢄꢅꢀ
ꢇꢇꢂꢋꢍꢀ
ꢃꢅꢂꢈꢋꢀ
ꢃꢅꢂꢅꢌꢀ
ꢃꢆꢂꢄꢈꢀ
ꢃꢄꢂꢈꢍꢀ
ꢄꢂꢇꢈꢀ
ꢄꢂꢈꢈꢀ
ꢇꢂꢄꢋꢀ
ꢇꢇꢂꢁꢆꢀ
ꢃꢋꢂꢌꢈꢀ
ꢃꢅꢂꢍꢅꢀ
ꢃꢁꢂꢇꢍꢀ
ꢃꢄꢂꢈꢆꢀ
ꢄꢂꢇꢈꢀ
ꢄꢂꢈꢈꢀ
ꢇꢂꢄꢋꢀ
ꢇꢇꢂꢈꢇꢀ
ꢃꢄꢂꢍꢌꢀ
ꢃꢊꢂꢍꢊꢀ
ꢃꢄꢂꢇꢆꢀ
ꢃꢄꢂꢇꢁꢀ
ꢄꢂꢇꢊꢀ
ꢄꢂꢈꢈꢀ
ꢇꢂꢄꢆꢀ
ꢇꢇꢂꢌꢄꢀ
ꢅꢄꢀ
ꢇꢄꢄꢀ
7DEOHꢀꢁꢂꢀ7KHꢀH[SHULPHQWDOꢀUHVXOWVꢀIRUꢀ'03ꢃLQVWDQFHVꢀ
*5$63±ꢀ91'ꢀ *5$63±916
gap ꢀꢀ gap ꢀꢀ
*916ꢃꢄ
gap ꢀꢀ
>ꢆ@ꢀ
*916ꢃꢅ
gap ꢀꢀ
>ꢆ@ꢀ
76ꢃ5916ꢀ
2XUꢀDOJRULWKPꢀ
,QVWDQFHVꢀ
ꢄ
ꢄ
ꢄ
ꢄ
T
Tꢀ
Tꢀ
Tꢀ
Tꢀ
gap ꢀ>ꢆ@
ꢄ
gap ꢀ>ꢆ@ꢀ
ꢄ
T
>ꢆ@
>ꢆ@ꢀ
ꢄꢇꢀ
ꢅꢇꢀ
ꢈꢈꢂꢇꢉꢀ ꢇꢂꢇꢇꢀ ꢈꢈꢂꢇꢉꢀ ꢇꢂꢇꢇꢀ ꢈꢈꢂꢇꢉꢀ ꢇꢂꢇꢁꢀ ꢈꢈꢂꢇꢉꢀ ꢇꢂꢅꢈꢀ
ꢈꢊꢂꢋꢈꢀ ꢇꢂꢇꢇꢀ ꢉꢇꢂꢈꢉꢀ ꢇꢂꢇꢉꢀ ꢈꢊꢂꢅꢄꢀ ꢇꢂꢉꢄꢀ ꢈꢊꢂꢅꢊꢀ ꢇꢂꢌꢁꢀ
ꢉꢍꢂꢈꢇꢀ ꢇꢂꢇꢇꢀ ꢉꢁꢂꢅꢇꢀ ꢈꢂꢍꢉꢀ ꢉꢈꢂꢊꢇꢀ ꢅꢂꢉꢄꢀ ꢉꢈꢂꢊꢁꢀ ꢉꢂꢈꢋꢀ
ꢉꢈꢂꢅꢋꢀ ꢄꢂꢄꢄꢀ ꢉꢉꢂꢅꢌꢀ ꢄꢇꢈꢂꢊꢅꢀ ꢉꢇꢂꢁꢊꢀ ꢅꢍꢂꢌꢀ ꢉꢇꢂꢌꢅꢀ ꢈꢌꢂꢉꢀ
ꢉꢈꢂꢄꢋꢀ ꢈꢂꢁꢍꢀ ꢈꢌꢂꢁꢁꢀ ꢈꢊꢊꢍꢂꢇꢀ ꢈꢁꢂꢊꢍꢀ ꢄꢅꢉꢂꢈꢀ ꢈꢌꢂꢄꢉꢀ ꢊꢈꢂꢌꢀ
ꢉꢋꢂꢄꢄꢀ ꢋꢇꢉꢂꢌꢊꢀ ꢉꢊꢂꢍꢇꢀ ꢄꢍꢅꢉꢂꢇꢊꢀ ꢈꢊꢂꢉꢄꢀ ꢉꢄꢉꢂꢇꢍꢀ ꢈꢊꢂꢍꢉꢀ ꢉꢅꢄꢂꢁꢅꢀ
ꢉꢍꢂꢊꢊꢀ ꢈꢌꢁꢋꢂꢍꢄꢀ ꢉꢅꢂꢈꢍꢀ ꢊꢈꢄꢄꢂꢅꢄꢀ ꢉꢄꢂꢍꢄꢀ ꢊꢉꢅꢂꢉꢁꢀ ꢉꢄꢂꢅꢌꢀ ꢊꢅꢄꢂꢍꢅꢀ
ꢈꢈꢂꢇꢉꢀ
ꢈꢊꢂꢅꢊꢀ
ꢉꢈꢂꢊꢁꢀ
ꢉꢇꢂꢌꢅꢀ
ꢇꢂꢇꢇꢀ
ꢇꢂꢇꢁꢀ
ꢇꢂꢋꢍꢀ
ꢁꢂꢌꢍꢀ
ꢀꢀꢁꢂꢃꢄ
ꢀꢅꢁꢆꢅꢄ
ꢃꢀꢁꢅꢇꢄ
ꢃꢂꢁꢈꢆꢄ
ꢇꢂꢄꢇꢀ
ꢇꢂꢅꢄꢀ
ꢍꢇꢀ
ꢄꢂꢄꢅꢀ
ꢄꢇꢇꢀ
ꢅꢇꢇꢀ
ꢍꢇꢇꢀ
ꢄꢇꢇꢇꢀ
ꢄꢈꢂꢍꢅꢀ
ꢄꢅꢄꢂꢅꢄꢀ
ꢅꢇꢁꢂꢊꢉꢀ
ꢈꢌꢂꢄꢉꢀ ꢁꢌꢂꢇꢌꢀ ꢀꢈꢁꢉꢃꢄ
ꢃꢀ ꢃꢀ ꢉꢄꢂꢊꢉꢀ
ꢃꢀ ꢃꢀ
ꢃꢉꢁꢆꢈꢄ ꢅꢇꢁꢊꢂꢋꢁꢀ
,PSURYHGꢀJDSꢀLVꢀKLJKOLJKWHGꢀLQꢀEROGIDFHꢀ
7DEOHꢀꢀꢁꢀ7KHꢀH[SHULPHQWDOꢀUHVXOWVꢀIRUꢀWKHꢀLQVWDQFHVꢀLQꢀ763/,%ꢀ
2XUꢀDOJRULWKPꢀ
,QVWDQFHVꢀ
UBꢀ
Best.Sol Aver.Sol Tꢀ
GDQW]LJꢂꢃꢀ ꢄꢃꢅꢃꢆꢇ ꢀꢁꢂꢁꢃ ꢄꢃꢅꢃꢆ ꢄꢁꢄꢈ
DWWꢂꢆꢀ ꢃꢉꢊꢋꢃꢉꢇ ꢁꢄꢅꢆꢁꢄ ꢃꢉꢊꢋꢃꢉ ꢄꢁꢂꢉꢀ
HLOꢅꢄꢀ ꢄꢉꢄꢌꢆꢇ ꢀꢄꢀꢇꢃ ꢄꢉꢄꢌꢆ ꢄꢁꢌꢉꢀ
EHUOLQꢅꢃꢀ ꢄꢂꢋꢌꢃꢄꢇ ꢀꢈꢆꢇꢁꢀ ꢄꢂꢋꢌꢃꢄ ꢄꢁꢃꢉꢀ
VWꢌꢉꢀ ꢃꢉꢅꢅꢌꢇ ꢁꢄꢂꢂꢇ ꢃꢉꢅꢅꢌ ꢂꢁꢃꢄꢀ
.UR$ꢄꢉꢉꢀ ꢊꢆꢋꢄꢃꢆꢇ ꢅꢃꢆꢀꢁꢃ ꢊꢆꢋꢄꢃꢆ ꢄꢂꢁꢅꢃꢀ
.UR&ꢄꢉꢉꢀ ꢊꢈꢄꢋꢃꢂꢇ ꢅꢉꢀꢆꢁꢈ ꢊꢈꢄꢋꢃꢂ ꢄꢃꢁꢂꢄꢀ
.UR'ꢄꢉꢉꢀ ꢊꢌꢈꢊꢈꢅꢇ ꢅꢇꢉꢅꢉꢂ ꢊꢌꢈꢊꢈꢅ ꢄꢋꢁꢋꢄꢀ
(LOꢄꢉꢄꢀ
3Uꢄꢃꢂꢀ
/LQꢄꢉꢅꢀ
ꢃꢌꢅꢄꢋ ꢁꢇꢂꢀꢆ ꢃꢌꢅꢄꢋ ꢄꢃꢁꢂꢄ
ꢋꢄꢅꢂꢋꢂꢈꢆꢀꢂꢈꢆꢈꢉꢋꢄꢅꢂꢋꢂꢈ ꢄꢈꢁꢋꢄ
ꢈꢉꢋꢊꢄꢉ ꢉꢄꢆꢅꢀꢄ ꢈꢉꢋꢊꢄꢉ ꢄꢅꢁꢃꢃꢀ
ꢇ WKHꢀRSWLPDOꢀYDOXHV
7DEOHꢀꢀꢁꢀ&RPSDULVRQꢀRIꢀWKHꢀRSWLPDOꢀVROXWLRQꢀIRUꢀWKHꢀ'03ꢀZLWKꢀWKHꢀEHVWꢂIRXQGꢀ
&5'03ꢂVROXWLRQꢀXVLQJꢀWKHꢀ&5'03ꢀREMHFWLYHꢀIXQFWLRQꢀ
Įꢀ ꢀꢃꢀ Įꢀ ꢀꢃꢁꢄꢀ Įꢀ ꢀꢃꢁꢅꢄꢀ
ꢇGLIIꢀ IHDVLELOLW\ꢀ ꢇGLIIꢀ IHDVLELOLW\ꢀ ꢇGLIIꢀ IHDVLELOLW\ꢀ ꢇGLIIꢀ IHDVLELOLW\ꢀ
WHVWꢂ[ꢂꢈꢃꢀ ꢉꢁꢅꢊꢀ 1Rꢀ ꢉꢁꢅꢋꢀ 1Rꢀ ꢉꢁꢋꢊꢀ 1Rꢀ ꢄꢁꢈꢌꢀ 1Rꢀ
WHVWꢂ[ꢂꢉꢃꢀ ꢌꢁꢍꢉꢀ 1Rꢀ ꢌꢁꢆꢊꢀ 1Rꢀ ꢌꢁꢆꢅꢀ 1Rꢀ ꢌꢁꢆꢃꢀ 1Rꢀ
Įꢀ ꢀꢆꢀ
LQVWDQFHVꢀ
This configuration determined in multiple combinations are
tested and the one who has presented the best solution
is chosen. In Table 1, we define a range for each of
the five parameters that yields 1200 different parameter
combinations and run the algorithm for some selected
instances of these combinations. Each run is limited to 1000
iterations but was stopped when the best-known solution
is found. This exhaustive search for the best parameter
combinations is useful as a benchmark for evaluating the
algorithm. Looking at the parameter combinations, we find
the following settings so that our algorithm obtains the best
solutions: 훽푟 = 5, 훽휂 = 5, 훼 = 1, 푝 = 1, and 휏 = 10.
0
Lastly, the last aspect to discuss is the stop criterium of the
algorithm. The parameter m is set to 10 to balance between
38
Vol. 2020, No. 01, September
TABLE I
it can be observed that our algorithm is capable of finding
the new best solutions for the 303 RCDMP-instances. Note
that: the found-best solutions is highlighted in bold line.
THE VARIABLE PARAMETERS
Parameter
훽푟
훼
훽휂
Value Range
0 ≤ 훽푟 ≤ 10, incremented by 0.25
0.5 ≤ 훼 ≤ 1.5, incremented by 0.25
0 ≤ 훽휂 ≤ 10, incremented by 0.25
0 ≤ 휏 ≤ 20, incremented by 5
0.3 ≤0푝 ≤ 1, incremented by 0.2
Table 7 compares the results of our algorithm with the
1000 vertices for DMP. Our algorithm gives much better
gives the same results.
휏
0
푝
computation time and efficiency. This parameter setting has
thus been used in the following experiments.
Table 8 presents the average results of our algorithm
on instances with up to 150 vertices selected from the
our algorithm obtains the optimal solutions with up to
100 vertices such as KroA100, KroB100, KroC100, and
KroD100 at reasonable amount of time. The experimental
results show that the proposed algorithm can be applied
well to the DMP (note that: the DMP is another variant of
the RCDMP when resource limit is ignored), though it is
not designed to solve it. Therefore, our algorithm can easily
adapt to similar variants of the problem.
2. Bounds
To evaluate the efficiency of the metaheuristic algorithm,
its solution can be compared to 1) the optimal solution
(OPT); and 2) a good upper bound (UB). We define the
improvement of our algorithm with respect to Best.Sol
(Best.Sol is the best solution found by our algorithm)
in comparison with the optimal solution (푔푎푝 [%]), and
1
upper bound (푔푎푝 [%]) in percent respectively as follows:
2
퐵푒푠푡.푆표푙 − 퐿퐵
푔푎푝 [%] =
× 100%
(8)
1
퐿퐵
Table 9 shows that the optimal solutions for the DMP
are generally not good solutions to the CRDMP on the
same instance. Specifically, our algorithm is better than the
optimal solution for the DMP using the CRDMP objective
function since the difference between their objective values
is up to 6.24%. Although the difference is not large, all
these optimal solutions for the DMP are not feasible solu-
tions for the CRDMP. Therefore, the methods designed for
the DMP may not be adapted easily to solve the CRDMP.
Developing an algorithm for the CRDMP is very necessary.
퐵푒푠푡.푆표푙 − 푈퐵
푔푎푝 [%] =
× 100%
(9)
2
푈퐵
We choose several state-of-the-art metaheuristic algorithms
3. Results and Comparative Analysis
The tables present Best.Sol, Aver.Sol, and T, respectively.
Tables from 2 to 5 compare the results of our algorithm with
the solutions obtained by Ban et al. [4] for the RCDMP-
instances. Column TS in Tables 2 to 5 corresponds to
the best solution of Tabu Search [4]. Column 훼 is cor-
responding to the results with different resource constraint
values. The results in Table 6, which are the average values
calculated from Table 2 to 5. Tables 7 to 8 compare
our algorithm with the state-of-the-art metaheusitics in
The average scaled running time of our algorithm is
Ban et al.’s algorithm [4].
IV. DICUSSIONS
In general, metaheuristic is a suitable approach for
solving the NP-hard problems in short computation time.
Recently, a metaheuristic for solving the problem has been
proposed. The algorithm is developed in a sequential heuris-
tic approach which starts with a single initial solution, and
at each step of the search, the current solution is replaced
by another solution found in its neighborhood. Since the
search space of the problem is a combinatorial explosion,
these algorithms only explore a subset of the search space.
Therefore, they can easily fall into the local optimal in
some cases. Our hybrid algorithm that brings together the
components of the ACO, and RVND can overcome this
terms of 푔푎푝 for DMP-instances. Table 9 compares the
2
optimal solutions with the best-found CRDMP-solutions
using the CRDMP objective function. For DMP-instances,
the optimal solutions are extracted from the exact algorithm
in [2].
Tables 2 to 5 compare the results obtained by Ban et al.
[4] to our algorithm for 320 instances. The results show
that our algorithm reaches better solutions at a reasonable
amount of time. Regarding the average 푔푎푝 in Table 6,
our algorithm quality improves 7.20% compared with Ban
2
39
Research and Development on Information and Communication Technology
drawback by searching from multiple promising solution
areas, thus, its exploring search space is extended. As a
result, the chances of finding better solutions are higher. To
summarize, our scheme includes new features as follows:
and RVND to solve the problem. Extensive numerical
experiments on benchmark instances show that on average,
our algorithm finds the new best solutions in 303 instances.
For close variants of the problem, our algorithm can reach
the optimal solutions for the problems with 100 vertices in
a reasonable amount of time. When the problem size is too
large, it takes longer time to operate the whole algorithm,
lowering the efficiency of finding the optimum. In these
cases, to reduce the running time, parallelizing ACO [14]
and divide and conquer ACO [13] can be applied to large-
scale instances. This is a topic for future research.
• Two kinds of ants coexist in the ACO. The ant group
that includes the dull ants can obtain more foods than
the group consisting of only the intelligent ants. It is
suitable in the real ant’s world.
• Every search algorithm needs to address the explo-
ration and exploitation of a search space. Exploration is
the process of visiting entirely new regions of a search
space, whilst exploitation is the process of visiting
those regions of a search space within the neighbor-
hood of previously visited points. To be successful,
a search algorithm needs to establish a good ratio
between exploration and exploitation. The ACO is also
combined with the RVND to keep a balance between
exploration and exploitation. In this combination, the
ACO allows us to explore the promising solution
spaces while the RVND based on a simple principle of
systematic switches between different neighborhoods
to exploit in these spaces.
ACKNOWLEDGEMENT
This research is funded by Hanoi University of Science
and Technology (HUST) under grant number T2017-PC-
082.
REFERENCES
[1] H.G. Abeledo and G. Fukasawa and R. Pessoa and A.
Uchoa, “The Time dependent Traveling Salesman Prob-
lem: Polyhedra and Branch-cut-and price Algorithm",
J. Math. Prog. Comp., Vol. 5, No. 1, 2013, pp. 27-55.
[2] H.B. Ban, K. Nguyen, M.C. Ngo, and D.N. Nguyen,
“An Efficient Exact Algorithm for Minimum Latency
Problem", J. PI, No. 10, 2013, pp. 1-8.
[3] H.B. Ban, and D.N. Nguyen, ”A Meta-Heuristic Algo-
rithm Combining between Tabu and Variable Neigh-
borhood Search for the Minimum Latency Problem",
J. FI, Vol. 156, No. 1, 2017, pp. 21-41
Our experiments not only prove these expectations but
also indicate that this approach finds the new best known
solutions in the 303 instances in comparison with the-
state-of-art metaheuristic. Moreover, our experiments show
that the methods designed for the DMP [3, 17, 19] may
not be adapted easily to solve the CRDMP since the
optimal solutions for the DMP are infeasible solutions for
the CRDMP. Therefore, it is important for developing a
metaheuristic for the CRDMP .
We discuss more about some optimization techniques
based on swarm intelligence. There are many optimiza-
tion techniques such as Genetic Algorithm [9], Particle
Swarm Optimization (PSO) [12], Artificial Bee Colony
(ABC) [11], and Cuckoo Search (CS) [20], etc. In fact,
no optimization technique is better than the others in all
cases. However, in the paper, the ACO algorithm is used
to solve the problem because: 1) the field of ACO has
attracted a large number of researchers, and nowadays a
large number of research results of both experimental and
theoretical nature exists; 2) Its efficiency is demonstrated
through solving the other variants of problem (Traveling
Salesman Problem (TSP) [22], Vehicle Routing Problem
(VRP) [18], ...); 3) it is very understandable and fast to
implement.
[4] H.B. Ban, “Using Metaheuristic for Solving the
Resource-Constrained Deliveryman Problem", Proc.
SOICT, 2019, pp. 917-935.
[5] A. Lucena, “Time-dependent Traveling Salesman
Problem-the Deliveryman case", J. Networks, Vol. 20,
No. 6, 1990, pp. 753-763.
[6] A. Blum, P. Chalasani, D. Coppersmith, W. Pulley-
blank, P. Raghavan, and M. Sudan, “The Minimum
Latency Problem", Proc. STOC, 1994, pp. 163-171.
[7] M. Dorigo, and T. Stutzle, “Ant Colony Optimization",
Bradford Books, London, 2004.
[8] M. Fischetti, G. Laporte, S. Martello, “The Delivery-
man Problem and Cumulative Matroids", J. Oper Res,
Vol. 41, No. 6, 1993, pp. 1055–1064.
[9] D. E. Goldberg, "Genetic Algorithms in Search, Op-
timization, and Machine Learning", Addison-Wesley,
Reading, Massachusetts, 1989.
[10] H. Hasegawa, “Optimization of GROUP behavior,
Japan Ethological Society Newsletter", Vol. 43, 2004,
pp. 22-23.
V. CONCLUSIONS
In this paper, we propose the metaheuristic algorithm
which is mainly based on the principles of the ACO,
40
Vol. 2020, No. 01, September
[11] D. Karaboga, “An Idea Based on Honeybee Swarm
for Numerica Optimization”, Technical Report TR06,
Erciyes University, 2005.
Ha-Bang Ban Ha-Bang Ban received his
B.E. in Information Technology, and Ph.D
in Computer Science at Hanoi University of
Science and Technology (HUST), Vietnam
in 2006, 2015, respectively. He is currently
a lecturer at the School of Information
and Communication Technology (SOICT),
HUST, Vietnam. Research interests of Dr.
[12] J. Kennedy, R. Eberhart, “Particle Swarm Optimiza-
tion”, Conf. Neural Networks, 1995, pp. 1942–1948.
[13] X. Li, J. Liao, and M. Cai, “Ant Colony Algorithm for
Large Scale TSP”, Proc. ICECING, 2011, pp.573-576.
[14] M. Manfrin, M. Birattari, T. Stu¨tzle, and Marco
Dorigo, “Parallel Ant Colony Optimization for the
Traveling Salesman Problem”, Proc. ANTS, 2006, pp
224-234.
Ban include algorithms, graphs, optimization, and logistics, etc.
He has published many publications in peer-reviewed international
journals and conferences.
[15] I. Mendez-Diaz, P. Zabala, A. Lucena, “A New For-
mulation for the Traveling Deliveryman Problem", J.
Discret Appl Math, No. 156, 2008, pp. 3223-3237.
[16] N. Mladenovic, P. Hansen, “Variable Neighborhood
Search", J. Operations Research, Vol. 24, 1997, pp.
1097-1100.
[17] N. Mladenovic, D. Urosevi, and S. Hanafi, “Variable
Neighborhood Search for the Travelling Deliveryman
Problem", J. 4OR, Vol. 11, 2012, pp. 1-17.
[18] M. Reimann, K. Doerner, and R.F. Hartl, “Analyzing
a Unified Ant System for the VRP and Some of Its
Variants”. S. Cagnoni et al. (Eds.): EvoWorkshops,
LNCS, pp. 300-310, 2003.
[19] A. Salehipour, K. Sorensen, P. Goos, and O.Braysy,
“Efficient GRASP+VND and GRASP+VNS meta-
heuristics for the Traveling Repairman Problem", J.
Operations Research, Vol. 9, No. 2, 2011, pp. 189-209.
[20] XS. Yang, S. Deb, “Cuckoo Search Via Levy Flights”,
Proc. NaBIC, 2009, pp. 210–214.
[21] D. S. Johnson, and L. A. McGeoch, “The Traveling
Salesman Problem: A Case Study in Local Optimiza-
tion in Local Search in Combinatorial Optimization",
E. Aarts and J. K. Lenstra, eds., 1997, pp. 215-310.
[22] H. X. Huan, N. Linh-Trung, D. Duc-Dong, and T.
Huynh, “Solving the Traveling Salesman Problem with
Ant Colony Optimization: A Revisit and New Efficient
Algorithms”, J. REV, Vol. 2, No. 3–4, 2012, pp. 121-
129.
testdata/tsp/tsplib/tsplib.html.
41
10 trang
9760
Free
Bạn đang xem tài liệu "An efficient ACO+RVND for solving the resource-constrained deliveryman problem", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- an_efficient_acorvnd_for_solving_the_resource_constrained_de.pdf
