Abstract (EN):
The Hop-constrained Minimum cost Flow Spanning Tree (HMFST) problem is an extension
of the Hop-Constrained Minimum Spanning Tree problem since it considers flow requirements
other than unit flows. Given that we consider the total costs to be nonlinearly flow dependent
with a fixed-charge component and given the combinatorial nature of this class of problems, we
propose a heuristic approach to address them. The proposed approach is a hybrid metaheuristic
based on Ant Colony Optimization (ACO) and on Local Search (LS). In order to test the
performance of our algorithm we have solved a set of benchmark problems and compared the
results 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 of
CPLEX. Our algorithm proved to be able to find an optimum solution in more than 75% of the
runs, for each problem instance solved, and was also able to improve on many results reported
for the MPGA. Furthermore, for every single problem instance we were able to find a feasible
solution, which was not the case for the MPGA nor for CPLEX. Regarding running times, our
algorithm improves upon the computational time used by CPLEX and was always lower than
that of the MPGA.
Idioma:
Inglês
Tipo (Avaliação Docente):
Científica
Tipo de Licença: