A hybrid ACO algorithm for the Capacitated Minimum Spanning Tree Problem

The problem of finding a Capacitated Minimum Spanning Tree asks for connecting a set of client nodes to a root node through a minimum cost tree network, subject to capacity constraints on all links. This paper reports on our design, implementation and performance evaluation of a hybrid Ant Colony Optimization algorithm for finding Capacitated Minimum Spanning Trees. Our Ant Colony Optimization algorithm is based on two important problem characteristics, namely the close relationship of the Capacitated Minimum Spanning Tree Problem with both the Capacitated Vehicle Routing Problem and the Minimum Spanning Tree Problem and hybridizes the Savings based Ant System with the algorithm of Prim, which is used to solve the subproblems of finding minimal spanning trees exactly. To assess the performance of our implementation we perform a computational study on a set of well known benchmark instances. For these instances our results show both the effectiveness and the efficiency of our algorithm when compared to several other state-of-the-art techniques.