Solving transportation problems with concave cost functions using genetic algorithms

Abstract

In this paper we propose a genetic algorithm for solving the non-linear transportation problem on a network with concave cost functions and the restriction that the flow must pass through all arcs of the network. We show that the algorithm can be used in solving large-scale problems. We prove that the complexity of a single iteration of the algorithm is $O(nm)$ and converges to an $\epsilon$-optimum solution. We also present some implementation and testing examples of the algorithm using Wolfram Mathematica.

Keywords

• genetic algorithm
• population
• minimum cost flow
• non-linear transport problem
• large-scale problem
• concave function