Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/18403
Title: A decomposition approach for the p-median problem on disconnected graphs
Author: Agra, Agostinho
Cerdeira, Jorge Orestes
Requejo, Cristina
Keywords: Location
Optimal diversity management problem
Decomposition
Issue Date: Oct-2017
Publisher: Elsevier
Abstract: 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.
Peer review: yes
URI: http://hdl.handle.net/10773/18403
DOI: 10.1016/j.cor.2017.05.006
ISSN: 0305-0548
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
AgraCerdeiraRequejo-COR2017.pdfMain article364.86 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.