Production
https://prod.org.br/article/doi/10.1590/S0103-65132006000200011
Production
Article

Uma heurística de localização-alocação (HLA) para problemas de localização de facilidades

A location-allocation heuristic (LAH) for facility location problems

Arakaki, Reinaldo Gen I.; Lorena, Luiz Antonio N.

Downloads: 0
Views: 329

Resumo

Neste trabalho, foi desenvolvida uma nova heurística de localização-alocação (HLA) para problemas de localização de facilidades (facility). Em tais problemas a questão central é localizar um objeto ou mais objetos, que são chamados de facilidades, e minimizar o custo de localizar estas facilidades. A HLA foi aplicada a dois problemas: o Problema de Localização de Máxima Cobertura (PLMC) e o Problema das P-Medianas Capacitado (PPMC) com o intuito de uma possível integração a Sistemas de Informações Geográficas (SIG). A HLA baseia-se na formação de agrupamentos (clusters) e na possibilidade de melhorá-los (em relação a algum objetivo). Uma bateria de problemas testes foi escolhida para validar a HLA. Bons resultados foram encontrados para o PLMC para instâncias (instance) pequenas e grandes, e para o PPMC em instâncias pequenas. Conclui-se que a HLA, sendo uma heurística de simples implementação, é rápida e bastante eficiente, portanto, indicada para ser integrada aos SIG.

Palavras-chave

Problema de localização de máxima cobertura, busca local, problema das p-medianas capacitado, heurística de localização-alocação

Abstract

This paper presents a new location-allocation heuristic (LAH) applied to facility location problems. Such approach is based on clustering and its main objective is to find out a facility (object) in a space by minimizing a function. The LAH developed throughout this work was employed in two problems: the Maximal Covering Location Problem (MCLP) and the Capacitated p-Median Problems (CPMP) with the purpose of a possible integration to Geographic Information Systems (GIS). A set of test problems (instances) was chosen to validate the LAH. Good computational results were obtained for small and large-scale MCLP instances and for small CPMP instances. These results demonstrate that LAH, being quick and fast, may be usefully applicable to GIS.

Keywords

Location-allocation heuristic, capacitated p-median problems, maximal covering location problem, local search

References



ASSAD, E. D.; SANO, E. E. Sistema de informações geográficas – aplicações na agricultura. Brasília: Embrapa-SPI/Embrapa-CPAC, 1998. 434 p.

CHURCH, R.; REVELLE, C. The maximal covering location problem. Papers of the Regional Science Association, v. 32, p. 101–118, 1974.

COOPER, L. Location-allocation problems. Operations Research, v. 11, p. 331–343, 1963.

DENSHAM, P.; RUSHTON, G. A more efficient heuristic for solving large p-median problems. Papers of the Regional Science Association, v. 71, p. 307–329, 1992.

ESRI. Avenue customization and application development for arcview. Environmental System Research Institute,Inc., 1996. 239 p.

GALVÃO, R. D.; ESPEJO, L. G. A.; BOFFEY, B. A comparison of lagrangean and surrogate relaxations for the maximal covering location problem. European Journal of Operational Research, v. 124, n. 2, p. 377-389, 2000.

GALVÃO, R. D.; REVELLE, C. A lagrangean heuristic for the maximal covering location problem. European Journal of Operational Research, v. 88, n. 1, p. 114-123, 1996.

LORENA, L. A. N.; PEREIRA, M. A. A Lagrangean/surrogate heuristic for the maximal covering location problem using Hillsman's edition. International Journal of Industrial Engineering, v. 9 n.1, p. 57-67, 2002. Special Issue on Facility Location and Layout.

LORENA, L. A. N.; SENNE, E. L. F. Local search heuristics for capacitated p-median problems. Networks and Spatial Economics, v . 3, n. 4, p. 407-419, 2003.

MARTELLO, S.; Toth, P. Knapsack problems, algorithms and computer implementations. John Wiley, 1990. 296 p.

SCHILLING, D. A.; JAYARAMAN, V.; BARKHI, R. A review of covering problems in facility location. Location Science, v. 1, n. 1, p. 25-55, Aug. 1993.

OSMAN, I. H.; CHRISTOFIDES, N. Capacitated clustering problems by hybrid simulated annealing and tabu search. International Transactions in Operational Research, v. 1, n. 3, p. 317-336, 1994.

TAILLARD, E. D. Heuristic methods for large centroid clustering problems. Journal of Heuristics , v . 9, n. 1, p. 51-73, 2003.

TEITZ, M.; BART, P. Heuristics methods for estimating the generalized vertex median of a weighted graph. Operations Research, v. 16, p. 955-961, 1968.

YEH, A. G.; CHOW, M. H. An integrated GIS and location-allocation approach to public facilities planning – an example of open space planning. Comput., Environ. and Urban Systems, v. 20, n. 4/5, p. 339-350, 1996.
5883a3fb7f8c9da00c8b4717 1574685864 Articles
Links & Downloads

Production

Share this page
Page Sections