Uma Abordagem Híbrida GRASP-ILS para o Problema de Projeto de Redes com Topologia Anel-Estrela
DOI:
https://doi.org/10.5540/tema.2016.017.01.0021Resumo
As mudanças decorrentes do crescimento das redes de telecomunicações trazem consigo a elevação dos problemas de organização, dificuldades de transmissão, localização e custo. Dentro deste cenário, o presente trabalho aborda o Ring Star Problem (RSP), aplicado a uma rede de telecomunicação com topologia anel-estrela, que consiste em obter a menor soma resultante do custo do anel principal e do custo da atribuição dos elementos, utilizando para isto uma estratégia heurística híbrida: Greedy Randomized Adaptive Search Procedure (GRASP) e Iterated Local Search (ILS).Referências
R. Andrea, M. Blesa, C. Blum & S. Michael. Hybrid metaheuristics – an emerging approach to optimization, (2008).
R. Baldacci, M. Dell’Amico & J.S. Gonza ́lez. The capacitated m-ring-star problem. Operations Research, 55(6) (2007), 1147–1162.
T.C.S. Dias, G.F. Souza Filho, E.M. Macambira, L.A.F. Cabral & M.H. Fampa. An Efficient Heuristic for the Ring Star Problem. Lecture Notes in Computer Science, 4007 (2006), 24–35.
A. Enrique. Hybrid metaheuristics: a new class of algorithms. Canada: John Wiley & Sons. Wiley series on parallel and distributed computing (2005).
T. A. Feo, M. G. C Resende. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 6 (1995), 109–133.
M.T. Furtado, A.C. Rego & C.A. Loural. Prospecc ̧a ̃ o Tecnolo ́ gica e Principais Tendeˆ ncias em Telecomunicac ̧o ̃ es. Cadernos CPqD Tecnologia, 1 (2005).
E.A. Hoshino & C.C. Souza. A Branch-and-Cut-and-Price Approach for the Capacitated m-Ring- Star Problem. V Latin-American Algorithms, Graphs and Optimization Symposium – LAGOS, 35 (2009), 103–108.
S. Kedad-Sidhoum & V.H. Nguyen. An Exact Algorithm for solving the ring star problem. Optimiza- tion A Journal of Mathematical Programming and Operations Research, 59 (2008), 125–140.
M. Labbe ́, G. Laporte, I.R.Mart ́ın & J.J.S. Gonza ́lez. Median Cycle Problem, Technical Report. Department of Operations Research and Multicriteria Decision Aid at Universite ́ Libre de Bruxel- les, (2011).
M. Labbe ́, G. Laporte, I.R.Mart ́ın & J. J.S. Gonza ́lez. The Ring Star Problem: Polyhedral Analysis and Exact Algorithm. Networks, 43 (2001), 177–189.
A. Liefooghe, L. Jourdan, M. Basseur, E. Talbi & E.K. Burke. Metaheuristics for the Bi-objective Ring Star Problem. Eighth European Conference on Evolutionary Computation in Combinatorial Optimisation (2008).
H.R. Lourenc ̧o, O.C. Martin & T. Stu ̈tzle. Iterated Local Search. Handbook of Metaheuristics, (2002), 321–353.
E.M. Macambira, C.C. Souza, N.M. Filho, L.S. Ochi & L.O. Bastos. Algoritmos Eficientes para o Projeto de uma Rede de Telecomunicac ̧o ̃es com Topologia em Anel. 5◦ Encontro Regional de Matema ́tica Aplicada e Computacional – V ERMAC-R3 (2005), 19–21.
J.A.M. Pe ́rez, J.M. Moreno-Vega & I.R. Martin. Variable Neighbourhood Tabu Search and its Ap- plication to the Median Cycle Problem. European Journal of Operational Research, 151 (2003), 365–378.
M.G.C. Resende & C.C. Ribeiro. Greedy Randomized Adaptive Search Procedures. Handbook of metaheuristics, 57 (2003), 219–249.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.