Information Technology Reference
In-Depth Information
3. Insertions:
a) Insert node 4 into three possible positions of the current partial tour as follows:
{
4
,
3
,
1
,
4
}
,
{
3
,
4
,
1
,
3
}
and
{
3
,
1
,
4
,
3
}
. Assume that the best objective function
value is with the partial tour
{
3
,
4
,
1
,
3
}
. So the current partial tour will be
{
3
,
4
,
1
}
.
b) Next, insert node 2 into four possible positions of the current partial tour as fol-
lows:
{
2
,
3
,
4
,
1
,
2
}
{
3
,
2
,
4
,
1
,
3
}
{
3
,
4
,
2
,
1
,
3
}
{
3
,
4
,
1
,
2
,
3
}
,
,
and
. Assume that
the best objective function value is with the partial tour
{
3
,
2
,
4
,
1
,
3
}
.Sothe
.
c) Finally, insert node 5 into five possible positions of the current partial tour
as follows:
current partial tour will be
{
3
,
2
,
4
,
1
}
{
5
,
3
,
2
,
4
,
1
,
5
}
,
{
3
,
5
,
2
,
4
,
1
,
3
}
,
{
3
,
2
,
5
,
4
,
1
,
3
}
,
{
3
,
2
,
4
,
5
,
1
,
3
}
and
{
3
,
2
,
4
,
1
,
5
,
3
}
. Assume that the best objective function value is with the partial
tour
{
3
,
2
,
4
,
5
,
1
,
3
}
. So the final complete tour will be
π
=
{
3
,
2
,
4
,
5
,
1
}
.
6.2.4
Insertion Methods
In this section of the chapter, the insertion methods are modified from the literature and
facilitate the use of the local search. It is important to note that for simplicity, we do
not include the cluster information in the following examples. However, whenever an
insertion move is carried out, the corresponding cluster is also inserted in the solution.
Insertion methods are based on the insertion of node
R
k
into
m
+ 1 possible positions of
π
D
.
Note that as an example, only a single node is considered to be removed from the current
solution to establish
D
with
m
nodes and an objective function value of
F
π
a partial or destructed tour
π
R
k
π
with a single node and re-inserted into the partial solution. Such
R
k
insertion of node
1 possible positions is actually proposed by Rosenkrantz
et al. [26] for the TSP. Snyder & Daskin [30] 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,
R
k
u
,
π
π
R
k
it avoids the insertion of node
π
on the first and the last position of any given partial
R
tour. Suppose that node
π
k
=8 will be inserted in a partial tour in Table 6.3.
Ta b l e 6 . 3 .
Current solution
j
1
2
3
4
j
1
n
j
n
j
3
1
5
4
2
j
j
π
14
5
22
16
π
8
d
π
j
π
j
+1
d
14
,
5
d
5
,
22
d
22
,
16
d
16
,
14
R
k
D
A
Insertion of node
π
in the first position of the partial tour
π
a
Remove
=
d
1
π
m
π
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
(
π
Search WWH ::
Custom Search