A Hybrid Optimization Algorithm for the CMST Problem

The Capacitated minimum spanning tree (CMST) problem is one of the most fundamental and significant problems in the optimal design of networks. It is also a classical combinatorial optimization problem which has been tackled by researchers for centuries using various methods. In this paper, a new NS-TS hybrid optimization algorithm that combines neighborhood search and tabu search is proposed. A novel neighborhood structure and associate tabu strategy is proposed and implemented. Computational experiments showing the effectiveness and efficiency of the algorithm on benchmark instances are given.