A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems

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

Autores

Dalila B.M.M. Fontes (Autor) FEP; Eleni Hadjiconstatinou (Autor) Outra; Nicos Christofides (Autor) Outra

Revista

Título: European Journal of Operational Research

Vol. 174 Nº 2

Páginas: 1205-1219

ISSN: 0377-2217

Editora: Elsevier

Indexação

ISI Web of Knowledge - 24 Citações

ISI Web of Science

Scopus - 28 Citações

Classificação Científica

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

Outras Informações

ID Authenticus: P-004-GJT

DOI: 10.1016/j.ejor.2005.03.024

Abstract (EN): In this paper, we describe a dynamic programming approach to solve optimally the single-source uncapacitated minimum cost network flow problem with general concave costs. This class of problems is known to be NP-Hard and there is a scarcity of methods to solve them in their full generality. The algorithms previously developed critically depend on the type of cost functions considered and on the number of nonlinear arc costs. Here, a new dynamic programming approach that does not depend on any of these factors is proposed. Computational experiments were performed using randomly generated problems. The computational results reported for small and medium size problems indicate the effectiveness of the proposed approach.

Idioma: Inglês

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

Nº de páginas: 15