P-median is one of the main problems of the Location-Allocation kind. This problem determines the location of facilities and assigns demand points to each of them. The p-median problem can be established as a discrete problem in graph terms as: Let G = *(V, E)* be an undirected graph where *V* is the set of *n* vertices and *E* is the set of edges with an associated weight that can be the distance between the vertices *d**ij** *=* d*(*v**i*, *v**j*) for every *i, j* =1,..., *n* in accordance to the determined metric. With the distances a symmetric matrix is formed, finding * *such that *|V**p**|* = *p*, where *p* can be either variable or fixed, and the sum of the shortest distances from the vertices in {*V-V**p*} to their closet vertex in *Vp* is reduced to the minimum. Expressed in this way the P-median problem is a combinatory optimization problem that belongs to the NP-hard class, where the approximation methods have been of great aid in recent years.

Test instances for p-median are found in the website:

- OR-Library (http://people.brunel.ac.uk/~mastjjb/jeb/info.html)

In this point, we have tested for the OR-Library matrices three algorithms that have given good results for geographical data (Simulated Annealing, Variable Neighborhood Search and a Bioinspired Variable Neighborhood Search). However, the partitioning method PAM (Partitioning Around Medoids), that is modeled like the P-median, attained better results than the mentioned metaheuristics, in a favorable computing time.

In this work we expose the behavior of four different algorithms for the test matrices from OR-Library. An analysis has been made with the goal to explain the quality of the results obtained, to conclude that PAM behaves with efficiency for such test matrices.

- Presentation