Heuristic Algorithms for the Multiple-Depot Ring-Star Problem

In this paper, we consider the problem of designing urban opticalnetworks. In particular, given a set of telephone exchanges, we must design a collection of ring-stars, where each ring-star is a cycle composed of a telephone exchange, some customers, some "transition points" used to save routing costs and customers not on the cycle connected to the cycle by a single edge. The ring topology is chosen in many fiber optic communication networks since it allows to prevent the loss of connection due to a single edge or even a single node failure. The objective is to minimize the total cost of the optical network which is mainly due to the excavation costs. We call this problem Multi-Depot Ring-Star Problem (MDRSP) and we formulate it as an optimization problem in Graph Theory. We present lower bounds andheuristic algorithms for the MDRSP. Computational results onrandomly generated instances and real-life datasets are also