×

Genetic algorithm for network cost minimization using threshold based discounting. (English) Zbl 1076.90006

This paper describes a genetic algorithm for a network flow problem. The key characteristic in this problem is that there may be a threshold associated to an arc such that if the amount of flow over an arc exceeds the corresponding threshold, a discount applies with respect to the costs. The solution of the linear programming relaxation of an integer formulation of the problem is used as a starting point for a genetic algorithm. Computational results are presented for instances with up to 25 nodes.

MSC:

90B10 Deterministic network models in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI EuDML