Geoscience Reference
In-Depth Information
X
X
.
w
j
C
w
s
/a
jsr
r
C
X
j2J
2
w
j
z
ij
2q
i
y
i
i
2
I
r2
i
fj;sg2E
(15.24)
y
i
2f
0;1
g
i
2
I
(15.25)
z
ij
2f
0;1
g
f
i;j
g2
E
(15.26)
r
2f
0;1
g
r
2
:
(15.27)
Here, constraints (
15.23
) ensure that each customer is either visited once by one
of the selected routes, or in a round trip from a facility. Facility capacities are stated
by constraints (
15.24
). For ease of notation, in these constraints, an artificial demand
w
i
D
0 is defined for each facility i.
Of course, in order to take advantage of this formulation it is essential to use a
method based on column generation since the number of variables is exponential.
Therefore, a crucial issue when developing exact solution methods based upon this
formulation is the pricing problem. Here, the pricing problem consists of finding
negative cost vehicle routes in . It belongs to the family of resource constrained
shortest path problems, which have been the focus of an abundant literature, mostly
because they appear as pricing problems in many column generation algorithms
where vehicle routes are involved (see, for instance, Desrochers et al.
1992
; Feillet
et al.
2007
; Righini and Salani
2008
).
In Contardo et al. (
2014a
), which has been the most successful work so far, the
authors allow for solutions that contain cycles, as long as they contain at least
three nodes. For this case, to guarantee that even if contains non-elementary
routes, these routes will not be part of a solution of LRP3, the authors replace
the degree constraints (
15.23
) by their following stronger variant, the strengthened
degree constraints:
X
X
a
jkr
r
C
X
i2I
z
ij
1j
2
J:
(15.28)
r2
kWfj;kg2E
On top of the efficiency of the algorithm used in the pricing problem, most
set partitioning based exact algorithms for the LRP also rely on the addition of
valid inequalities to tighten the bounds obtained during the branching process. In
particular, Baldacci et al. (
2011
) proved that all valid inequalities developed for
flow formulations can be transformed into valid inequalities for the set partitioning
formulation presented above, since, thanks to the distinction between routes visiting
one or more customers made in the variables definition, the following equalities
hold:
z
ij
D
X
r2
a
ijr
r
8f
i;j
g2
E:
(15.29)
