p-Center Problems - Location Science - page 83

et al. ( 2004 ). The algorithm developed by Calik and Tansel ( 2013 ) solves their
formulations for restricted sets of radius values iteratively to converge to an optimal
solution. They proposed several selection strategies for a two-element specialization
of their algorithm. They also utilize the matrix reduction rules known for the set
covering problem in their restricted formulations when solving large problems.
In the recent studies, instances from the OR-Library (Beasley 1990 ) and TSPLIB
(Reinelt 1991 ) have been used for making computational experiments. The data
for the uncapacitated p-median problem found in the OR-Library consists of 40
instances with n D 100 900 and p D 5 .n=3/. This data was used in
the experiments conducted by Ilhan and Pınar ( 2001 ), Elloumi et al. ( 2004 ), and
Calik and Tansel ( 2013 ). In addition to these instances, Elloumi et al. ( 2004 )used
the instances u1060, rl1323 and u1817 (n D 1060;1323, and 1817, respectively)
and Calik and Tansel ( 2013 ) used the instances u1817, d15112, and pcb3038
(n D 1817;2500, and 3038, respectively) from the TSPLIB.

4.4 Heuristics

Mladenovi´cetal.( 2003 ) introduced the first meta-heuristic approaches for finding
approximate solutions to the p-center problem. They proposed a multistart local
search algorithm (M-I), a chain substitution Tabu Search (TS) algorithm, and a vari-
able neighborhood search (VNS) algorithm and conducted large scale experiments
on 40 p-median instances from the OR-Library and instances with up to 3,038
nodes from TSPLIB. These experiments reveal that their algorithms outperform the
algorithm proposed by Hochbaum and Shmoys ( 1985 ). Among the three heuristics
proposed, TS and VNS algorithms outperform M-I algorithm, VNS performs the
best on the average in terms of both the solution quality and solution time; however,
TS provides slightly better results for the instances with smaller p values.
Pullan ( 2008 ) proposed a memetic genetic algorithm (PBS) for the vertex-
restricted p-center problem, which combines a population based meta-heuristic
with a local search algorithm. By using the phenotype crossover and directed
mutation tools of the genetic algorithm, a wide range of elite starting solutions
are generated and then, these solutions are improved to local optimality by using
a local search algorithm. From the computational experiments using the instances
previously tackled by Mladenovi´cetal.( 2003 ), an improvement in the CPU times
and in the objective value of some problems is observed when PBS is compared with
the VNS algorithm. The PBS algorithm can be executed also in a parallel processing
mode. The experiments conducted by increasing the number of parallel processors
utilized in the algorithm provide better CPU times.
Salhi and Al-Khedhairi ( 2010 ) obtained tight lower and upper bounds by using a
three-level meta-heuristic and integrated these bounds with the algorithm by Daskin
( 2013 ) to solve the vertex-restricted p-center problem. In the first and second
levels of the algorithm, a variable neighborhood strategy is utilized with distinct
neighborhood structures. In the third level, a perturbation mechanism is introduced