Heurística GRASP para o problema de p-medianas aplicado à localização de concentradores

Autores

  • Tiago de Azevedo Santos IFF
  • Dalessandro Soares Vianna Universidade Federal Fluminense (UFF)
  • Marcilene de Fátima Dianin Vianna Universidade Federal Fluminense (UFF)

DOI:

https://doi.org/10.5935/1809-2667.20110023

Palavras-chave:

p-mediana, Otimização combinatória, GRASP, Heurística

Resumo

Várias situações práticas reais, tais como localizações de depósitos, hospitais e dispositivos de telecomunicações (concentradores, torres de celulares, etc), podem ser vistas como um problema de p-medianas. Este trabalho apresenta uma proposta para a solução do problema de p-medianas baseado no backbone da rede de computadores que será instalado no Instituto Federal Fluminense (IFF). Esse tipo de ocorrência é conhecida na literatura como problema de localização de concentradores. Para resolver a questão citada foi proposta uma heurística GRASP. Testes computacionais realizados, mostram que a heurística elaborada neste trabalho atingiu resultados satisfatórios.

Downloads

Não há dados estatísticos.

Biografia do Autor

Tiago de Azevedo Santos, IFF

Pós-graduado em Produção e Sistemas - IFF

Dalessandro Soares Vianna, Universidade Federal Fluminense (UFF)

Doutor em Informática (PUC-Rio). Professor Adjunto da Universidade Federal Fluminense – UFF

Marcilene de Fátima Dianin Vianna, Universidade Federal Fluminense (UFF)

Mestre em Matemática (PUC-Rio). Professora Assistente da Universidade Federal Fluminense – UFF

Referências

ASSUNÇÃO, R.M.; LAGE, J.P.; A.REIS, E.; SILVA, P.L.N. Análise de conglomerados espaciais via árvore geradora mínima. Revista Brasileira de Estatística, v.63, p.7-24, 2004.

CHIYOSHI, F.; GALVÃO, R.D. A statistical analysis of simulated annealing applied to the p-median problem. Annals and Operations Research, v.96, p.61-74, 2000.

DRUMMMOND, L.M.A.; OCHI, L.S.; VIANNA, D.S. An asynchronous parallel metaheuristic for the period vehicle routing problem. Future Generation Computer Systems, v.17, n.4, p.379-386, 2001.

ERKUT E.; BOZKAYA, B.; ZHANG, J. An effective genetic algorithm for the p-median problem. Alberta: University of Alberta, 1997. 23 p

FEO, T.A. AND RESENDE, M.G.C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v.6, p.109-133, 1995.

GOLDMAN, A.J. Optimal location for centers in a network. Transportation Science, v.3, p.352–360, 1969.

HANSEN, P.; MLADENOVIC, N.; PEREZ-BRITO. Variable neighborhood decomposition search. Journal of Heuristics, v.7, p.335-350, 2001.

HOSAGE, C.M.; GOODCHILD, M.F. Discrete space location-allocation solutions from genetic algorithms. Annals of Operations Research, v.6, p.657-682, 1986.

MARQUES, T.B.; ARROYO, J.E.C. ; VIANNA, D.S. Heurísticas para o problema de alocação de antenas de transmissão. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 2007, Fortaleza. p. 1-12.

O’KELLY, M.E. A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, v.32, p.393–404, 1987.

RESENDE, M.G.C. Greedy Randomized Adaptive Search Procedures (GRASP). AT&T Labs Research Technical Report, v.98.41.1, 1998.

RESENDE, M. G. C.; RIBEIRO, C. C. Greedy randomized adaptive search procedures. In: GLOVER, F. ; KOCHENBERGER, G. (Eds.). Handbook of metaheuristics. England: Kluwer, 2003. p.219-249.

RESENDE, M.G.C.; WERNECK, R.F. A Hybrid Heuristic for p-Median Problem. Journal of Heuristics, v.10, p.59-88, 2004.

RIBEIRO, C.C.; VIANNA, D.S. A hybrid genetic algorithm for the phylogeny problem using path-relinking as a progressive crossover strategy. International Transactions in Operational Research, v.16, p.641-657, 2009.

ROLLAND, E.; SCHILLING, D.A.; CURRENT, J.R. An efficient tabu search procedure for the pmedian problem. European Journal of Operational Research, v.96, n.2, p.329-342, 1996.

VOSS, S. A reverse elimination approach for the p-median problem. Studies in Locational Analysis, v.8, p.49-58, 1996.

Downloads

Como Citar

SANTOS, T. de A.; VIANNA, D. S.; VIANNA, M. de F. D. Heurística GRASP para o problema de p-medianas aplicado à localização de concentradores. Revista Vértices, [S. l.], v. 13, n. 3, p. 31–40, 2011. DOI: 10.5935/1809-2667.20110023. Disponível em: https://essentiaeditora.iff.edu.br/index.php/vertices/article/view/1809-2667.20110023. Acesso em: 4 fev. 2023.

Edição

Seção

Artigos Originais

Artigos mais lidos pelo mesmo(s) autor(es)