The P-median problem: A computational experience

B. Bernábe 1, R. González 2, M. Estrada,3

1, 2, 3 Facultad de Ciencias de la Computación, benemérita Universidad Autónoma de Puebla, Puebla, México

beatriz.bernabe@gmail.com

Abstract: 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 a facility. 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 that the sum of the shortest distances from the vertices in {V-Vp} to their closet vertex in Vp is reduced to the minimum. Said in this way the P-median problem is a combinatory optimization problem that belongs to the NP-hard class, tested 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 Bioinspired in Variable Neighborhood). 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 of explaining the quality of the results obtained to conclude that PAM behaves with efficiency for such test matrices.

The following work is organized as follows:

Introduction as section 1. Section 2 deals with presenting the general aspects of the P-median problem. In section 3 the employed metaheuristics are briefly explained to proceed with section 4, where PAM is exposed along with the computational experience.

Finally in section 5 conclusions and future remarks.

Keywords : Metaheuristcs. P-mediana, PAM

References

[1] E. Carrizosa, M. Marquez, M. Puerto (1998). The weber problem with regional demand, European Journal of Operational Research , 358-365.

[2] D. Pérez, J. Moreno (2004). Búsqueda por entornos variables:desarrollo y aplicaciones en locaclización. Murcia: Universidad de Murcia, 357-389.

[3] H. Jiang, X. Zhang, M. Li (2007). Backbone of the p-Median Problem. Lecture Notes in Computer Science, 699-704.

[4] L. Kaufman and P. J. Rousseeuw (1990). Finding groups in data: An introduction to cluster analysis, Wiley Interscience, 1990.

[5] L. Kaufman and P. Rousseeuw (1987). Clustering by Means of Medoids, Statistical Data Analysis Based on the L1 Norm and Related Methods, North-Holland, 1987, pp. 405-416.

[6] R. Martí (2003). Procedimientos Metaheurísticos en Optimización Combinatoria. Matematiques 1(1), 3-62.