Topological design of two-level telecommunication networks with modular switches

In this article we propose a mixed 0-1 linear programming model for the top ological network design problem with modular switches such as the ones that will be used in asynchronous transfer mode (ATM) frame relay and other bro adband networks. The model includes the location of switches, their configu ration with respect to ports and multiplexers, the design of an access netw ork with a star topology, and a backbone network with a fixed topology (rin g or tree). To obtain a solution, we propose a greedy heuristic that provid es a good starting solution, and a tabu search heuristic to improve the sol ution. Finally, we present an example of the application of the heuristics and results for a set of randomly generated problems with up to 500 users a nd 30 potential switch sites. For the hundreds of problems generated, the t abu algorithm produced solutions that were, on average, within 1.5% of the optimal solution, and in the worst case within 4.95% of the optimal solutio n.