Scatter search for capacitated minimum spanning tree

We develop a scatter search algorithm for the classical capacitated minimum spanning tree (CMST) problem. We address both the homogeneous and the more difficult heterogeneous variant of the problem. The CMST is central in a wide range of network design applications in industrial engineering, routing and logistics, and communication networks. Since the problem is NP-Complete, heuristic solution methods are often required to find highquality solutions within practical time limits. Research efforts have been focused on complex algorithm designs combining advanced neighborhood search techniques with exact solution methods or hybrids of genetic algorithms with various alternative search techniques and likewise supplemented with optimization procedures. In this study we go back to the roots and offer an alternative algorithm that competes with the best algorithms in the literature and both avoids complicated artifacts and is simpler to implement. Key features of the proposed algorithm include an oscillation neighborhood search method characterized by two classes of neighborhoods and an evolutionary search procedure based on a scatter search framework.

Automated summary

We develop a scatter search algorithm to solve the classical capacitated minimum spanning tree problem, including both homogeneous and heterogeneous variants. This problem is central in network design applications in industrial engineering, routing and logistics, and communication networks. Since it is an NP-Complete problem, heuristic solution methods are necessary to find high-quality solutions within practical time limits. Our proposed algorithm competes with the best algorithms in the literature and avoids complicated artifacts.