Geoscience Reference
In-Depth Information
15.3
Formulations and Exact Algorithms
The available exact algorithms for solving LRPs rely on mathematical programming
formulations of the problem. Most of these formulations have been developed
around the existing formulations for discrete facility location problems and multi-
depot vehicle routing problems. Since the early formulations of Golden et al. (
1977
)
and of Perl and Daskin (
1985
), several LRP formulations have been studied. CLRPs
have received particular attention, since they are amongst the most basic LRPs. This
section will concentrate on these problems.
As mentioned above, the main difficulty when developing a formulation for an
LRP model is to guarantee that each route will start and end at one facility and
neither closed loops visiting only customers, nor paths connecting two different
facilities will be formed. For this reason, to a large extent, the developments
concerning formulations for LRP models are strongly related with the literature
on capacitated vehicle routing problems, especially, on multi-depots problems. As
happens in these problems, one can assume, without loss of generality, that an
optimal solution exists in which no edge of E
I
is used more than twice and the
only edges used twice, if any, belong to E
IJ
. This is actually the case of problem
instances in which the edge lengths satisfy the triangle inequality. Any instance
can in fact be easily transformed into an equivalent one satisfying this property, by
replacing the actual length of each edge with the length of a shortest path connecting
its endpoints.
Broadly speaking, the existing formulations for the LRP can be classified in
either of two families. On the one hand, one can find the so-called flow formulations,
where different sets of variables are used to determine the set of located facilities
and to describe the vehicle routes. On the other hand, one can find set covering
formulations, where one single variable is defined associated with each feasible
vehicle route. To a large extent, the appropriate solution method depends on the
formulation employed; while branch-and-cut approaches are the most suitable
for flow formulations, set covering formulations are in general better suited for
algorithms based on column generation. The most recently presented algorithms
combine column generation and cut generation methods.
15.3.1
Flow Formulations
Within the flow formulations, different models can be distinguished according to
two criteria: the number of indices of the variables used to define the vehicle routes
(including or not a third index to identify which vehicle uses a given link), and the
nature of these variables, known as commodity flow variables when they consider
the quantity of goods traveling on every link and as vehicle flow variables when they
only indicate whether it is used or not.
