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

• Type: Article in International Conference Proceedings Book
• Date: 2011

Authors

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

Conference proceedings International

Title: GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE

Pages: 139-145

13th Annual Genetic and Evolutionary Computation Conference (GECCO)

Dublin, IRELAND, JUL 12-16, 2011

Indexing

ISI Web of Knowledge - 12 Citations

Scopus - 15 Citations

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 7