Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/18403
Título: | A decomposition approach for the p-median problem on disconnected graphs |
Autor: | Agra, Agostinho Cerdeira, Jorge Orestes Requejo, Cristina |
Palavras-chave: | Location Optimal diversity management problem Decomposition |
Data: | Out-2017 |
Editora: | Elsevier |
Resumo: | 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 |
Aparece nas coleções: | CIDMA - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
AgraCerdeiraRequejo-COR2017.pdf | Main article | 364.86 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.