Solving Hop-constrained MST problems with ACO, FEP Working Paper, n. 493, 2013

Abstract

The Hop-constrained Minimum cost Flow Spanning Tree (HMFST) problem is an extensionof the Hop-Constrained Minimum Spanning Tree problem since it considers flow requirementsother than unit flows. Given that we consider the total costs to be nonlinearly flow dependentwith a fixed-charge component and given the combinatorial nature of this class of problems, wepropose a heuristic approach to address them. The proposed approach is a hybrid metaheuristicbased on Ant Colony Optimization (ACO) and on Local Search (LS). In order to test theperformance of our algorithm we have solved a set of benchmark problems and compared theresults obtained with the ones reported in the literature for a Multi-Population Genetic Algorithm(MPGA). We have also compared our results, regarding computational time, with those ofCPLEX. Our algorithm proved to be able to find an optimum solution in more than 75% of theruns, for each problem instance solved, and was also able to improve on many results reportedfor the MPGA. Furthermore, for every single problem instance we were able to find a feasiblesolution, which was not the case for the MPGA nor for CPLEX. Regarding running times, ouralgorithm improves upon the computational time used by CPLEX and was always lower thanthat of the MPGA.