Advertisement

An Efficient Heuristic for the Ring Star Problem

  • Thayse Christine S. Dias
  • Gilberto F. de Sousa Filho
  • Elder M. Macambira
  • Lucidio dos Anjos F. Cabral
  • Marcia Helena C. Fampa
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4007)

Abstract

In this paper, we consider a combinatorial optimization problem that arises in the design of telecommunications network. It is known as the Ring Star Problem. In this problem the aim is to locate a simple cycle through a subset of vertices of a graph with the objective of minimizing the sum of two costs: a routing cost proportional to the length of the cycle, and an assignment cost from the vertices not in the cycle to their closest vertex on the cycle. We propose a new hybrid metaheuristic approach to solve the Ring Star Problem. In the hybrid metaheuristic, we use a General Variable Neighborhood Search (GVNS) to improve the quality of the solution obtained with a Greedy Randomized Adaptive Search Procedure (GRASP). A set of extensive computational experiments on instances from the classical TSP library and randomly generated are reported, comparing the GRASP/GVNS heuristic with other heuristic found in the literature. These results indicate that the proposed hybrid metaheuristic is highly efficient and superior to the other available method proposed for the Ring Star Problem.

Keywords

ring star problem network design GRASP VNS heuristics 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. Journal of Global Optimization 6, 109–133 (1995)CrossRefMathSciNetzbMATHGoogle Scholar
  2. 2.
    Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP. Technical Report TD-5WYSEW, AT&T Labs Research (2004)Google Scholar
  3. 3.
    Gourdin, E., Labbé, M., Yaman, H.: Telecommunication and location. In: Drezner, Z., Hamacher, H. (eds.) Facility Location: applications and theory, pp. 275–305. Springer, Heidelberg (2002)Google Scholar
  4. 4.
    Hansen, P., Mladenović, N.: Variable neighborhood search. Computers & Operations Research 24(11), 1097–1100 (1997)CrossRefMathSciNetzbMATHGoogle Scholar
  5. 5.
    Hansen, P., Mladenović, N.: Variable neighbourhood search. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 145–184. Kluwer, Dordrecht (2003)Google Scholar
  6. 6.
    Labbé, M., Laporte, G., Martín, I.R., González, J.J.S.: The ring star problem: Polyhedral analysis and exact algorithm. Networks 43(3), 177–189 (2004)CrossRefMathSciNetzbMATHGoogle Scholar
  7. 7.
    Labbé, M., Laporte, G., Martín, I.R., González, J.J.S.: Locating median cycles in networks. European Journal of Operational Research 160(2), 457–470 (2005)CrossRefMathSciNetzbMATHGoogle Scholar
  8. 8.
    Martins, S.L., Ribeiro, C.C.: Metaheuristics and applications to optimization problems in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (eds.) Handbook of Optimization in Telecommunications, pp. 103–128. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  9. 9.
    Pérez, J.M., Moreno Vega, M., Martín, I.R.: Variable neighbourhood tabu search and its application to the median cycle problem. European Journal of Operational Research 151, 365–378 (2003)CrossRefMathSciNetzbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Thayse Christine S. Dias
    • 1
  • Gilberto F. de Sousa Filho
    • 2
  • Elder M. Macambira
    • 3
  • Lucidio dos Anjos F. Cabral
    • 3
  • Marcia Helena C. Fampa
    • 1
  1. 1.Programa de Engenharia de Sistemas e ComputaçãoUniversidade Federal do Rio de JaneiroRio de JaneiroBrasil
  2. 2.Departamento de InformáticaUniversidade Federal da ParaíbaJoão PessoaBrasil
  3. 3.Departamento de EstatísticaUniversidade Federal da ParaíbaJoão PessoaBrasil

Personalised recommendations