Groupe d’études et de recherche en analyse des décisions


Tabu Search and Post-Optimization Algorithms for the Topological Update of Two-Level Networks with Modular Switches


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).

, 36 pages