Upper bounds minimum-cost for single-source uncapacitated concave network flow problems

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

Autores

Dalila B.M.M. Fontes (Autor) FEP; Hadjiconstantinou, E (Autor) Outra; Christofides, N (Autor) Outra

Revista

Título: Networks

Vol. 41

Páginas: 221-228

ISSN: 0028-3045

Editora: Wiley-Blackwell

Indexação

ISI Web of Knowledge - 12 Citações

Scopus - 14 Citações

Outras Informações

ID Authenticus: P-000-G52

DOI: 10.1002/net.10076

Abstract (EN): In this paper, we describe a heuristic algorithm based on local search for the Single-Source Uncapacitated (SSU) concave Minimum-Cost Network Flow Problem (MCNFP). We present a new technique for creating different and informed initial solutions to restart the local search, thereby improving the quality of the resulting feasible solutions (upper bounds). Computational results on different classes of test problems indicate the effectiveness of the proposed method in generating basic feasible solutions for the SSU concave MCNFP very near to a global optimum. A maximum upper bound percentage error of 0.07% is reported for all problem instances for which an optimal solution has been found by a branch-and-bound method. (C) 2003 Wiley Periodicals, Inc.

Idioma: Inglês

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

Nº de páginas: 8