Information Technology Reference
In-Depth Information
Step3: Calculate the exchanged objective function
f
1
, if
f
1
>
f
, turn to Step4; if
not, turn to Step5;
Step4: If the current optimal solution does not exist in the tabu list, update tabu list,
input the obtained optimal solution into the tabu list, simultaneously remove
out the ban-lifted elements; otherwise, turn to Step5;
=
ii
, turn to Step1;
Step6: repeat Step1- 5, till the current optimal solution can not update.
Step5:
+
1
3.4 Adaptive Tabu Length
In order to ensure effectiveness of the tabu list, during the whole process of searching,
make
[
]
L
min
,
L
as its variable region
a
N
,
b
N
, in it
0
<
a
<
b
. So the tabu
max
length
L
's variable scope is the formula as the following:
L
λ
L
λ
L
=
+
(
−
)
(6)
min
max
I
n the formula,
L
and
ma
L
are the upper and lower bound of tabu length
L
's dy-
namic change respectively,
N
refers to the number of clients, the weighing coefficient
is
min
0
≤ λ
≤
1
.
4 Experimental Calculation and Result Analysis
Example One: The data originates from Document [6]. There are one depot and 20
client nodes, the coordinates and demand amount of each node is created randomly, as
indicated in table 1; give six vehicles of the same type, and the load capacity is 8.
Table 1.
Known condition of examples
Item coordinate Distribution
amount
Item coordinate Distribution
amount
0
(52,4)
0
1
(15,49)
1.64
11
(24,89)
2.35
2
(0,61)
1.31
12
(19,25)
2.60
3
(51,15)
0.43
13
(20,99)
1.00
4
(25,71)
3.38
14
(73,91)
0.65
5
(38,62)
1.13
15
(100,95)
0.85
6
(35,45)
3.77
16
(7,73)
2.56
7
(100,4)
3.84
17
(69,86)
1.27
8
(10,52)
0.39
18
(24,3)
2.69
(26,79)
0.24
(66,14)
3.26
9
19
(87,7)
1.03
(9,30)
2.97
10
20
4.1 Solution of New Tabu Search Algorithm
This algorithm adopts the following parameters as part. The maximum iterative times
are
max_
iter
=500, tabu length is
α
=
2
,
β
=
3
,
λ
=
0
.
6
, and candidate solution
Search WWH ::
Custom Search