A Neighborhood Structure for the CMST Problem
This paper studies the Capacitated Minimum Spanning Tree (CMST) problem, which is one of the most fundamental and significant problems in the optimal design of communication networks. A new neighborhood structure is proposed by analyzing the features of the optimal solution of the CMST problem. A new neighborhood search algorithm based on the new neighborhood structure and certain new searching methods is designed and implemented. Computational experiments showing the effectiveness of the new algorithm on benchmark instances are given.