Análise de desempenho da heurística Busca Local com permuta All Pairs aplicada ao problema de alocação de facilidades

Autores

  • Tarcísio Barroso Marques Instituto Federal de Educação, Ciência e Tecnologia Fluminense - Campus Itaperuna, BR 356, Km 3 s/n
  • Lucas de Souza Siqueira Instituto Federal de Educação, Ciência e Tecnologia Fluminense - Campus Itaperuna, BR 356, Km 3 s/n
  • Rodrigo Oliveira Zacarias Instituto Federal de Educação, Ciência e Tecnologia Fluminense - Campus Itaperuna, BR 356, Km 3 s/n

DOI:

https://doi.org/10.13037/ria.vol13n2.202

Resumo

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

2018-02-26

Como Citar

Marques, T. B., Siqueira, L. de S., & Zacarias, R. O. (2018). Análise de desempenho da heurística Busca Local com permuta All Pairs aplicada ao problema de alocação de facilidades. Revista De Informática Aplicada, 13(2). https://doi.org/10.13037/ria.vol13n2.202

Edição

Seção

Artigos