Abstract
The transportation problem (TP) is discussed in all operational research textbooks. Although the TP can be formulated as a linear programme, owing to its special structure, it can be solved more efficiently than just using the standard simplex algorithm. Typically, the first step in solving a TP is to ‘balance’ the problem. If total supply is not equal to total demand, then a dummy column (supply greater than demand) or dummy row (demand greater than supply) is created. Although a few papers have discussed the importance of how the dummy column (row) is handled, this has been done only with reference to using one particular heuristic (Vogel's approximation method or VAM). Furthermore, the impact on solution quality based on how a heuristic processes the dummy column or row has not been empirically quantified. The closer an initial heuristically determined basic feasible solution is to the optimal solution, the fewer the required iterations of the modified transportation simplex to determine the optimal solution. The purpose of this article is to empirically quantify the importance of how five TP heuristics (northwest corner method, the greedy heuristic, VAM, Russell's method and the maximum demand method) process the dummy column (row) in a balanced TP.
Similar content being viewed by others
References
Bertsekas, D.P. (1991) Linear Network Optimization Algorithms and Codes. Cambridge, MA: MIT Press.
Gass, S.I. (1990) On solving the transportation problem. Journal of the Operational Research Society 41: 291–297.
Glover, F., Karney, D., Klingman, D. and Napier, A. (1974) A computation study on start procedures, basis change criteria, and solution algorithms for transportation problems. Management Science 20: 793–813.
Goyal, S.K. (1984) Improving VAM for unbalanced transportation problems. Journal of the Operational Research Society 35: 1113–1114.
Hillier, F.S. and Lieberman, G.J. (2010) Introduction to Operations Research, 9th edn. New York: McGraw-Hill.
Kirca, O. and Satir, A. (1990) A heuristic for obtaining an initial solution for the transportation problem. Journal of the Operational Research Society 41: 865–871.
Mathirajan, M. and Meenakshi, B. (2004) Experimental analysis of some variants of Vogel's approximation method. Asia-Pacific Journal of Operational Research 21: 447–462.
Pargar, F., Javadian, N. and Ganji, A.P. (2009) A heuristic for obtaining an initial solution for the transportation problem with experimental analysis. The 6th International Industrial Engineering Conference, Sharif University of Technology, Tehran, Iran.
Ramakrishnan, C.S. (1988) An improvement to Goyal's modified VAM for the unbalanced transportation problem. Journal of the Operational Research Society 39: 609–610.
Reinfeld, N.V. and Vogel, W.R. (1958) Mathematical Programming. Englewood Cliffs, NJ: Prentice-Hall.
Russell, E.J. (1969) Extension of Dantzig's algorithm to finding an initial near-optimal basis for the transportation problem. Operations Research 17: 187–191.
Storozhyshina, N., Pargar, F. and Vasko, F.J. (2011) A comprehensive empirical analysis of 16 heuristics for the transportation problem. OR Insight 24: 63–76.
Vasko, F.J., Creggar, M.L., Stott, K.L. and Woodyatt, L.R. (1994) Optimal assignments of slabs to orders: an example of appropriate model formulation. Computers & Industrial Engineering 26: 797–800.
Winston, W.L. (2004) Operations Research: Applications and Algorithms. Belmont, CA: Thomson.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vasko, F., Storozhyshina, N. Balancing a transportation problem: Is it really that simple?. OR Insight 24, 205–214 (2011). https://doi.org/10.1057/ori.2011.6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/ori.2011.6