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

G-96-45

Heuristics for Ring Network Design when Several Types of Switches are Available

, et

We consider a model for communications network design that includes the optimal location of switches (of which there are several types) and the design of the access and backbone networks. The model is of the integer programming variety, and in order to find its solution, we propose a greedy heuristic that yields a good starting solution and a more sophisticated heuristic based on tabu search. Finally we present numerical results for problems including as much as 200 user sites and 20 potential switch sites.

, 16 pages