Discrete/Binary Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 148

k =8 in between the edge π

v R u , π

Ta b l e 6 . 6 . Insertion of node π

j 1 2 3 4 5

n j 3 2 1 5 4

π j 14 8 5 22 16

d π j π j +1 d 14 , 8 d 8 , 5 d 5 , 22 d 22 , 16 d 16 , 14

F ( π )= d 14 , 5 + d 5 , 22 + d 22 , 16 + d 14 , 8 + d 8 , 5 − d 33 , 44 + d 44 , 41 + d 41 , 25 + d 25 , 24 +

d 14 , 5
F (

)= d 5 , 22 + d 22 , 16 + d 16 , 14 + d 14 , 8 + d 8 , 5
Note that Case B can actually be managed by Case C , since the tour is cyclic. Note
again that the above insertion approach is somewhat different than the one in Snyder &
Daskin [30], where the cost of an insertion of node

π

k in an edge π v is evaluated

u ,

π π

by C = d v . Instead, we directly calculate the fitness function value

of the complete tour after using the insertion methods above, i.e., well suited for the
NEH insertion heuristic..

k + d − d π u u k π v

π π π π

6.2.5 Destruction and Construction Procedure

We employ the destruction and construction (DC) procedure of the iterated greedy (IG)
algorithm [27] in the DDE algorithm. In the destruction step, a given number d of nodes,
randomly chosen and without repetition, are removed from the solution. This results in
two partial solutions. The first one with the size d of nodes is called X R and includes
the removed nodes in the order where they are removed. The second one with the size
m d of nodes is the original one without the removed nodes, which is called X D .It

should be pointed out that we consider each corresponding cluster when the destruction
and construction procedures are carried out in order to keep the feasibility of the GTSP
tour. Note that the perturbation scheme is embedded in the destruction phase where p
nodes from X R are randomly chosen without repetition and they are replaced by some
other nodes from the corresponding clusters.
The construction phase requires a constructive heuristic procedure. We employ the
NEH heuristic described in the previous section. In order to reinsert the set X R

−

into the

destructed solution X D

1 in X R

R

in a greedy manner, the first node π is inserted into all

d + 1 positions in the destructed solution X D possible m − generating m − d + 1 partial

R

solutions. Among these m

1 , the best partial
solution with the minimum tour length is chosen and kept for the next iteration. Then
the second node

− d + 1 partial solutions including node π

R
2

in X R is considered and so on until X R π is empty or a final solution

is obtained. Hence X D is again of size m .
The DC procedure for the GTSP is illustrated through Table 6.7 and Table 6.12
using the GTSP instance in Table 6.2. Note that the destruction size is d = 2andthe
perturbation strength is p = 1 in this example. Perturbation strength p = 1 indicates
replacing (mutating) only a single node among two nodes with another one from the
same cluster.