A gradient driven transportation algorithm

Abstract

In this work we present a new algorithm for the solution of the transportation problem. Although the algorithm is gradient-directed, it does not use the classical gradient approach. Instead, it first computes a reduced gradient and then determines an improved feasible direction in the dual space, thereby extending the initial gradient. To accomplish this, we make use of a special diagonal ordering of the basic vectors. After obtaining the intial basic feasible solution, the algorithm may transfer, without any computational overhead, to a streamlined dual simplex routine, or continue on with the gradient method.

Keywords:

• Transportation problem
• extended reduced gradient