Topological design of two-level telecommunication networks with modular switches
成果类型：
Article
署名作者：
Chamberland, S; Sansò, B; Marcotte, O
署名单位：
University of Quebec; Ecole de Technologie Superieure - Canada; University of Quebec; Ecole de Technologie Superieure - Canada; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal; University of Quebec; University of Quebec Montreal; Universite de Montreal; University of Quebec; University of Quebec Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.5.745.12412
发表日期：
2000
页码：
745-760
关键词：
摘要：
In this article we propose a mixed 0-1 linear programming model for the topological network design problem with modular switches such as the ones that will be used in asynchronous transfer mode (ATM) frame relay and other broadband networks. The model includes the location of switches, their configuration with respect to ports and multiplexers, the design of an access network with a star topology, and a backbone network with a fixed topology (ring or tree). To obtain a solution, we propose a greedy heuristic that provides a good starting solution, and a tabu search heuristic to improve the solution. Finally, we present an example of the application of the heuristics and results for a set of randomly generated problems with up to 500 users and 30 potential switch sites. For the hundreds of problems generated, the tabu algorithm produced solutions that were, on average, within 1.5% of the optimal solution, and in the worst case within 4.95% of the optimal solution.