Geoscience Reference
In-Depth Information
quite fast, can produce pretty good solutions for some types of instances, in
general, they tend to have a rather poor behavior, and most authors moved fast to
other types of heuristics.
Clustering-based methods
partition the set of customers into clusters and then
they either locate a depot for each cluster and solve a vehicle routing problem
afterwards, or solve an auxiliary traveling salesman problem for each cluster
before locating the depots. Barreto et al. (
2007
) present a method of this type and
also analyze different clustering criteria in this context. A more recent example
of this type of method is the constructive procedure considered in the two-phase
method of Willmer Escobar et al. (
2013
) for the capacitated LRP. With their
algorithm, the authors have provided the currently best known solutions for many
of the existing benchmark instances (with up to 200 customers and 20 facilities)
but at a high computational cost since some instances required more than 10 min
of CPU time.
Iterative methods
can be seen as an evolution of sequential methods, where
several iterations of a sequential method are performed, and the information
obtained at each iteration is used to guide the methods used for choosing the
locations and designing the vehicle routes built at the next one. The algorithm
proposed in Prins et al. (
2007
) falls in this category. Using their algorithm, the
authors could find very good solutions (proven to be optimal in several cases) for
instances with up to 200 customers and 20 facilities, and the CPU time exceeded
1 min in only a reduced subset of the considered instances.
In
hierarchical methods
the problem is considered in a more integrated way,
without splitting its components. However, the two decisions are not considered
to be equally important; facilities location is regarded as the main problem
decision and vehicle routes design as a secondary one. Many contributions fit
in this category (Albareda-Sambola et al.
2005
;TingandChen
2013
), especially
the most recent ones, since they tend to yield better results. Indeed, the results
obtained in Ting and Chen (
2013
) are comparable with those of Willmer Escobar
et al. (
2013
), although solutions are slightly worse in general terms, this is
compensated by somehow smaller CPU times.
Finally, one can also find in the literature one approximation algorithm for the
LRP in Harks et al. (
2013
). The proposed algorithm builds a solution by combining
the solutions to two auxiliary problems: and uncapacitated facility location problem,
and a minimum spanning tree. For this algorithm, they prove an approximation
factor of 4:38.
