CMST问题的分支定界算法

A branch and bound algorithm for the CMST problem

研究了网络优化设计中具有流量约束的最小生成树(CMST)问题,以是否聚合点对为条件,提出了一类新的基于点集分割思想的分支定界算法,阐述了算法的原理,通过分析搜索最优解的过程说明了算法的优势.计算结果表明,提出的算法相对于原有的基于边的分支定界算法平均减少了约83%的搜索步数,并节约了68%的计算时间.

The capacitated minimum spanning tree （CMST） problem in the optimal design of networks was studied. This paper proposed a solution method using a node-partitioning branch and bound technique, in which the branching was based on whether grouping a pair of nodes or not. By introducing the search process and pruning technique, the advantage of the algorithm was illustrated. Calculation result shows that the proposed strategy is more efficient than the previous arc - orientated branch and bound algorithm, resulting in a decrease of 83% of searching steps and 68% of computing time in an average.