Information Technology Reference
In-Depth Information
•
Step 8: Stopping criterion
-
If the number of generations exceeds the maximum number of generations, or
some other termination criterion, then stop; otherwise go to step 2.
5.3
Insertion Methods
In this section of the chapter, the insertion methods denoted as
LocalSearchSD()
are
modified from the literature and facilitate the use of the local search. Insertion methods
are based on the insertion of node
R
k
into
m
+ 1 possible positions of a partial or de-
π
D
. Note that as
an example, only a single node is considered to be removed from the current solution to
establish
with
m
nodes and an objective function value of
F
π
D
structed tour
π
R
k
π
with a single node and re-inserted into the partial solution. Such insertion
R
k
of node
1 possible positions is actually proposed by Rosenkrantz et al. [22]
for the TSP. Snyder & Daskin [26] adopted it for the GTSP. It is based on the removal
and the insertion of node
π
into
m
−
in an edge
π
v
of a partial tour. However, it avoids the
R
k
u
,
π
π
R
k
insertion of node
π
on the first and the last position of any given partial tour. Suppose
R
that node
π
k
=27 will be inserted in a partial tour in Table 5.4.
Ta b l e 5 . 4 .
Partial Solution to Be Inserted for the Instance 11EIL51
j
1
2
3
4
5
6
7
8
9
10
j
π
1
22
20
50
10
33
44
41
25
24
d
π
j
π
j
+1
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
173
7
15
21
17
12
17
20
21
14
29
R
k
D
A
Insertion of node
π
in the first position of the partial tour
π
a
Remove
=
d
m
π
1
π
b
Add
=
d
+
d
k
π
1
m
π
k
π
π
D
are fit-
ness function values of the tour after insertion and the partial tour,
respectively.
)=
F
π
D
+
Add
) and
F
π
b
F
(
π
−
Remove
,where
F
(
π
Example A:
Remove
=
d
D
1
m
π
π
Remove
=
d
10
π
1
π
Remove
=
d
24
,
1
Add
=
d
+
d
k
π
1
m
π
k
π
π
Add
=
d
+
d
1
π
1
10
π
1
π
π
Add
=
d
27
,
1
+
d
24
,
27
F
(
)=
F
π
D
+
Add
−
π
Remove
Search WWH ::
Custom Search