Geoscience Reference
In-Depth Information
facilities. Connectivity constraints (
15.5
) ensure that each vehicle route includes a
facility, while flow conservation constraints (
15.6
) ensure that
z
variables do indeed
define routes, and constraints (
15.7
) mean that these routes visit one single facility.
Finally, constraints (
15.8
)forcethex and
z
variables to take consistent values.
Formulations of this type tend to be rather large, on the one hand, because
they have an exponential number of connectivity constraints and, on the other
hand, because they have O.
j
V
j
3
/ variables. Connectivity constraints, as well as
additional valid inequalities, have traditionally been dealt with by using cutting
plane procedures, such as branch-and-cut. However, even after relaxing connectivity
constraints, the size of the formulations remains too large for solving realistic size
instances.
As an alternative, several authors have worked on formulations where vehicle
flow variables
z
do not include the third index to identify which vehicle uses each
arc. In fact, early works addressing the particular cases of the LRP with one single
depot or one single route per depot, such as Laporte and Nobert (
1981
) or Laporte
et al. (
1983
) already used this type of approach.
A very successful example of this type of formulations is presented in Belenguer
et al. (
2011
). In this case, the authors propose an undirected formulation that uses
the following variables:
For each i
2
I, y
i
indicates whether a facility is established at i.
For each edge
f
i;j
g2
E,
z
ij
indicates whether edge
f
i;j
g
is used exactly once
in the solution.
For each edge
f
i;j
g2
E
IJ
,
z
ij
indicates whether edge
f
i;j
g
is used twice in the
solution.
Note that, as mentioned above, it can be assumed that the only edges that can be
traversed twice in an optimal solution belong to E
IJ
and, therefore, variables
z
2
are
only defined for those edges.
Additionally to the above variables, the following notation is used. For each set
of customers S
J, .S/ is a lower bound on the minimum number of vehicles
needed to serve the aggregate demand of all customers in set S. The most commonly
used bound in this type of formulations is
2
3
Q
X
j2S
1
6
7
1
.S/
D
w
j
:
However, instead of
1
.S/ some authors have used the optimal value of the bin
packing problem defined by the weights of the customers in S, and bin size equal
to the vehicle capacity, Q. In what follows, this second bound will be referred to as
2
.S/.
