Information Technology Reference
In-Depth Information
into a double vehicle (see Figure 1). This step is done only if feasibility with
respect to the time window constraint is kept and the resulting cost of the
merge is less than the sum of the cost of both single vehicles.
a) Before
b) After
D
D
A
A
C
C
B
B
^
`
S
S
ABCDA
ABCDA
,,,,
,,,,
^
`
S
ABCDA
,,,,
1
1
^
`
2
Fig. 1.
Merging two single vehicles into one double vehicle
Method 2: Transfering loads between vehicles.
The idea behind it is to
analyze vehicles (either single or double) emanating from the same plant
and try to combine both routes into a single route by one of the vehicles.
This move is allowed only if the vehicles to be combined are of the same
type and the resulting route is feasible with respect to the time window
constraints. The method is depicted in Procedure 4, where
u
and
v
denote
the vehicles to be combined with corresponding routes
π
u
=
{
u
1
,u
2
,...,u
u
}
and
π
v
=
{
v
1
,v
2
,...,v
v
}
, respectively. Here, the neighborhood of possible
moves is
N
2
(Step 1).
Note in Steps 5-9, when combining these routes
π
u
and
π
v
, if vehicle
u
has
still some load that must be delivered back to its depot
σ
(
u
) or if vehicle
v
must pickup some load in
σ
(
k
) then the resulting combined route would have
to go through the depot resulting in
π
u
=
;otherwise,
the combined vehicle may skip the depot to have
π
u
as in Step 8.
{
u
1
,...,u
u
,v
2
,...,v
v
}
Procedure 4.
transferShipment()
1:
N
2
=
{
(
k
1
,k
2
)
∈ K × K
:
σ
(
k
1
)=
σ
(
k
2
)
∧ v
type
k
1
=
v
type
k
2
}
2:
while
(
|N
2
| >
0)
do
3:
(
u, v
)
←
chose one element of
N
2
;
N
2
← N
2
\{
(
u, v
)
}
4:
π
u
=
u
1
,...,u
u
;
π
v
=
v
1
,...,v
v
if
p∈P
g
σ
(
u
)
up
>
0
∨
p∈P
g
σ
(
v
)
vp
>
0
then
5:
6:
π
u
=
u
1
,...,u
u
,v
2
,...,v
v
7:
else
8:
π
u
=
u
1
,...,u
u−
1
,v
2
,...,v
v
9:
end if
10:
if
(
π
u
is a feasible route path and
f
(
π
u
)
<f
(
π
u
)+
f
(
π
v
))
then
11:
π
u
← π
u
12:
K ← K \{v}
13:
N
2
← N
2
\{
(
k
1
,k
2
):
k
1
=
v ∨ k
2
=
v}
14:
end if
15:
end while
16:
return
