Uma Abordagem Híbrida GRASP-ILS para o Problema de Projeto de Redes com Topologia Anel-Estrela

Autores

  • Lisieux Marie Marinho dos Santos Andrade Universidade Federal da Paraíba
  • Lucídio dos Anjos Formiga Cabral Universidade Federal da Paraíba
  • Thayse Christine Souza Dias Centro Universitário de João Pessoa
  • Eduardo Ribas Pinto Centro Universitário de João Pessoa

DOI:

https://doi.org/10.5540/tema.2016.017.01.0021

Resumo

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

Biografia do Autor

Lisieux Marie Marinho dos Santos Andrade, Universidade Federal da Paraíba

Programa de Pós-Graduação em Informática

Lucídio dos Anjos Formiga Cabral, Universidade Federal da Paraíba

Programa de Pós-Graduação em Informática

Thayse Christine Souza Dias, Centro Universitário de João Pessoa

Departamento de Informática

Eduardo Ribas Pinto, Centro Universitário de João Pessoa

Departamento de Informática

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

2016-04-29

Como Citar

Andrade, L. M. M. dos S., Cabral, L. dos A. F., Dias, T. C. S., & Pinto, E. R. (2016). Uma Abordagem Híbrida GRASP-ILS para o Problema de Projeto de Redes com Topologia Anel-Estrela. Trends in Computational and Applied Mathematics, 17(1), 21. https://doi.org/10.5540/tema.2016.017.01.0021

Edição

v. 17 n. 1 (2016)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.