Development of a heuristic to solve the general transportation problem

Abstract

The transportation problem is well known and has very important applications. For this well-researched model, there are very efficient approaches for solving it that are available. These approaches include formulating the transportation problem as a linear program and then using the efficient methods such as the simplex method or interior point algorithms.

The Hungarian method is another efficient method for solving both the assignment model and the general transportation model. An assignment problem is a special case of the transportation model in which all supply and demand points are 1. Every transportation problem can be converted into an assignment problem since rows and columns can be split so that each supply and each demand point is 1.

The transportation simplex method is another method that is also used to solve the general transportation problem. This method is also called the modified distribution method (MODI). To use this approach, a starting solution is required and the closer the starting solution to the optimal solution, the fewer the iterations that are required to reach optimality.

The fourth method for transportation models is the network simplex method, which is the fastest so far. Unfortunately, all these approaches for transportation models are serial in nature and are very difficult to parallelize, which makes it difficult to efficiently use the available massively parallel technology. There is a need for an efficient approach for the transportation problem, which is easily parallelizable. This paper presents a See-Saw approach for solving the general transportation problem. This is an extension of the See-Saw approach for solving the assignment problem. The See-Saw moves can be done independently, which makes the approach proposed in this paper more promising than the available methods for transportation models