Smallest Position Value Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 130

R
k =27 into the last position of partial solution for Case B

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

j 1 2 3 4 5 6 7 8 9 10 11

j

π 1 22 20 50 10 33 44 41 25 24 27

d π j π j +1 d 1 , 22 d 22 , 50 d 20 , 50 d 50 , 10 d 10 , 33 d 33 , 44 d 44 , 41 d 41 , 25 d 25 , 24 d 24 , 27 d 27 , 1

174 7 15 21 17 12 17 20 21 14 22 8

Example C:

u = 6
v = 7
Remove = d u v

π π

Remove = d 7

Remove = d 33 , 44
Add = d

6

π π

k + d

u k π v

π π π

Add = d 1 + d

7
Add = d 33 , 27 + d 27 , 44
F (

D
6

1 π

π π π

)= F π

D + Add

π − Remove

F ( )= d 1 , 22 + d 22 , 20 + d 20 , 50 + d 50 , 10 + d 10 , 33 + d 33 , 44 + d 44 , 41 + d 41 , 25 + d 25 , 24 +

d 24 , 1 + d 33 , 27 + d 27 , 44 −

π

d 33 , 44

F ( )= d 1 , 22 + d 22 , 20 + d 20 , 50 + d 50 , 10 + d 10 , 33 + d 44 , 41 + d 41 , 25 + d 25 , 24 + d 24 , 1 +

d 33 , 27 + d 27 , 44

π

k between an edge π v for Case C

u , π

Ta b l e 5 . 7 . Insertion of node π

j 1 2 3 4 5 6 7 8 9 10 11

j

π 1 22 20 50 10 33 27 44 41 25 24

d π j π j +1 d 1 , 22 d 22 , 50 d 20 , 50 d 50 , 10 d 10 , 33 d 33 , 27 d 27 , 44 d 44 , 41 d 41 , 25 d 25 , 24 d 24 , 1

230 7 15 21 17 12 41 33 20 21 14 29

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 [26], where the cost of an insertion of node in an edge π

v . R

k

u ,

π π

5.3.1 Hybridization with Local Search

The hybridization of DE algorithm with local search heuristics is achieved by per-
forming a local search phase on every trial individual generated. The SWAP proce-
dure [26], denoted as LocalSearchSD in this chapter, and the 2-opt heuristic [21] were