Information Technology Reference
In-Depth Information
q σ ( k ) kp = g σ ( k ) kp
k
K,p
P
(35)
w kt ,y ikh ,z k ∈{
0 , 1
}
i
V,t
T,k
K,h
H
(36)
x ijk ∈{
0 , 1
}
( i,j )
E,k
K
(37)
v type
k
∈{−
1 , 0 , 1
}
k
K
(38)
v top
k
,v bel
k
,g ikp ,g ikp ,q ikp
Z +
i
V,k
K,p
P
(39)
l k ,u k ,s ik ,c ik
0
i
V,k
K
(40)
Here M L , M T ,and M C are large enough big- M constants to make the corre-
sponding constraints redundant. The objective is to minimize the sum of vehicle
routing cost and vehicle usage cost (1). Constraints (2) limit the number of trail-
ers that may be assigned to a vehicle. Constraints (3) ensure that a single trailer
can be assigned to at most one vehicle. Constraints (4) are used to identify the
type of vehicle configuration. Constraints (5)-(6) set the vehicle time windows.
Constraints (7) and (8) set the vehicle capacity on top and bottom compart-
ments, respectively. Constraints (9) and (10) set the relationship between the
z k and the x ijk and w kt variables, respectively. Flow balance is assured by (11).
Constraints (12) ensure that a vehicle may visit a node at most once. Constraints
(13)-(14) and (15)-(16) guarantee the time windows for both customers and vehi-
cles, respectively. Constraints (17)-(19) set the correct relationship between the
binary time index variables y ijk and the time variables s ik and OT k . The dock
capacity constraints are given by (20). Constraints (21) and (22) are used to en-
sure that the time variables are consistent with travel and service times. Product
availability and demand are set by (23) and (24), respectively. Constraints (25)
and (26) ensure that a vehicle can load or unload product at node i only if it
visits that node. Constraints (27)-(28) establish the connection on vehicle load
between nodes i and j when vehicle k indeed travels directly from i to j . Vehicle
capacity is set by (29) and (30), the latter considering that type N products can
be placed in the bottom compartment of any vehicle or in the top compartment
of vehicles with a shelf. Constraints (31)-(32) ensure the consistency of the cost
variables. Conditions (33) make it impossible to assign trailers to vehicles in
different starting locations. Constraints (34) and (35) establish initial delivery
and pickup conditions for a vehicle at the start of its route. The nature of the
decision variables are set in (36)-(40).
The problem is NP-hard [2]. The largest instance we could solve exactly after
several hours of computing time by CPLEX branch-and-bound algorithm was in
the order of 6 nodes, 7 trailers, and 5 products. Given real-world instances are
significantly larger, we develop a heuristic framework for this problem.
3 Proposed Heuristic
GRASP [5] is a multi-start metaheuristic that has been widely used for finding
good quality solutions to many hard combinatorial optimization problems. It
relies on greedy randomized constructions and local search.
 
Search WWH ::




Custom Search