National Taiwan University Department of Information ManagementYena, Hong-HsuHong-HsuYenaLin, Yeong-Sung FrankYeong-Sung FrankLin2006-11-142018-06-292006-11-142018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/2006111501244117Among various access network topologies, the tree topology is the most popular due to its simplicity and relatively low cost. A salient example is the CATV network. In this paper, we consider the tree-based access network design problem where the operational cost and the fixed installation cost are jointly minimized. The problem is formulated as a combinatorial optimization problem, where the difficulty of solving a Steiner tree problem typically encountered in a tree-based topological design problem is particularly circumvented. The basic approach to the algorithm development is Lagrangean relaxation and the subgradient method. In the computational experiments, the proposed algorithm calculates near-optimal solutions within 3.2% of an optimal solution in 1 min of CPU time for test networks of up to 26 nodes.application/pdf238250 bytesapplication/pdfzh-TWAccess network designNetwork planningTree-based networksOptimizationLagrangean relaxationSteiner tree problemotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/2006111501244117/1/3953.pdf