A Tabu Search heuristic for capacitated network design

This paper studies a topical capacitated network design problem that arises in the telecommunication industry. In this problem, given point-to-point demand between various pairs of nodes, a minimum cost survivable network must be designed by installing capacitated equipments (routers, line cards, ...) on nodes as well as link facilities on arcs. This realistic problem finds its motivation in the rapidly developing field of telecommunication networks and the introduction of fiber-optic technology. It is, in particular, faced by the network designer whenever a new network is set up. To the best of our knowledge, this is the first work that addresses this capacitated network design problem where equipments, such as routers and lines cards, have to be settled on network nodes. We present a Tabu Search heuristic to find a solution that minimizes the total network cost. Numerical results are provided for randomly generated networks and networks coming from real-word applications.