Concave minimum cost network flow problems solved with a colony of ants

• Tipo: Artigo em Revista Científica Internacional
• Data: 2013

Autores

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

Revista

Título: Journal of Heuristics

Vol. 19

Páginas: 1-33

ISSN: 1381-1231

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 9 Citações

Scopus - 11 Citações

INSPEC

COMPENDEX

Classificação Científica

FOS: Ciências sociais > Economia e gestão

CORDIS: Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional ; Ciências Sociais > Economia > Estudos de gestão > Gestão industrial ; Ciências Sociais > Economia > Estudos de gestão > Gestão da produção

Outras Informações

ID Authenticus: P-002-0N6

DOI: 10.1007/s10732-012-9214-6

Abstract (EN): In this work we address the Single-Source Uncapacitated Minimum Cost Network Flow Problem with concave cost functions. This problem is NP-Hard, therefore we propose a hybrid heuristic to solve it. Our goal is not only to apply an ant colony optimization (ACO) algorithm to such a problem, but also to provide an insight on the behaviour of the parameters in the performance of the algorithm. The performance of the ACO algorithm is improved with the hybridization of a local search (LS) procedure. The core ACO procedure is used to mainly deal with the exploration of the search space, while the LS is incorporated to further cope with the exploitation of the best solutions found. The method we have developed has proven 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. Our algorithm was able to improve upon some of their results in terms of solution quality, proving that the HACO algorithm is a very good alternative approach to solve these problems. In addition, our algorithm is substantially faster at achieving these improved solutions. Furthermore, the magnitude of the reduction of the computational requirements grows with problem size.

Idioma: Inglês

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

Nº de páginas: 33