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.
http://dx.doi.org/10.1590/S0103-65132006000200011
Prod, vol.16, n2, p.319-328, 2006
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.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email