A restricted-entry method for a transportation problem with piecewise-linear concave costs

This paper presents a heuristic solution method for a transportation problem with piecewise-linear concave costs. The solution algorithm extends the restricted-entry-basis rule for the simplex method to the transportation method. The method not only finds a local optimum (as in the simplex version), but also efficiently searches for better local optima. Computational experience indicates that the algorithm finds optimal or near optimal solutions within a reasonable time on a personal computer.