|
Description:
|
Telecommunication networks form an integral part of life . Avoiding failures on
these networks is always not possible . Designing network structures that survive these
failures have become important in ensuring the reliability of these network structures .
With the introduction of SONET (Synchronous Optical Network ) technology , rings
have become the preferred survivable network structure . This network configuration
has a set of disjoint rings (each node being a part of single ring ) , and these disjoint
rings are connected via another main ring . In this research , we present a mathematical
model for the design of such disjoint rings with node number balance criterion
among the rings . When , given a set of nodes and distances between them , the Balanced
Disjoint Rings (BDR ) problem is the minimum total link length clustering of
nodes into a given number of disjoint rings in such a way that there is almost the
same number of nodes in each ring . The BDR problem is a class of the standard
Traveling Salesman Problem (TSP ) . It is clear from this observation that the BDR
problem becomes a TSP when the number of rings required is set to one . Hence
BDR is NP -Hard , and we do not expect to obtain a polynomial time algorithm for
its solution . To overcome this problem , we developed a set of construction heuristics
(Break -MST , Distance Method , Hybrid Method , GRASP -Based Distance Method )
and improvement heuristics (Multi -Exchange , Single Move ) . Different combinations of construction and improvement heuristics were implemented and the quality of solution
thus obtained was compared to the standard Branch and Cut Technique . It was
found that the algorithm with GRASP -Based Distance Method as the construction
heuristic and multi -exchange - single -move combination as the improvement heuristic
performed better than other combinations . All combinations performed better in
general than the standard Branch and Cut technique in terms of solution time . |