Análise de desempenho da heurística Busca Local com permuta All Pairs aplicada ao problema de alocação de facilidades
DOI:
https://doi.org/10.13037/ria.vol13n2.202Resumo
Este artigo apresenta uma Busca Local que faz a permuta All Pairs, aplicada ao problema de alocação de facilidades, tratado como o problema das p-medianas. O objetivo é alocar um número fixo de facilidades (medianas) em pontos estratégicos de uma região para minimizar a distância total envolvida, entre as facilidades abertas e os pontos de demanda atendidos, aplicando-se a Busca Local, visando a melhoria da solução inicial. Em uma nova abordagem do problema, foi imposta uma restrição de distância que informa se a facilidade mais próxima ao ponto de demanda poderá atendê-lo ou não. O trabalho apresentado neste artigo poderá ser usado por outras Meta-heurísticas, como um Algoritmo Genético, através a criação de uma população inicial já melhorada pelo processo da Busca Local, dentre outros.
Downloads
Referências
ARYA, V.; GARGA, N.; KHANDEKAR, R., MEYERSON, K. M.; PANDIT, V. Local Search Heuristics for K-Median and Facility Location Problems, Vol. 33, No 3, pp. 544-562, 2004.
BRONDANI, A. E.; FRANÇA, F. A. M.; KOPP JÚNIOR, R. V.; NETTO, P. O. B.; JURKIEWICZ, S. Alocação de unidades urbanas de lazer por um modelo de p-medianas. Revista Eletrônica Pesquisa Operacional para o Desenvolvimento, Rio de Janeiro, v. 5, n. 2, p. 209-223, mai./ago, 2013.
CAPDEVILLE, R. M. A.; VIANNA, D. S. Heurísticas GRASP para o problema de alocação de pontos de acesso em uma rede sem fio em ambiente indoor. Revista Eletrônica Sistemas & Gestão, v. 8, n. 1, p. 86-93, 2013.
HAKIMI, S. L. Optimum distribution of switching centers and the medians of a graph. Operations Research, 12, 450-459, 1964.
HAKIMI, S. L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Operations Research, 13, 462-475, 1965.
LINTZMAYER, C. N.; MULATI, M. H.; SILVA, A. F. RT-ColorAnt: Um Algoritmo Heurístico Baseado em Colônia de Formigas Artificiais com Busca Local para Colorir Grafos, XLIII Simpósio Brasileiro de Pesquisa Operacional, pp. 1666-1677, 2011.
LORENA, L. A. N; SENNE, E. L; PAIVA, J. A. Integração de modelos de localização a sistemas de informações geográficas. Gestão & Produção, São Carlos, v. 8, n. 2, 2001.
LORENA, L; SENNE, E. Local search heuristics for capacitated p-median problems, Networks and Spatial Economics. v.3, n.4, pp. 407-419, 2003.
MARQUES, T. B.; SIQUEIRA, L. S.; ZACARIAS, R. O. Busca Local com permuta All Pairs aplicada ao problema de alocação de facilidades. In: Computer on the Beach, 2017, Florianópolis. Anais do Computer on the Beach, 2017. p. 446-455. Disponível em: https://siaiap32.univali.br/seer/index.php/acotb/article/view/10574/5929. Acesso em: 18 jan. 2018.
RIBEIRO, W. S.; ARROYO, J. E. C. Metaheurística GRASP biobjetivo para um problema de localização de facilidades. Anais do Encontro Nacional de Engenharia de Produção, Rio de Janeiro, 2008.
RIBEIRO, P. C. F. Um enfoque na localização de facilidade baseado em testes de redução e heurísticas ADD/DROP. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação), Faculdade Lourenço Filho, Fortaleza/CE, 2008.
PEARL, P. Heuristics: Intelligent Search for Computer Problem Solving. New York: AddisonWesley, 1984.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2019 Tarcísio Barroso Marques, Lucas de Souza Siqueira, Rodrigo Oliveira Zacarias

Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Os autores que publicam trabalhos na RIA estão de acordo com os seguintes termos:
- Autores mantêm seus direitos autorais e concedem à RIA o direito à primeira publicação. Admite-se o compartilhamento do referido trabalho, desde que seja reconhecida sua autoria e publicação inicial nesta revista.
- Autores podem fechar contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicado na RIA, com reconhecimento de sua autoria e publicação inicial nesta revista.
- Autores podem publicar e distribuir seu trabalho online, antes ou durante o processo editorial.