This paper deals with the problem of how to update a telecommunication network economically. We first propose a mixed integer programming model that includes the update of the location and configuration (with respect to ports, multiplexers and bases) of switches, the update of the access network with a star topology, and the update of the backbone network with a topology specified by the network planner. Moreover, we suppose the use of multiplexers both in the access and in the backbone network. In order to find a solution, we propose an initial heuristic, a tabu-based heuristic, and a post-optimization algorithm. Among all possible topologies for the backbone network, we consider the ring topology for computational tests. Finally, we present an illustrative example, followed by a performance analysis of the proposed heuristics (using a lower bound).
Paru en décembre 1997 , 36 pages