Open    Access



The P-Median Problem: A Tabu Search Approximation Proposal Applied to Districts



Author(s)

María Beatriz Bernábe Loranca, Rogelio González Velázquez and Martín Estrada Analco

Full-Text PDF XML     2980 Views

DOI:10.17265/2159-5291/2015.03.002

Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Puebla, México

P-median is one of the most important Location-Allocation problems. This problem determines the location of facilities and assigns demand points to 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 V_pÍ V such that |V_p| _QUOTE ⊆⊆ = 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 V_p is reduced to the minimum. Under these conditions the P-median problem is a combinatory optimization problem that belongs to the NP-hard class and the approximation methods have been of great aid in recent years because of this. In this point, we have chosen data from OR-Library [1] and we have tested three algorithms that have given good results for geographical data (Simulated Annealing, Variable Neighborhood Search, Bioinspired Variable Neighborhood Search and a Tabu Search-VNS Hybrid (TS-VNS). However, the partitioning method PAM (Partitioning Around Medoids), that is modeled like the P-median, attained similar results along with TS-VNS but better results than the other metaheuristics for the OR-Library instances, in a favorable computing time, however for bigger instances that represent real states in Mexico, TS-VNS has surpassed PAM in time and quality in all instances. In this work we expose the behavior of these five different algorithms for the test matrices from OR-Library and real geographical data from Mexico. Furthermore, we made an analysis with the goal of explaining the quality of the results obtained to conclude that PAM behaves with efficiency for the OR-Library instances but is overcome by the hybrid when applied to real instances. On the other hand we have tested the 2 best algorithms (PAM and TS-VNS) with geographic data geographic from Jalisco, Queretaro and Nuevo León. In this point, as we said before, their performance was different than the OR-Library tests. The algorithm that attains the best results is TS-VNS.

Metaheuristcs, P-mediana, PAM, Tabu search