Parallelization of the scatter search for the p-median problem

This article develops several strategies for the parallelization of the metaheuristic called scatter search, which is a population-based method that constructs solutions by combining others. Three types of parallelization have been proposed to achieve either an increase of efficiency or an increase of exploration. The procedures have been coded in C using OpenMP and compared in a shared memory machine with large instances. The obtained algorithms are tested on the p-median problem.