On Optimal Solutions for the Optimal Communication Spanning Tree Problem

作     者：Rothlauf, Franz 

作者机构：Johannes Gutenberg Univ Mainz Dept Informat Syst D-55099 Mainz Germany 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2009年第57卷第2期

页      面：413-425页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：communications networks/graphs simulation statistical analysis topological network design tree algorithms 

摘      要：This paper presents an experimental investigation into the properties of the optimal communication spanning tree (OCST) problem. The OCST problem seeks a spanning tree that connects all the nodes and satisfies their communication requirements at a minimum total cost. The paper compares the properties of random trees to the properties of the best solutions for the OCST problem that are found using an evolutionary algorithm. The results show, on average, that the optimal solution and the minimum spanning tree (MST) share a higher number of links than the optimal solution and a random tree. Furthermore, optimal solutions for OCST problems with randomly chosen distance weights share a higher number of links with an MST than OCST problems with Euclidean distance weights. This intuitive similarity between optimal solutions and MSTs suggests that some heuristic optimization methods for OCST problems might be improved by starting with an MST. Using an MST as a starting solution for a greedy search in the tested cases either improves median running time up to a factor of 10 while finding solutions of the same quality, or increases solution quality up to a factor of 100 while using the same number of search steps in comparison to starting the greedy search from a random tree. Starting a local search, a simulated annealing approach and a genetic algorithm from an MST increases solution quality up to a factor of three in comparison to starting from a random solution.