Please use this identifier to cite or link to this item: https://hdl.handle.net/10216/70705
Author(s): Marta Monteiro
Dalila B.M.M. Fontes
Fernando A.C.C. Fontes
Title: Solving Hop-constrained MST problems with ACO, FEP Working Paper, n. 493, 2013
Issue Date: 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.
Subject: Economia e gestão
Economics and Business
Scientific areas: Ciências sociais::Economia e gestão
Social sciences::Economics and Business
URI: https://repositorio-aberto.up.pt/handle/10216/70705
Document Type: Trabalho Académico
Rights: openAccess
License: https://creativecommons.org/licenses/by-nc/4.0/
Appears in Collections:FEP - Trabalho Académico

Files in This Item:
File Description SizeFormat 
40114.pdf1.63 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons