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 dij = d(vi, vj) for every i, j =1,..., n in accordance to the determined metric. With the distances a symmetric matrix is formed, finding such that |Vp| = p, where p can be either variable or fixed, and the sum of the shortest distances from the vertices in {V-Vp} 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