Location-Routing and Location-Arc Routing - Location Science - page 392

Additionally to this equivalence, when adapting valid inequalities originally
stated for flow formulations to set-partitioning formulations, some authors have used
the following result, first established in Laporte et al. ( 1985 ) in the context of vehicle
routing problems. Many of the valid inequalities derived for two-index formulations
for vehicle routing problems are concerned with a combination of connectivity and
capacity issues. In these cases, arguments of the type “at least vehicles are needed
to satisfy the demand of all customers in S J” result in constraints of the form
“the border of S is crossed, at least, 2 times”, that is, the sum of flows on edges
with a single endpoint in S must be at least 2. In these constraints, the number of
routes visiting S is overestimated using the flow in the cut-set of S, since there is
no way to compute the exact number of routes that visit S using the flow variables.
When equivalence ( 15.29 ) is used to derive valid inequalities for LRP3 from these
valid inequalities, the coefficient of each r variable for a given set S is the number
of times route r traverses the border of S. Bearing in mind the rationale behind
the constraints, one can see that, actually, these coefficients can be changed to take
value 2 if route r visits at least one customer in S,and0 otherwise. In general, this
results in stronger valid inequalities.

15.3.3 Valid Inequalities

It is impractical to list all the valid inequalities that have been more or less
successfully used for LRPs. Actually, most of the valid inequalities that have been
developed for vehicle routing problems have been adapted later for the case of LRPs
and in many cases, families of inequalities have been gradually strengthened or
extended. In what follows, we present a selection of the most recent families. For
more detailed information on these cuts and their evolution, the reader is referred
to Belenguer et al. ( 2011 ) and Contardo et al. ( 2013 ) for flow formulations, and to
Baldacci et al. ( 2011 ) and Contardo et al. ( 2014a ) for set partitioning formulations.

15.3.3.1 y-Strengthened Capacity Cuts (y-SCC)

For S J, and a route r 2 , let the binary parameter rS take value 1 if route r
visits at least one customer in S,and0 otherwise. Given S 0 S such that 1 .S 0 / D
1 .S/, the following inequalities are valid:
X

rS r C X
i2I

X

z ij 1 .S/:

r2

j2SnS 0

This family of constraints is a strengthening proposed in Contardo et al. ( 2014a )
of the previous y-Capacity Cuts derived in Belenguer et al. ( 2011 ).