Information Technology Reference
In-Depth Information
The proposed method is depicted in Procedure 1. The problem involves many
decisions at different levels. Thus, to make the problem more tractable a de-
composition approach is taken. The main idea is first to estimate point-to-point
requests (done in Step 5), and then, based on this information, to apply the it-
erative GRASP phases of construction (Step 7) and local search (Step 8). Each
of these components is described next.
Procedure 1.
GRASP(
Δβ
,
α
,
limit iter
)
Input:
Δβ
, step parameter for cost matrix;
α
, RCL quality parameter;
limit iter
,
number of iterations
Output:
X
best
, best solution found
1:
X
best
←∅
;
f
(
X
best
)
←
+
∞
2:
find shortest paths(G, C
s
,C
d
,S
s
,S
d
)
3:
β ←
0
4:
while
(
β ≤
1)
do
5:
R ← solve TP(β)
6:
for
(
iter
=1to
limit iter
)
do
7:
X ← constructSolution
(
α, R
)
8:
X ← localSearch
(
X
)
9:
if
(
X
is better than
X
best
)
then
10:
X
best
← X
11:
end if
12:
end for
13:
β ← β
+
Δβ
14:
end while
15:
return
X
best
Preprocessing: Construction of the optimal cost and time matrices:
Initially we
have an undirected graph where the edges handle two types of costs (
c
ij
and
c
ij
)andtwotypesoftimes(
s
ij
and
s
ij
), for single and double vehicles. In this
preprocessing phase (Step 2 of Procedure 1), we find optimal shortest paths be-
tween all pairs of nodes for each of the four matrices by applying the well-known
Floyd-Warshall algorithm. Let
c
[
ij
]
and
c
[
ij
]
be the cheapest cost of traveling
from node
i
to node
j
using a single and double vehicle, respectively. Similarly,
let
s
[
ij
]
and
s
[
ij
]
represent the shortest time of traveling from
i
to
j
for a single
and a double vehicle, respectively. This information on optimal paths is used in
other components of the algorithm and needs to be computed only once.
Decomposition: Point-to-point request generation:
As mentioned before, to make
the problem more tractable we first attempt to estimate point-to-point requests.
Each request or order is identified by a vector (
i,j,p,r
ijp
), where
r
ijp
is the
amount of product
p
(measuredinnumberof12-bottleboxes)tobepickedupat
i
and delivered to
j
. To compute these requests, we solve a transportation problem,
where we take as input the information on pickup and delivery quantities at every
node (given by parameters
n
ip
and
n
ip
, respectively), and the “cost” between
nodes
i
and
j
. Now, we must bear in mind that this cost depends on whether
