This thesis is concerned with a heuristic approach for node clustering problem arising in designing the fiber-optic telecommunication network.
In designing the telecommunication network, it is a matter for deep reflection that we partition the region into a number of clusters, since we must consider the geographical and administrative characteristics of the region to be partitioned, distribution of traffic demands, structure of the network, various designing costs and so on. The clustering problem for network design formulated in integer programming is a special case of graph partitioning problem which has been studied for a long time in graph theory and proved to be NP-hard. Therefore, if the region to be clustered is very wide the number of decision variables increases and it takes a lot of time to obtain the optimal solution of this problem. In this study, we have developed a heuristic for this clustering problem and derived some computational results.
