Development of a heuristic to solve the general transportation problem
DOI:
https://doi.org/10.15587/1729-4061.2021.243735Keywords:
transportation problem, Sew-Saw rule, linear programming, transportation simplex methodAbstract
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
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
How to Cite
Issue
Section
License
Copyright (c) 2021 Elias Munapo
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
