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

• Type: Article in International Scientific Journal
• Date: 2013

Authors

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

Journal

Title: Journal of Heuristics

Vol. 19

Pages: 1-33

ISSN: 1381-1231

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 10 Citations

COMPENDEX

INSPEC

Scientific classification

FOS: Social sciences > Economics and Business

CORDIS: Physical sciences > Mathematics > Applied mathematics > Operations research ; Social sciences > Economics > Management studies > Industrial management ; Social sciences > Economics > Management studies > Production management

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 33