GRADIENT-DIRECTED TRANSPORTATION ALGORITHMS (COMPLEXITY, PARALLEL COMPUTATION)

A new class of gradient-directed algorithms for the solution of the transportation problem is investigated. To our knowledge, this is a first successful attempt at using the gradient method for linear network flow problems. Existing algorithmic work on the transportation and network flow problems is reviewed and evaluated, along with other related work in the areas of parallel computation and computational complexity. The major contributions of this work are the following: (a) The development of a gradient-directed transportation algorithm that is simple, efficient, and suitable for practical use. (b) The development of a new type of data structures that may be used to solve not only transportation problems, but network flow problems in general. (c) Computational complexity and parallel computation results for a number of network flow and graph theoretical problems. (d) Empirical evaluation of the gradient algorithms, which have been fully implemented and tested on a number of randomly generated transportation problems with satisfactory result.