A DESIGN OF THE MINIMUM COST RING-CHAIN NETWORK WITH DUAL-HOMING SURVIVABILITY: A TABU SEARCH APPROACH

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 470
  • Download : 2
This article discusses a design of the ring-chain architecture with dual homing survivability for metropolitan telecommunication networks. A self-healing ring (SHR) and multiple chains are considered to cover hub, ring nodes and other offices. Offices in a chain are connected to the ring in dual homing fashion to increase the survivability. Given a ring topology, the problem is to minimize the link cost of the chain network which satisfies the dual homing constraint. An integer programming formulation and the NP-completeness of the problem is presented. As a solution procedure, a tabu search is proposed with two types of moves; insert and swap. To increase the efficiency of the search procedure, tabulists, aspiration criteria, and diversification strategy are discussed. The computational results show that the proposed tabu search provides near optimal solutions wiflfin a few seconds. Approximately 1%-4% gap from the optimum is experienced in problems with reasonable size of metropolitan area networks.
Publisher
Elsevier
Issue Date
1997
Citation

Computers & Operations Research, Vol.24, No.9, pp.883-897

ISSN
0305-0548
URI
http://hdl.handle.net/10203/23243
Appears in Collection
IE-Journal Papers(저널논문)

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0