Information Technology Reference
In-Depth Information
Step4: if
w
1
−
q
≤
w
, and
D
+
D
≤
D
; then
R
=
R
{
i
}
,
h
=
h
+
1
if not turn
U
k
i
k
i
−
1
i
k
k
k
k
k
to Step6;
Step5: if
k
>
K
, then
k
=
K
, otherwise,
k
=
k
;
Step6:
k
=
k
+
1
, turn to Step3;
Step7:
ii
, turn to Step2;
Step8: repeat Step2-7,
K
recorded the total used vehicles,
=
+
1
R
recorded a group of
feasible routes.
3.2 Inner Neighborhood Operation
Specific procedures as such:
(1) 1-move
move
1 is a heuristic algorithm the same as operators (1, 0) and (0, 1), which can
effectively improve the quality of solutions and the feasibility of poor solutions.
(2) 2-opt
)
−
ia
sig-
nified to change the direction of the route from
i
to
j
. That was in the
l
route, the
client points were:
signified the neighbor point of the client point
i
in the route
l
, and
(
,
j
)
k
(
i
(
,
2
,...,
n
,
)
, in it, 0 signified distribution centre. The procedures
of the
2
−
opt
neighborhood operation were as such:
Step1:
i
:
=
1
i
:
=
0
;
1
Step2: if
i
>
n
−
2
, end; otherwise, turn to Step3;
Step3: revise
i
:
=
k
(
i
),
j
:
=
k
(
i
),
j
:
=
i
+
2
;
2
i
1
2
Step4: if
j
>
n
, turn to Step8, if not, turn to Step5;
j
s
j
, change route
l
as such (1)
a
i
j
Step5:
:
=
(
)
(
,
)
, (2) alternately used
2
1
2
1
i
j
i
j
i
1
i
j
j
(
,
)
and
(
,
)
, substitute
(
,
)
and
(
,
)
;
1
1
2
2
2
1
2
l
is feasible, and better than
l
, revise
l
, if not, turn to
Step6: If the changed route
Step7;
Step7:
j
:
=
j
,
j
:
=
j
+
1
, return to Step4;
1
2
Step8:
i
:
=
i
,
i
:
=
i
+
1
, return to Step2.
1
2
3.3 Outer Neighborhood Operation
(1) 2-opt*
That is in the route
l
, the client points are
(
,
2
,...,
n
,
, in the route
k
, the client
points are
(
0
2
,...,
m
, in it, 0 signifies distribution centre.
,
)
Step1: Randomly choose n number of client points in the route
l
, for each client
point
i
, choose client point
j
nearby the route
k
, if exist, exchange
chains
(
i
,
i
+
1
),
(
j
,
j
+
1
;
1
l
and
1
k
,
Step2: Conduct
2
−
opt
neighborhood operation in the exchanged routes
to obtain feasible solution;
Search WWH ::
Custom Search