A design of the minimum cost ring-chain network with dual-homing survivability: A tabu search approach

A design of the minimum cost ring-chain network with dual-homing survivability: A tabu search approach

0.00 Avg rating0 Votes
Article ID: iaor1998514
Country: United Kingdom
Volume: 24
Issue: 9
Start Page Number: 883
End Page Number: 897
Publication Date: Sep 1997
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

This article discusses a design of the ring-chain architecture with dual homing survivability for metropolitan telecommunication networks. A self-healing ring 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 within a few seconds. Approximately 1–4% gap from the optimum is experienced in problems with reasonable size of metropolitan area networks.

Reviews

Required fields are marked *. Your email address will not be published.