Information Technology Reference
In-Depth Information
Procedure 2.
constructSolution(
α
,
R
)
1:
X
π
←∅
2:
K ← T
3:
R
=
}
4:
P ← getFeasiblePaths
(
K,R
)
5:
while
(
R
=
∅
)
do
6:
{
i, j
:(
i, j, p, r
ijp
)
∈
R
P}
ϕ
min
←
min
{ϕ
(
i, j, k
):(
i, j, k
)
∈
P}
ϕ
max
←
max
{ϕ
(
i, j, k
):(
i, j, k
)
∈
7:
P
:
ϕ
(
i, j, k
)
≤ ϕ
min
+
α
(
ϕ
max
− ϕ
min
)
}
9: (
i, j, k
)
←
chosen randomly from RCL
10: (
X
k
,R
)
← assignProducts
(
i,j, k, R,X
)
11:
end while
12:
returnToDepot
(
X
Π
)
13:
return
X
8:
RCL =
{
(
i, j, k
)
∈
ϕ
δ
(
i,j,k
)=
c
[
u
(
k
)
i
]
+
c
[
ij
]
+
c
jσ
(
k
)]
where
δ
=
s
(
d
)if
k
is a single (double) vehicle. This function estimates the cost
of traveling from the vehicle
k
current location
u
(
k
)tonode
i
then to
j
and then
back to its depot
σ
(
k
). Then, a restricted candidate list (RCL) is built (Step 9)
with those elements whose greedy function value falls within
α
%ofthebest
possible value. An element from RCL is randomly chosen. Step 10 performs the
assignment of route (
i,j
) to vehicle
k
, and figures out the amount of product to
be loaded by first assigning the non-returnable items without exceeding the non-
returnable capacity, and then filling the vehicle with the returnable products,
performing the necessary time updating for vehicle
k
and remaining orders to be
served
R
. By proceeding this way, we guarantee that the product type priority
rule (i.e., not placing type N products on top of type R in vehicles with no shelf)
is met. Finally, in Step 12, we make sure that every vehicle returns from its
current location to its depot.
Improvement Phase:
A solution delivered by the construction phase might not
necessarily satisfy the dock capacity constraints (20). Therefore, the goal of the
local search is to attempt to improve the quality of the solution or to repair in-
feasibility if needed. The proposed improvement phase (depicted in Procedure 3)
includes three different methods, which are described next.
Procedure 3.
localSearch()
1:
mergeV ehicles
()
2:
transferShipment
()
3:
repairDocks
()
4:
return
Method 1: Merging single vehicles.
The idea behind this method is to iden-
tify those pairs of single vehicles that use the same route and merge them
