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

procedure LS (π)

h := 1
while ( h ≤ m ) do
π ∗ := LocalSearchSD (π)
if ( f (π ∗ ) ≤ f (π)) then
π := π ∗
h := 1

else

h := h + 1

else
endwhile
ret urn π
end procedure

Fig. 5.2. The Local Search Scheme

Procedure SWAP ()

remove j f rom T

for each k ∈ V j
c k min d uk + d kv − d uv / ( u , v ) is an edge in T ←

k ∗ ←

{ c k }

arg min
k ∈ V j

insert k ∗ into T between (u , v)

Fig. 5.3. The SWAP Procedure

separately applied to each trial individual. The 2-opt heuristic finds two edges of a
tour that can be removed and two edges that can be inserted in order to generate a new
tour with a lower cost. More specifically, in the 2-opt heuristic, the neighborhood of a
tour is obtained as the set of all tours that can be replaced by changing two nonadjacent
edges in that tour. Note that the 2-opt heuristic is employed with the first improvement
strategy in this study. The pseudo code of the local search ( LS ) procedures is given in
Fig 5.2.
As to the LocalSearchSD procedure, it is based on the SWAP procedure and is
basically concerned with removing a node from a cluster and inserting a different node
from that cluster into the tour. The insertion is conducted using a modified nearest-
neighbour criterion, so that the new node may be inserted on the tour in a spot different.
Each node in the cluster is inserted into all possible spots in the current solution and the
best insertion is replaced with the current solution. The SWAP procedure of Snyder &
Daskin [26] is outlined in Fig 5.3, whereas the proposed DE algorithm is given in Fig
5.4. Note that in SWAP procedure, the followings are given such that tour T ;set V j ;
node j ∈ V j , j ∈ T ; distances d uv between each u , v ∈ V .

5.4 Computational Results

Fischetti et al. [8] developed a branch-and-cut algorithm to solve the symmetric GTSP.
The benchmark set is derived by applying a partitioning method to standard TSP