Heuristic solutions for general concave minimum cost network flow problems

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

Autores

Dalila B M M Fontes (Autor) FEP; Jose Fernando Goncalves (Autor) FEP

Revista

Título: Networks

Vol. 50 Nº 1

Páginas: 67-76

ISSN: 0028-3045

Editora: Wiley-Blackwell

Indexação

ISI Web of Knowledge - 28 Citações

Scopus - 30 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-004-8KS

DOI: 10.1002/net.20167

Abstract (EN): We address the single-source uncapacitated minimum cost network flow problem with general concave cost functions. Exact methods to solve this class of problems in their full generality are only able to address small to medium size instances, since this class of problems is known to be NP-Hard. Therefore, approximate methods are more suitable. In this work, we present a hybrid approach combining a genetic algorithm with a local search. Randomly generated test problems have been used to test the computational performance of the algorithm. The results obtained for these test problems are compared to optimal solutions obtained by a dynamic programming method for the smaller problem instances and to upper bounds obtained by a local search method for the larger problem instances. From the results reported it can be shown that the hybrid methodology improves upon previous approaches in terms of efficiency and also on the pure genetic algorithm, i.e., without using the local search procedure. (C) 2007 Wiley Periodicals, Inc.

Idioma: Inglês

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

Nº de páginas: 10