Solving Hop-constrained MST problems with ACO

Marta S.R. Monteiro (), Dalila B.M.M. Fontes () and Fernando A.C.C. Fontes ()
Additional contact information
Marta S.R. Monteiro: Faculdade de Economia and LIAAD-INESC TEC
Dalila B.M.M. Fontes: Faculdade de Economia and LIAAD-INESC TEC
Fernando A.C.C. Fontes: Faculdade de Engenharia da Universidade do Porto and ISR-Porto

FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto

Abstract: 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.

Keywords: Ant Colony Optimization; Nonlinear Costs; Hybrid; Local Search; Minimum Spanning Tree Problem; Hop-constraints (search for similar items in EconPapers)
JEL-codes: C44 C61 (search for similar items in EconPapers)
Pages: 37 pages
Date: 2013-05
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/wp493.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.fep.up.pt/investigacao/workingpapers/wp493.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/wp493.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:por:fepwps:493

Access Statistics for this paper

More papers in FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto Contact information at EDIRC.
Bibliographic data for series maintained by ().