In this paper we propose heuristic algorithms for the capacitated p-median problem. In the first one solutions are obtained with Scatter Search whereas the second algorithm uses Path Relinking. A third approach that combines Path Relinking with Scatter Search is also analyzed. The GRASP methodology is used to generate the initial Reference Set both for Scatter Search and Path Relinking. Computational experiments have been carried out with different data sets in order to evaluate the performance of the approaches. In general, Scatter Search outperforms Path Relinking, but the use of Path Relinking prior to Scatter Search has shown to enhance the performance of Scatter Search, specially in terms of the computation times required, due to the improvement of the initial Reference Set. The obtained results, that have been compared with previous approaches, show the efficiency of the methods both in terms of the quality of the solutions found and of the required computation times, even for very large instances.
