Tabu meta-heuristic based on local search for the concave production–transportation problem

Recently, strongly polynomial time algorithms have been developed for special concave minimisation problems under network constraints and with a fixed number of non-linear variables. In many cases these algorithms are not computationally efficient unless the number of non-linear variables is very small. However, the ideas behind these algorithms can be utilized and embedded in heuristics which then will be able to solve large scale problems. This paper presents a tabu search meta-heuristic for the general concave production–transportation problem where the number of non-linear elements is not fixed. Our approach is based on an exact strongly polynomial algorithm. Computational results including a comparison between the performance of the tabu and the exact algorithm are presented.