Development of a heuristic to solve the general transportation problem

Authors

DOI:

https://doi.org/10.15587/1729-4061.2021.243735

Keywords:

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

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

Author Biography

Elias Munapo, North-West University

PhD, Professor of Operations Research

Department of Statistics and Operations Research

School of Economics and Decision Sciences

References

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: https://doi.org/10.1016/j.patrec.2021.05.014

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: https://doi.org/10.33889/ijmems.2021.6.2.037

Kline, A., Ahner, D., Hill, R. (2019). The Weapon-Target Assignment Problem. Computers & Operations Research, 105, 226–236. doi: https://doi.org/10.1016/j.cor.2018.10.015

Liu, Y., Tu, Y., Zhang, Z. (2021). The row pivoting method for linear programming. Omega, 100, 102354. doi: https://doi.org/10.1016/j.omega.2020.102354

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: https://doi.org/10.1016/j.ejor.2020.10.027

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: https://doi.org/10.1016/j.amc.2019.05.041

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: https://doi.org/10.1016/j.asoc.2021.107619

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: https://doi.org/10.1016/j.ejor.2016.11.024

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

Downloads

Published

2021-12-16

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. https://doi.org/10.15587/1729-4061.2021.243735

Issue

Section

Mathematics and Cybernetics - applied aspects