TY - JOUR

T1 - A decomposition approach for the p-median problem on disconnected graphs

AU - Agra, Agostinho

AU - Cerdeira, Jorge Orestes

AU - Requejo, Cristina

N1 - Sem PDF.
Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) (UID/MAT/04106/2013; UID/MAT/00297/2013)

PY - 2017/10

Y1 - 2017/10

N2 - The p-median problem seeks for the location of p facilities on the vertices (customers) of a graph to minimize the sum of transportation costs for satisfying the demands of the customers from the facilities. In many real applications of the p-median problem the underlying graph is disconnected. That is the case of p-median problem defined over split administrative regions or regions geographically apart (e.g. archipelagos), and the case of problems coming from industry such as the optimal diversity management problem. In such cases the problem can be decomposed into smaller p-median problems which are solved in each component k for different feasible values of pk, and the global solution is obtained by finding the best combination of pk medians. This approach has the advantage that it permits to solve larger instances since only the sizes of the connected components are important and not the size of the whole graph. However, since the optimal number of facilities to select from each component is not known, it is necessary to solve p-median problems for every feasible number of facilities on each component. In this paper we give a decomposition algorithm that uses a procedure to reduce the number of subproblems to solve. Computational tests on real instances of the optimal diversity management problem and on simulated instances are reported showing that the reduction of subproblems is significant, and that optimal solutions were found within reasonable time.

AB - The p-median problem seeks for the location of p facilities on the vertices (customers) of a graph to minimize the sum of transportation costs for satisfying the demands of the customers from the facilities. In many real applications of the p-median problem the underlying graph is disconnected. That is the case of p-median problem defined over split administrative regions or regions geographically apart (e.g. archipelagos), and the case of problems coming from industry such as the optimal diversity management problem. In such cases the problem can be decomposed into smaller p-median problems which are solved in each component k for different feasible values of pk, and the global solution is obtained by finding the best combination of pk medians. This approach has the advantage that it permits to solve larger instances since only the sizes of the connected components are important and not the size of the whole graph. However, since the optimal number of facilities to select from each component is not known, it is necessary to solve p-median problems for every feasible number of facilities on each component. In this paper we give a decomposition algorithm that uses a procedure to reduce the number of subproblems to solve. Computational tests on real instances of the optimal diversity management problem and on simulated instances are reported showing that the reduction of subproblems is significant, and that optimal solutions were found within reasonable time.

KW - Decomposition

KW - Location

KW - Optimal diversity management problem

UR - http://www.scopus.com/inward/record.url?scp=85019182283&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2017.05.006

DO - 10.1016/j.cor.2017.05.006

M3 - Article

AN - SCOPUS:85019182283

VL - 86

SP - 79

EP - 85

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -