Tuesday 28
Local search and decomposition
M. Basseur
› 9:20 - 9:40 (20min)
The P-median problem: A computational experience
María Beatriz Bernábe  1@  , Rogelio González, Martín Estrada@
1 : Computer Science Department - Benemérita Universidad Autónoma de Puebla  (FCC BUAP)  -  Website
14 Sur and San Claudio San Manuel, Ed. 104c-303c, 72570 Puebla, Pue -  Mexico

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
Online user: 1 RSS Feed