Capacitated minimum spanning trees: Algorithms using intelligent search

In this paper a survey on existing algorithms for the capacitated minimum spanning tree problem (CMST) is given. The algorithms are classified providing some insights into their fundamental principles. Reporting the literature, comparisons of the solution quality are given. As one result of the exploration it is observed that heuristic procedures for the CMST in general consider arcs when generating or transforming a solution. Contrary to this we develop an improvement procedure which is based on partitioning nodes into subsets thus focusing more on the combinatorial nature of the CMST. Given a feasible solution the attained node assignment is altered by a local search process based on shifts and node exchanges. To overcome local optimality simulated annealing and tabu search are investigated. Computations on some benchmark test problems are reported and improvements over the well-known Esau-Williams solution are presented. Some new best solutions are obtained