Geoscience Reference
In-Depth Information
15.3.3.2
Set Partitioning Effective Strengthened Facility Capacity
Inequalities (SP-ESFCI)
As mentioned above, the main difficulty when modeling vehicle routes is to ensure
the connectivity of the solutions, especially in capacitated problems. When loca-
tional decisions must also be made, ensuring connectivity and capacity satisfaction
entails an extra degree of complexity. Most of the known valid inequalities focus on
vehicle capacities and rarely take facility capacities into account. SP-ESFCI aim at
putting facility capacity constraints in relation with the locational variables.
To this end, we need to extend the definition of
1
to take into account a set of
facilities. Given a set of customers S
J and a set of facilities H
I,wedefine
1
.S;H/
D
max
n
0;
l
w
.S/
P
i2H
q
Q
mo
as a lower bound on the number of vehicle
routes rooted at facilities outside H, needed to serve all customers in S,evenifall
facilities in H provided their service to customers in S. Then, for S
0
S
J,and
i
2
H
I with
1
.S
n
S
0
;H/
D
1
.S;H/, the following inequality is valid:
X
z
ij
1
.S;H
nf
i
g
/
C
y
i
1
.S;H/
1
.S;H
nf
i
g
/
:
X
rS
r
C
X
i2InH
X
r2
i
j2SnS
0
i2InH
(15.30)
The main idea behind these constraints is similar to that of the y-SCC inequali-
ties, but now, the constraint takes two different shapes depending on whether facility
i is opened or not.
15.3.3.3
Strengthened Framed Capacity Inequalities (SFrCI)
Moving back to vehicle capacities, we find the following valid inequalities, which
have been successively improved since some early papers on vehicle routing.
Given a subset of customers S
J, partitioned into disjoint subsets
S
D
f
S
1
;:::;S
t
g
(S
D[
t
sD1
S
s
), we denote by
3
.S
j
/ the optimal value of the bin
packing problem defined as follows. For each set S
s
in
S
,wedefine
1
.S
s
/ items of
size Q, except for the last one, which will have a size equal to
w
.S/
.
1
.S/
1/Q,
and we define bin capacities equal to Q. Then, the SFrCI corresponding to frame
.S;
S
S
/ is:
t
t
X
X
X
X
rS
r
C
rS
s
r
3
.S
j
S
/
C
1
.S
s
/:
(15.31)
r2
sD1
r2
sD1
These inequalities generalize and reinforce the capacity inequalities, which
force that the number of routes that visit a given set of customers S is at least
1
.S/. Note that when no location decisions have to be made, in the presence
of degree constraints, capacity constraints are equivalent to subtour elimination
constraints (
15.15
). Indeed, when for a given set S
J,
S
only contains one set,
