Geoscience Reference
In-Depth Information
z
-degree of S
s
is 2 or larger in all cases. In contrast, the evaluation of con-
straint (
15.32
)gives
6
C
.2
C
2
C
3
C
2/
2.4
C
1
C
1
C
1
C
1/;
which is clearly not satisfied. Here, note that in the computation of
3
.S
j
/, four
items were defined, with sizes 6;6;2 and 6, respectively, and the bin capacity was
set to 7.
The example of Fig.
15.3
also provides some insight in the way how the variable
definition in set partitioning formulations such as LRP3 forbids some fractional
solutions that are sometimes encountered when using flow formulations. Indeed,
the solution of the figure can be obtained in a relaxation of formulation LRP2, but it
is impossible to obtain it from formulation LRP3, since it cannot be decomposed as
the (fractional) combination of vehicle routes which are feasible with respect to the
vehicle capacity constraint.
S
15.4
Heuristic Algorithms
Many heuristics have been devised for different variants of LRPs. It is not the
goal of this chapter to enumerate and explore all these contributions. Instead, we
concentrate on the tools that have been most useful in those heuristics.
In the design of heuristics for LRPs it is very difficult to ignore the fact that
the problem combines decisions of two completely different natures: the location
of the facilities and the design of vehicle routes. Indeed, even solution methods
based on the use of neighborhoods tend to distinguish between the neighborhoods
that affect the set of facilities (add, drop or swap) and those that are typically
used in vehicle routing problems. A clear example of this fact is the variable
neighborhood search (VNS) heuristic recently proposed in Jarboui et al. (
2013
)for
an LRP with capacitated facilities and uncapacitated vehicles or the granular tabu
search heuristic presented in Willmer Escobar et al. (
2013
) for an LRP where both
vehicles and depots are capacitated. Possible exceptions are some algorithms based
on the construction of giant tours that encode both types of decisions, so that tour
modifications can alter both, facility locations and vehicle routes. Examples of this
type of algorithm are those of Yu et al. (
2010
) or Contardo et al. (
2014b
).
A commonly accepted classification for heuristic methods for LRPs, due to
Nagy and Salhi (
2007
), includes four categories, depending on how the interaction
between these decisions is taken into account in the design of heuristics.
Sequential methods
split the problem into its subproblems. First they solve the
location problem, using estimates of the routing costs that only take into account
the distances between customers and facilities and, they then solve the routing
problems defined at each opened facility with its assigned customers. Although
Srivastava and Benton (
1990
) show that this type of methods, that are typically
