Heurística GRASP para o problema de p-medianas aplicado à localização de concentradores
DOI:
https://doi.org/10.5935/1809-2667.20110023Palavras-chave:
p-mediana, Otimização combinatória, GRASP, HeurísticaResumo
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
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
Edição
Seção
Licença
Os autores do manuscrito submetido à revista Vértices, representados aqui pelo autor correspondente, concordam com os seguintes termos:
Os autores mantêm os direitos autorais e concedem sem ônus financeiro à revista Vértices o direito de primeira publicação.
Simultaneamente o trabalho está licenciado sob a Licença Creative Commons Atribuição 4.0 Internacional (CC BY 4.0), que permite copiar e redistribuir os trabalhos por qualquer meio ou formato, e também para, tendo como base o seu conteúdo, reutilizar, transformar ou criar, com propósitos legais, até comerciais, desde que citada a fonte.
Os autores não receberão nenhuma retribuição material pelo manuscrito e a Essentia Editora irá disponibilizá-lo on-line no modo Open Access, mediante sistema próprio ou de outros bancos de dados.
Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada na revista Vértices (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial neste periódico.
Os autores têm permissão e são estimulados a divulgar e distribuir seu trabalho online na versão final (posprint) publicada pela revista Vértices em diferentes fontes de informação (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer tempo posterior à primeira publicação do artigo.
A Essentia Editora poderá efetuar, nos originais, alterações de ordem normativa, ortográfica e gramatical, com o intuito de manter o padrão culto da língua, contando com a anuência final dos autores.
As opiniões emitidas no manuscrito são de exclusiva responsabilidade do(s) autor(es).
Como Citar
1.png)
