Skip to main content
Log in

Least-cost network topology design for a new service

An application of tabu search

  • Section V Heuristics And Paraller Algorithms
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a centralized new service. Our results are compared to those of a greedy algorithm which applies corresponding decision rules, but without the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs that can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C. Anderson and C. Rasmussen, A genetic algorithm for the new service network topology problem, in:Heuristics for Combinatorial Optimization, Section 7 (1989) 190–206.

    Google Scholar 

  2. F. Glover, Tabu search, Part 1, ORSA J. Comp. 1(1989)190–206.

    Google Scholar 

  3. F. Glover, Candidate lists and tabu search, Preprint, CAAI, University of Colorado (1989).

  4. A. Hertz and D. de Werra, The tabu search metaheuristic: How we used it, Ann. Math. AI 1(1990)111–121.

    Google Scholar 

  5. M. Lee, Least cost network topology design for a new service using the tabus search, in:Heuristics for Combinatorial Optimization, Section 6 (1989), pp. 1–18.

    Google Scholar 

  6. M. Malek, M. Guruswamy, H. Owens and M. Pandya, Serial and parallel search techniques for the traveling salesman problem, Ann. Oper. Res. 21(1989)59–84.

    Google Scholar 

  7. S.H. Parrish, T. Cox, W. Keuhner and Y. Qui, Planning for least cost expansion of communications network topology, US West Advanced Technologies Science and Technology Technical Report.

  8. J. Ryan (ed.), Final report of mathematics clinic, in:Heuristics for Combinatorial Optimization (1989).

  9. J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem, Research Report HAR-89-001, W.A. Harriman School for Management and Policy, SUNY at Stony Brook, NY (1989), to appear in ORSA J. Comp.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

This research was partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract No. F49629-90-C-0033.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Glover, F., Lee, M. & Ryan, J. Least-cost network topology design for a new service. Ann Oper Res 33, 351–362 (1991). https://doi.org/10.1007/BF02073940

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02073940

Keywords

Navigation