An ant colony optimization algorithm to solve the minimum cost network flow problem with concave cost functions

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2011

Autores

Marta S. R. Monteiro (Autor) Outra; Dalila B. M. M. Fontes (Autor) FEP; Fernando A. C. C. Fontes (Autor) FEUP

Ata de Conferência Internacional

Título: GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE

Páginas: 139-145

13th Annual Genetic and Evolutionary Computation Conference (GECCO)

Dublin, IRELAND, JUL 12-16, 2011

Indexação

ISI Web of Knowledge - 12 Citações

Scopus - 15 Citações

Outras Informações

ID Authenticus: P-006-4XH

DOI: 10.1145/2001576.2001596

Abstract (EN): In this work we address the Singe-Source Uncapacitated Minimum Cost Network Flow Problem with concave cost functions. Given that this problem is of a combinatorial nature and also that the total costs are nonlinear, we propose a hybrid heuristic to solve it. In this type of algorithms one usually tries to manage two conflicting aspects of searching behaviour: exploration, the algorithm's ability to search broadly through the search space; and exploitation, the algorithm ability to search locally around good solutions that have been found previously. In our case, we use an Ant Colony Optimization algorithm to mainly deal with the exploration, and a Local Search algorithm to cope with the exploitation of the search space. Our method proves to be very efficient while solving both small and large size problem instances. The problems we have used to test the algorithm were previously solved by other authors using other population based heuristics and our algorithm was able to improve upon their results, both in terms of computing time and solution quality.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 7