Information Technology Reference
In-Depth Information
single or double vehicles are used which is unknown at this point. However, we
can construct a cost function as a convex combination of the optimal costs for
single and double vehicles parameterized by a weight
β
∈
[0
,
1]. The output, for
a fixed value of
β
is a set of requests
R
.
Let
y
ij
a binary-decision variable equal to 1 if at least one request from
i
to
j
exists and 0 otherwise. Then, the transportation problem TP(
β
) given below is
solved in Step 5 of Procedure 1. Here,
M
=max
i∈V,p∈P
{
n
ip
}
is a large enough
constant to make the constraint (44) redundant when
y
ij
= 1. The problem is
not quite a classical transportation problem. Here we have a fixed cost rather
than a variable cost. Also, we have several capacity/demand constraints for the
different products. However, time is not an issue since this problem is easy to
solve even for large instances. Note that different values of
β
give rise to different
cost structure among nodes, and therefore, we proceed to generate different TPs
for a variety of values of
β
. As can be seen in Procedure 1 we use a step size
Δβ
that allows us to discretize the range for
β
and try out different matrices and
have therefore more diversity.
Model TP(β)
βc
[
ij
]
+(1
β
)
c
[
ij
]
y
ij
f
(
r, y
)=
i,j∈V
Minimize
−
(41)
subject to
j∈V
n
ip
r
ijp
≤
i
∈
V,p
∈
P
(42)
n
jp
r
ijp
≥
j
∈
V,p
∈
P
(43)
i∈V
r
ijp
≤
My
ij
i,j
∈
V
(44)
p∈P
r
ijp
≥
0
i,j
∈
V,p
∈
P
(45)
V
(46)
Construction phase:
Given a set of requests
R
, this phase is where these requests
are assigned to vehicles, and, as a consequence, where routes are determined for
these vehicles. The construction procedure is depicted in Procedure 2.
The procedure starts by initializing the set of vehicle routes
X
π
=
y
ij
∈{
0
,
1
}
i,j
∈
}
as the empty set (Step 1) and by assigning each trailer
t ∈ T
to a vehicle
k ∈ K
σ
(
t
)
(Step 2), that is, initally we have single vehicles. In a later stage
we consider merging two single vehicles into one double vehicle. Then a set
R
containing all possible point-to-point pairs that need to be served and a
set
P
containing all feasible routes are formed. Here, the latter is defined as
P
=
{
π
k
|
k
∈
K
R
∧
, where the term feasibility
means that vehicle
k
can deliver the products from node
i
to
j
within the vehicle
and node time windows. Let
P
k
be the set of all feasible routes associated with
vehicle
k
. Then, the actual route construction takes place within the
while
loop
(Steps 5-11). Following the GRASP philosophy, a greedy function that measures
the cost of assigning pair (
i,j
) to vehicle
k
is computed as follows:
{
(
i,j,k
):(
i,j
)
∈
(
i,j,k
) is a feasible route
}
