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.202Resumen
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.
Descargas
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2019 Tarcísio Barroso Marques, Lucas de Souza Siqueira, Rodrigo Oliveira Zacarias

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
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.