Information Technology Reference
In-Depth Information
procedure
LS
(π
←
X
)
h
:= 1
while
(
h
≤
m
)
do
π
∗
:=
LocalSearchSD
(π
←
X
)
if
(
f
(π
∗
←
X
)
≤
f
(π
←
X
))
then
π
←
X
:= π
∗
←
X
h
:= 1
else
h
:=
h
+ 1
else
endwhile
ret urn
π
←
X
end procedure
Fig. 6.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
∗
←
arg min
k
{
c
k
}
∈
V
j
insert k
∗
into T between (u
,
v)
Fig. 6.3.
The SWAP Procedure
6.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 in-
stances from the TSPLIB library [23]. The benchmark set with optimal objective func-
tion values for each of the problems is obtained through a personal communication
with Dr. Lawrence V. Snyder. The benchmark set contains between 51 (11) and 442
(89) nodes (clusters) with Euclidean distances and the optimal objective function value
for each of the problems is available. The DDE algorithm was coded in Visual C++
and run on an Intel Centrino Duo 1.83 GHz Laptop with 512MB memory. The popula-
tion size was fixed at 100. The initial population is constructed randomly and then the
NEH insertion heuristic was applied to each random solution. The destruction size and
perturbation strength were taken as 5 and 3, respectively. The crossover and mutation
probability were taken as 0.9 and 0.2, respectively. PTL [33] crossover operator is used
in the DDE algorithm. The DDE algorithm was terminated when the best so far solu-
tion was not improved after 50 consecutive generations. Five runs were carried out for
each problem instance to report the statistics based on the relative percent deviations(
Δ
)
from optimal solutions as follows
(
H
i
/
R
R
i
=1
−
×
OPT
)
100
Δ
avg
=
(6.8)
OPT
Search WWH ::
Custom Search