Telecommunications network design with multiple technologies

Abstract

In this paper we consider a telecommunications network design problem allowing for multiple technologies. The problem arises in wide-area network and metro-area network design for which a combination of Technologies may be necessary due to high traffic volumes, long-distance transmission, and design restrictions. The network design problem builds the best network to channel traffic between a set of origins and destinations, which requires selecting links, equipping them with fiber, deciding on the type of technology, and locating switches. The goal is to minimize the total cost of the network, which accounts for the flow cost, the fiber and technology costs, and the switch-location cost. We model the problem using a multicommodity network design formulation with side constraints. We apply Benders decomposition to the problem and develop a twophase solution method that uses a number of improvements over the basic Benders algorithm. We present promising results on randomly generated test problems.