Abstract

We focus on a problem encountered when designing centralized telecommunications networks, namely, the terminal layout problem. Given each terminal's geographical location, the problem consists in creating multipoint lines rooted at a central site (typically a concentrator) in order to save on connection costs. Well-known multipoint line topologies are the tree, the bus, and the loop. When terminals are assigned a weight representing the average traffic amount exchanged with the central site and lines are constrained by the amount of traffic they can carry, the tree-topology problem is referred to as the Capacitated Minimum Spanning Tree (CMST) problem. Algorithms that generate solutions for CMST problems create tree structured networks but can also be used to produce bus structured networks by imposing additional constraints. As for the loop topology, the problem is analogous to the Vehicle Routing problem found in Operation Research. These problems are NP-Complete. Finding an optimal solution in an acceptable amount of time is, therefore, unlikely due to the exponential growth in complexity relative to problem size. Nevertheless, techniques yielding exact solutions have been developed but are limited to networks of no more than, say, 50 terminals. Alternatively, heuristics solve the problem to near-optimality with acceptable computational effort. We designed applications with graphical output capabilities for Windows 3.1$\sp{\rm TM}$ using simulated annealing (SA) in an attempt to improve upon well-known heuristic solutions. Our SA programs are presented along with computational results on data sets containing up to 250 terminals. Results are evaluated and compared with those obtained with other heuristic methods.