CONDUIT AND CABLE INSTALLATION FOR A CENTRALIZED NETWORK WITH LOGICAL STAR-STAR TOPOLOGY

Abstract

We address a comprehensive design issue of a centralized communication network with logical star-star topology: each established hub is connected to the center node via its own cable route which may pass through a number of sites, and so is the connection from a user to its destination hub. The study distinguishes itself from other network design studies in the literature by explicitly addressing the reality that the cable can be installed only in the conduit, and some hub devices such as line concentrators and multiplexers, if properly installed, would provide more economical cable paths. A cost minimization model is first made to cover three types of decisions in one setting: locating hubs, placing conduit system, and installing cable therein. It is then formulated as a variant of classical network design model, allowing the incorporation of the well-known dual-ascent solution strategy. Despite the complexity inherent to the design problem, the performance of the proposed solution heuristic is shown via the extensive computational experiments with large-scale test problems to be very satisfactory in both speed and quality of the solutions generated.