Development of a heuristic to solve the general transportation problem




transportation problem, Sew-Saw rule, linear programming, transportation simplex method


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

Author Biography

Elias Munapo, North-West University

PhD, Professor of Operations Research

Department of Statistics and Operations Research

School of Economics and Decision Sciences


Conte, D., Grossi, G., Lanzarotti, R., Lin, J., Petrini, A. (2021). Analysis of a parallel MCMC algorithm for graph coloring with nearly uniform balancing. Pattern Recognition Letters, 149, 30–36. doi:

Kumar, S., Munapo, E., Nyamugure, P. (2021). An Insight into the Characteristic Equation for an Integer Program. International Journal of Mathematical, Engineering and Management Sciences, 6 (2), 611–620. doi:

Kline, A., Ahner, D., Hill, R. (2019). The Weapon-Target Assignment Problem. Computers & Operations Research, 105, 226–236. doi:

Liu, Y., Tu, Y., Zhang, Z. (2021). The row pivoting method for linear programming. Omega, 100, 102354. doi:

Castro, J., Nasini, S. (2021). A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks. European Journal of Operational Research, 290 (3), 857–869. doi:

Rabbani, Q., Khan, A., Quddoos, A. (2019). Modified Hungarian method for unbalanced assignment problem with multiple jobs. Applied Mathematics and Computation, 361, 493–498. doi:

Taha, H. A. (2017). Operations Research: An Introduction. Harlow, United Kingdom: Pearson.

Singh, G., Singh, A. (2021). Extension of particle swarm optimization algorithm for solving transportation problem in fuzzy environment. Applied Soft Computing, 110, 107619. doi:

Holzhauser, M., Krumke, S. O., Thielen, C. (2017). A network simplex method for the budget-constrained minimum cost flow problem. European Journal of Operational Research, 259 (3), 864–872. doi:

Micheli, G., Weger, V. (2019). On Rectangular Unimodular Matrices over the Algebraic Integers. SIAM Journal on Discrete Mathematics, 33 (1), 425–437. doi:




How to Cite

Munapo, E. (2021). Development of a heuristic to solve the general transportation problem. Eastern-European Journal of Enterprise Technologies, 6(4 (114), 44–51.



Mathematics and Cybernetics - applied aspects