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

Tarcísio Barroso Marques, Lucas de Souza Siqueira, Rodrigo Oliveira Zacarias

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.


Texto completo:

PDF

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-

, 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.

-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,

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,

, Florianópolis. Anais do Computer on

the Beach, 2017. p. 446-455. Disponível em:

https://siaiap32.univali.br/seer/index.php/ac

otb/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,

PEARL, P. Heuristics: Intelligent Search for

Computer Problem Solving. New York:

AddisonWesley, 1984.




DOI: http://dx.doi.org/10.13037/ras.vol13n2.202

Apontamentos

  • Não há apontamentos.


Revista de Informática Aplicada - USCS/UFABC