Wide area telecommunication network design: application to the Alberta SuperNet

Abstract

This article proposes a solution methodology for the design of a wide area telecommunication network. This study is motivated by the Alberta SuperNet project, which provides broadband Internet access to 422 communities across Alberta. There are two components to this problem: the network design itself, consisting of selecting which links will be part of the solution and which nodes should house shelters; and the loading problem which consists of determining which signal transport technology should be installed on the selected edges of the network. Mathematical models are described for these two subproblems. A tabu search algorithm heuristic is developed and tested on randomly generated instances and on Alberta SuperNet data.

Keywords:

• heuristic
• network design
• telecommunications

Acknowledgements

This work was partially supported by the Canadian Natural Sciences and Engineering Research Council under grants CRD 268431, OGP 25481 and 39682-05. This support is gratefully acknowledged. Thanks are due to Fatma Gzara, Osman Alp, Erla Anderson and two anonymous referees for their valuable comments.