The p-Median Problem - Location Science - page 28

2.5.2 Metaheuristics for the p-Median Problem

The myopic algorithm is a construction algorithm. The neighborhood and exchange
algorithms are improvement algorithms. A large variety of metaheuristic algorithms
have been devised to find solutions to the p -median problem. Mladenovi´cetal.
( 2007 ) provide a relatively recent review of these techniques. Below we highlight a
few of the classic papers and approaches in this field.
Chiyoshi and Galvão ( 2000 ) present a statistical analysis of a simulated annealing
algorithm (Kirkpatrick 1984 )forthe p -median model. They employed the 40-
instance dataset proposed by Beasley ( 1990 ). The dataset includes instances ranging
from 100 to 900 demand locations. They found that in 100 runs of a simulated
annealing algorithm for each instance, the best solution found was the optimal
solution in 26 of the 40 instances. The maximum deviation from optimality for
the best of the 100 runs for the 40 instances was 1.62 %. Al-khedhairi ( 2008 )
also employed simulated annealing for the Beasley dataset and found the optimal
solution in 33 of the cases. However, the maximum deviation was over 18 % for
the seven instances for which the simulated annealing algorithm failed to find
the optimal solution. Murray and Church ( 1996 ) also discuss the application of
simulated annealing to the p -median problem as well as to the maximal covering
problem.
Alp et al. ( 2003 ) propose an effective genetic algorithm (Goldberg 1989 ; Haupt
and Haupt 1998 ; Holland 1975 ; Michalewicz 1994 ; Mitchell 1998 )forthe p -median
problem. For the 40-instance Beasley dataset, they ran their algorithm 10 times for
each instance. They found the optimal solution at least once in 28 of the 40 cases. In
six of the cases, the genetic algorithm always identified the optimal solution. In the
12 cases in which the genetic algorithm failed to find the optimal solution, the best
of the ten runs resulted in objective functions that deviated from the optimal value
by 0.02-0.4 %.
Rolland et al. ( 1996 ) applied tabu search (Glover 1990 ; Glover and Laguna 1997 )
to the p -median problem. They tested their algorithm using randomly generated
datasets ranging in size from 13 to 500 nodes. For instances with 100 nodes or
fewer, the results were compared to two-exchange heuristics as well as to the optimal
solution found using an integer programming algorithm. For the larger instances,
optimal solutions were not obtained and the three heuristics were compared with
each other. In all cases, the tabu search algorithm outperformed the other two
heuristics. For the smaller instances (100 nodes or fewer) the tabu search algorithm
averaged 0.5 % from optimality with a maximum deviation of 6 %. Tabu search
found the optimal solution in 66 % of the smaller test cases. For the 12 larger test
cases, tabu search found the best solution in all but one case.
If an improvement (e.g., the neighborhood search or exchange algorithm outlined
above) is started with many different randomly generated solutions, the p facilities
that are selected are often similar across the various solutions. In other words, some
sites are selected in many of the runs and many other candidate sites are never
selected. Using this observation, Rosing and ReVelle ( 1997 ) developed a heuristic