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.0021Abstract
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).References
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
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.