Geoscience Reference
In-Depth Information
random initial solution is selected and then refined using a set of predefined rules
based on the concept of -optimal cover. This procedure is repeated many times with
the hope of finding a good solution. Chvátal (
1979
) proposes a basic greedy heuristic
that selects iteratively the facility with the largest number of nodes covered per unit
cost. A bound is established for the worst value of the solution provided by the
heuristic. Feo and Resende (
1989
) develop a probabilistic heuristic for set covering
problems arising in Steiner triple systems. It is a non-deterministic variation of a
previous deterministic heuristic where randomization is introduced to escape from
local minima.
Many more different metaheuristic techniques have been used to approach SCP:
surrogate relaxation (Lorena and Lopes
1994
), simulated annealing (Jacobs and
Brusco
1995
;Bruscoetal.
1999
), genetic algorithms (Al-Sultan et al.
1996
; Beasley
and Chu
1996
). However, as with the exact case, subgradient methods are the most
effective. Ceria et al. (
1998
) use a primal-dual subgradient Lagrangian algorithm to
provide information for a later greedy heuristic to decide which variables to fix to
one. Caprara et al. (
1999
) use variable pricing to update the subset of columns that
define a core problem in their subgradient optimization heuristic. This is a difference
with respect to Ceria et al. (
1998
) where the core set is not modified. They also
improve the way in which the step-size and ascent direction definitions are usually
done in subgradient optimization in order to speed up convergence.
For the Maximal Covering Location Problem and similar problems, we can find
several heuristics. Already in Church and ReVelle (
1974
) where the problem is
introduced, a greedy heuristic is provided. Later, Daskin (
1983
) describes a heuristic
for the Maximum Expected Covering Location Problem which finds good solutions
for all values of q (the probability of a facility not working). It starts with all the
facilities located at the node that covers the maximum demand and then considers
single node substitutions. For each of the new solutions, it is analyzed if there is
an interval where the current best solution is improved. By iterating this procedure,
interval [0,1] is partitioned and a heuristic solution is given for each of the resulting
subintervals. In MCLP, Galvão and ReVelle (
1996
) develop a Lagrangian heuristic
that uses a vertex interchange heuristic to improve upper bounds. In Galvão et al.
(
2000
), heuristics based on Lagrangian and surrogate relaxations are compared.
Here, the relaxed surrogate problem is a binary knapsack problem whose linear
relaxation is solved in the heuristic. The authors show that, when the initial set of
multipliers is obtained using a dual descent procedure, the performance of the two
methods is similar.
Eaton et al. (
1986
) deal with a hierarchical covering problem where sites with
multiple cover are maximized while the number of vehicles is minimized in an
application to ambulance deployment in Santo Domingo. Although they proposed
two formulations, no solver was available at that moment in the Ministry of Health
of Dominican Republic and they then developed a heuristic that minimizes the
number of facilities, maximizes multiple coverage and minimizes response time.
In their algorithm, they create a cover matrix, then order coverage zones in a list and
remove dominated sites iteratively.
