ILS METAHEURISTICS APPLIED TO THE P-MEDIAN PROBLEM

This work proposes an algorithm based on the Iterated Local Search (ILS) metaheuristic to solve the capacitated p-median problem. The construction of the initial solution is based on the constructive phase of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic. Computational experiments were carried out using 35 instances from the literature. The results, obtained in 30 executions of the heuristic, show average gaps lower than 0.60\% for the best values of the objective function, in all instances, compared with the values obtained by the solver CPLEX and by \citet{Stefanello}, and average values for the objective function with an average gap lower than 2.00\%. Furthermore, compared to the results of \citet{Vasconcelos}, a negative average gap was obtained for the best objective function values, and lower average execution times in approximately 50\% of the instances.