Geoscience Reference
In-Depth Information
outside it, or to some facility different from i. Additionally, since individual routes
are not identified using 2-index variables, it is necessary to explicitly forbid tours
connecting two different facilities. This is done by means of the so-called path
elimination constraints (
15.17
). Additional constraints (
15.18
) are needed to forbid
paths connecting two facilities through one single customer. The path elimination
constraints are similar to the chain-barring constraints introduced by Laporte et al.
(
1988
).
Using this formulation enriched with some families of valid inequalities,
Belenguer et al. (
2011
) were able to solve within less than 2 h instances of up
to 50 customers and five potential facilities.
15.3.2
Set-Partitioning Formulations
Set partitioning formulations for the LRP were introduced much later than flow
formulations. Indeed, papers addressing this type of formulations have appeared
relatively recently, in parallel with similar formulations for vehicle routing prob-
lems. The first such formulation was presented in Berger et al. (
2007
); the slightly
different formulation presented in Akca et al. (
2009
) was later used in Baldacci et al.
(
2011
) and further strengthened by Contardo et al. (
2014a
).
In order to present this type of formulations, some extra notation is required.
Variables now correspond to the possible vehicle routes that are feasible with respect
to the vehicle capacity and serve more than one customer. These routes will be
indexed in
D[
i2I
i
,where
i
gathers the routes starting from facility i.The
return trips from a facility to a single customer will be dealt with separately. For
each route r
2
, we will denote by `
r
the total length of the route, by
w
r
its total
demand and, for each edge
f
i;j
g2
E, the coefficient a
ijr
will denote the number of
times edge
f
i;j
g
is used in route r. Note that coefficients a
ijr
are binary if route r is
elementary, but can take larger values if non-elementary routes are allowed.
The formulation exploited by Contardo et al. (
2014a
) uses the following binary
variables:
For each i
2
I, y
i
indicates whether a facility is established at i.
For each i
2
I and j
2
J,
z
ij
indicates whether a return trip from facility i to
customer j is part of the solution.
For each route r
2
,
r
indicates whether route r is used.
.LRP3/ minimize
X
i2I
f
i
y
i
C
X
r2
`
r
r
C
X
fi;jg2E
IJ
2`
ij
z
ij
(15.22)
subject to
X
r2
X
a
ijr
r
C
X
i2I
2
z
ij
D
2
j
2
J
i2V
(15.23)
