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


Heuristics for the Topological Design Problem of Two-Level Multitechnology Telecommunication Networks with Modular Switches


In this article we propose a model for the topological design problem of two-level multitechnology telecommunication networks that includes the optimal location of modular switches, their configuration with respect to ports and bases, the design of an access network with a star topology and a backbone network with a fixed topology. Moreover, we consider, in order to satisfy the demand of a maximum number of clients, that several access technologies and rates can be used. Three backbone topologies are studied (ring, tree and full-mesh) and sets of valid inequalities are proposed. The model is of the integer programming variety, and in order to find a good solution, we propose a greedy heuristic that yields a starting solution and a more sophisticated heuristic based on the tabu search principle. Numerical results for problems with up to 400 clients and 30 potential switch sites are presented.

, 39 pages