COST-MINIMIZING CONSTRUCTION OF A UNIDIRECTIONAL SHR WITH DIVERSE PROTECTION

The widespread use of SONET technology makes the self-healing ring (SH R) architecture the most basic building-block in designing a large fib er-optic network which is not only survivable but also cost-effective, We address the design problem of placing a single SONET unidirectiona l ring with a single gateway hub in a region administered by a communi ty of interest, Introduced for the purpose of further cost-saving in o ur problem setting is the flexibility that some offices, instead of be ing included in the ring, can be homed to the ring via two are-disjoin t paths, Given the set of offices and potential arcs, the objective is then to determine at the minimum total cost both the ring location an d the homing to the ring of its nonmember nodes. We formulate the prob lem as a mixed integer programming model and develop an efficient solu tion procedure by devising six improvement heuristics, Extensive compu tational experiments are conducted with input data instances selected from the data ranges of the real-world environments, The practical val ue of the solution procedure for network planners is well evidenced by its excellent and consistent performance of quickly generated good-qu ality solutions over various input data instances.