Geoscience Reference
In-Depth Information
The formulation proposed in Belenguer et al. (
2011
)is
.LRP2/ minimize
X
i2I
f
i
y
i
C
X
fi;jg2E
`
ij
z
ij
C
X
fi;jg2E
IJ
2`
ij
z
ij
(15.12)
subject to
X
i2I
2
z
ij
C
X
i2V nfjg
z
ij
D
2
(15.13)
j
2
J
z
ij
C
z
ij
y
i
(15.14)
i
2
I;j
2
J
X
z
ij
j
S
j
.S/
S
J
(15.15)
i;j2S
X
X
z
sj
C
X
t2Infig
X
.
z
ts
C
2
z
ts
/
2i
2
I;S
J
I
w
.S/ > q
i
s2S
s2S
j2JnS
(15.16)
z
jt
C
X
s2S
.
z
sj
C
z
st
/
C
X
s;
u
2S
z
s
u
C
X
i2I
0
z
ij
C
X
i2InI
0
z
it
j
S
jC
2
S
J;I
0
I
I
j;t
2
J
n
S
(15.17)
X
.
z
ij
C
z
ij
/
1
(15.18)
j
2
J
i2I
(15.19)
y
i
2f
0;1
g
i
2
I
z
ij
2f
0;1
g
(15.20)
f
i;j
g2
E
z
ij
2f
0;1
g
(15.21)
f
i;j
g2
E
IJ
:
The original formulation includes an extra term in the objective function to
account for fixed costs for the use of vehicles. Although this term has not been
included here, these costs can be easily included in the above formulation by
suitably modifying the lengths `
ij
for each
f
i;j
g2
E
IJ
.
In this formulation, constraints (
15.13
) are the degree constraints, which force
each customer to be visited by some route. Constraints (
15.14
) are imposed in order
to ensure that no route is rooted at a closed facility. Constraints (
15.15
)playtwo
major roles. On the one hand, they forbid solutions with subtours which are not
linked to any facility. On the other hand, they ensure that the vehicle capacities are
not exceeded. Note that only
z
1
variables are involved in these constraints since
each
z
2
variable is associated with one complete facility-customer-facility tour,
which will not violate the vehicle capacity constraints in any feasible LRP instance.
Facility capacities are imposed through constraints (
15.16
): if a set of customers
S cannot be fully served from a given facility i because of its capacity, then at
least one customer in S must be visited by a vehicle route rooted at a different
facility and, therefore, at least two edges must be used that link set S with customers
