We study the problem of building subscriber lines with minimal length of duct in telecommunication networks. For, designing physical distribution system or integrated circuit, this problem is known as the k-Minimum Spanning Tree or k-MST problem and it has been widely studied before. In this paper, we demonstrate that for building subscriber lines, general k-MST algorithms does not offer the suitable computing time, because they are based on greedy algorithm and there are many factors to calculate. Thus, we reformulate the problem in terms of minimizing the computing time, rather than the length of duct. We propose heuristic algorithms to compute good approximations for subscriber lines. Our simulation results show that the proposed heuristic algorithms offer affordable computing time compared with general k-MST algorithms without compromising over the length of duct.
展开▼
