Scientific Research

An Academic Publisher

**Incessant Allocation Method for Solving Transportation Problems** ()

Keywords

Share and Cite:

*American Journal of Operations Research*,

**6**, 236-244. doi: 10.4236/ajor.2016.63024.

Received 3 April 2016; accepted 28 May 2016; published 31 May 2016

1. Introduction

Transportation Problem (TP) is one of the subclasses of Linear Programming Problems in which the objective is to transport various quantities of a single homogeneous commodity that are initially stored at various origins to different destinations in such a way that the total transportation cost is minimum. To achieve this objective we must know the amount and location of available supplies and the quantities demanded. In addition, we also know the unit transportation cost of the commodity to be transported from various origins to various destinations. Few examples of TP are summarized in Table 1 [1] .

Table 1. Examples of transportation problem.

Balanced transportation problems and unbalanced transportation problems are the types of TPs. If the sum of the supplies of all the sources is equal to the sum of the demands of all the destinations, the problem is termed as a balanced TP. On the other hand, the problem is termed as unbalanced TP. The basic steps for obtaining an optimum solution to a TP are:

・ Step 1: Mathematical formulation of the TP.

・ Step 2: Verify the TP: either it is balanced or unbalanced. If the problem is unbalanced, first balance it.

・ Step 3: Determine the Initial Basic Feasible Solution (IBFS).

・ Step 4: Verify the optimality condition of the IBFS. If the solution is not optimal, improve it for obtaining optimal solution.

The basic TP was first developed by Hitchcock [2] and then the systematic solution procedures from the simplex algorithm were further developed, primarily by Dantzig [3] and then by Charnes et al. [4] . In the solution procedure of TP, IBFS is known as the fundamental stage for finding an optimal solution. The well recognized classical methods, for finding an IBFS for the transportation problems are North West Corner Rule (NWCR) [5] [6] , Least Cost Method (LCM) [5] [6] and Vogel’s Approximation Method (VAM) [5] - [7] . Again researchers worked and are working on transportation problem to develop new algorithm to find a better IBFS for TPs [8] - [34] , and these methods may be used to solve maximization transportation problems [35] - [38] and also time minimization transportation problems [29] [39] - [41] . Like other researchers, in this paper an effective procedure for finding an IBFS for the cost minimizing TPs is proposed, and the proposed method is also used to solve profit maximization TP. Exceptionality and applicability of the method are also studied and explained in this study.

2. Tabular Form of Transportation Model

The tabular form of a TP is a matrix within a matrix shown in Table 2. Cost matrix is one of them that representing unit transportation cost c_{ij}, indicating the cost of shipping one unit from the i-th origin to the j-th destination. Super impose of this matrix is the matrix of transportation variable x_{ij}, indicating the amount shipped from i-th source to j-th destination. Right and bottom sides of the transportation table point out the amounts of supplies a_{i} available at source i and the amount demanded b_{j} at destination j.

3. Mathematical Formulation of Transportation Problem

The TP can be stated as an allocation problem in which there are m sources (suppliers) and n destinations (customers). Each of the m sources can allocate to any of the n destinations at a per unit carrying cost c_{ij} (unit transportation cost from source i to destination j). Each sources has a supply of a_{i} units, and each destination has a demand of b_{j} units,. The objective is to determine which routes are to be selected and the size of the shipment on those routes, so that the total transportation cost of meeting demand, given the supply constraints, is minimized. Hence the mathematical formulation of cost minimization TP is,

Minimize:

Subject to:

, for all i and j.

Table 2. Tabular form of transportation problem.

4. Illustration of the Proposed Method

In this research, allocations (from the first allocation to last allocation) in the cost cells are distributed in a continuous way, and for following this process, proposed method is named as “Incessant Allocation Method (IAM)” for Solving TP. Logical development of the proposed process for solving cost minimizing TP is illustrated below:

・ Step 1: Formulate the TP. For unbalanced problem, we do not require to balance the transportation problem.

・ Step 2: Find the smallest cost cell c_{ij} in the transportation table to make the first allocation. Allocate x_{ij} = min (a_{i}, b_{j}) in the cell (i, j). In case of ties, select the cell where maximum allocation can be allocated. Again in case of same cost cells and allocation select the cell for which sum of demand and supply is maximum in the original transportation table. Finally if all these are same, select the cell randomly.

・ Step 3: Adjust the supply and demand requirements in the respective rows and columns. Then following cases arise:

Case-1: If the allocation x_{ij} = a_{i}, i-th row is to be crossed out and b_{j} is reduced to (b_{j} - a_{i}). Now complete the allocation along j-th column by making the allocation/allocations in the smallest cost cell/cells continuously. Consider that, j-th column is exhausted for the allocation x_{kj} in the cell (k, j). Now, follow the same procedure to complete the allocation along k-th row and continue this process until entire rows and columns are exhausted.

Case-2: If the allocation x_{ij} = b_{j}, j-th column is to be crossed out and a_{i} is reduced to (a_{i} - b_{j}). Now by following the same procedure explained in case-1, complete the allocation along i-th row and continue the process until entire rows and columns are exhausted.

Case-3: If the allocation x_{ij} = a_{i} = b_{j}, find the next smallest cost cell, (i, k) from the rest of the cost cells along i-th row and j-th column. Assign a zero in the cell (i, k) and cross out i-th row and j-th column. After that complete the allocation along k-th column following the process described in Case-1 to complete the allocations.

Case-4: For any allocation, other than first allocation made along the row/column satisfies both the row and column. In such case find the smallest cost cell which is along the column/row and assign a zero in that cell and continue the process described in above cases to complete the allocation along the column/row and also to complete entire allocations.

・ Step-4: Finally calculate the total transportation cost which is the sum of the product of cost and corresponding allocated value.

5. Procedure for Solving Maximization Problem

There are some TPs where the objective is to maximize the profit rather than minimizing transportation cost is known as profit maximization TP. In the solution procedure of profit maximization TP, for finding an IBFS, allocations are to be made in highest profit cells, rather than in lowest cost cells. In this research proposed method has also been applied to solve the profit maximization TP.

6. Numerical Problems

In this research 15 problems are solved randomly from various literature and books only to analyze the perfectness and to justify the usefulness of the method. These problems and their IBFS obtained by IAM, are listed in the Tables 3-5 respectively.

Table 3. Cost minimization transportation problems (balanced problems).

Table 4. Cost minimization transportation problems (unbalanced problems).

Table 5. Profit maximization transportation problems.

6.1. Solution of a Problem with Illustration

Illustrative solution makes the theorem understandable to the readers. Considering this only the solution of BTP-4 from cost minimization TPs is illustrated, mathematical formulation of this problem is shown in Table 6.

Table 6. Tabular form of BTP-4.

Allocation of various cells of the above problem is shown in Table 7 and this is the IBFS for the problem:

Table 7. Initial basic feasible solution of BTP-4.

・ First Allocation: Allocate 60 = min (60, 95) in the cell (6, 5) which is the smallest cost cell among all the cost cells of BTP-4. Cross out the 6-th row as this allocation satisfies this row and along 5-th column, the demand is reduced to 35 = (95 - 60).

・ Second Allocation: Now the smallest cost cell along 5-th column is 2 appears in the cell (5, 5) and allocate the reduced demand 35 in this cell. In this case 5-th column is exhausted and the supply along 5-th row is reduced to 65 = (100 - 35).

・ By following the same procedure Third Allocation is 65 in the cell (5, 3). Fourth Allocation is 75 in the cell (2, 3). Fifth Allocation is 5 in the cell (2, 4). Sixth Allocation is 35 in the cell (4, 4). Seventh Allocation is 55 in the cell (4, 2), Eighth Allocation is 30 in the cell (1, 2). Ninth Allocation is 65 in the cell (1, 6). Tenth allocation is 25 in the cell (1, 1) and the final allocation is 50 in the cell (3, 1) are made.

・ Finally total transportation cost is,

7. Exceptionality of Proposed Method

This research finds two exceptionalities which are as follows:

・ This method does not require balancing an unbalanced transportation problem for finding an initial solution.

・ This method always yields an initial basic feasible solution for the balanced transportation problems.

7.1. Explanation of the Second Exceptionality

In the balanced TP, for an allocation either a single row or a single column is exhausted except the final allocation. If both of the row and column are exhausted for a single allocation, one zero is assigned to make the number of allocations equal to the number of row and column. Only the final allocation exhausted both the row and column together. Now for m × n transportation matrix the number of allocating cells are to be [(m + n − 2) + 1] = (m + n − 1). According to the definition of IBFS, this ensures the starting/initial solution is a basic feasible solution for the balanced TPs.

8. Result and Analysis

In this research, classical TP methods for finding an IBFS are studied in details. Hamdy A. Taha’s TORA software is used in order to find the IBFS for the methods (NWCR, LCM and VAM) and to find the optimal result. Again the initial result for the IAM is calculated manually. Finally various mathematical comparisons between the results obtained by existing methods, and IAM are shown in the Tables 8-11.

Table 8. Cost minimization transportation problems (balanced problems).

Table 9. Cost minimization transportation problems (unbalanced problems).

Table 10. Profit maximization transportation problems.

Table 11. Comparison of average of PoCIR and grand average of PoCIR.

In the comparisons mainly the initial result obtained by various methods are shown. The percentage of correctness is calculated by using the formula [% of correctness = 100 − {(initial result − optimal result) * 100/optimal result)}] for cost minimization TPs. Again, for the profit maximization transportation problems this percentage is obtained by the formula [% of correctness = 100 − {(optimal result − initial result) * 100/optimal result}]. This result is studied only to evaluate the obtained IBFS is numerically either equal to optimal result or nearer to optimal result. During this process it is observed that in most of the cases IBFS obtained by IAM is numerically optimal or nearer to optimal value.

Again average of PoCIR for each types of cost minimizing TP (balanced, unbalanced) and profit maximization TP is also studied to analyze the performance of IAM for finding IBFS. For each type of problems, it is found that this percentage for IAM is remarkably better than NWCR and LCM and parallel to the percentage obtained by VAM.

We also calculate GAPoCIR to justify the general performance of the method, which is shown in Figure 1. This figure ensures the feasibility of IAM for solving any types of TP.

Figure 1. Comparison of GAPoCIR.

Finally we acknowledge that, VAM as well as IAM yields a better IBFS for the TPs. Again computational procedure of IAM is easier than VAM. Hence from this discussion IAM can be claim an effective process for finding an IBFS.

9. Conclusion

The aim of any industry is to transport goods from sources to destinations with minimum cost. Minimization of transportation cost is one of the main objectives to maximize the profit. In this article, we propose an efficient procedure for finding an IBFS for minimizing transportation cost. Methodical evaluation of the proposed method is also carried out for both the balanced and unbalanced TPs. We also use this method in solving profit maximization TPs to justify its applicability in all types of TPs. It is also observed that our method is usually resulting in minimal and maximal values respectively for cost minimizing TPs and profit maximization TPs. Finally the proposed method presented in this paper claims its wide application in solving TPs.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | Panneerselvam, R. (2010) Operation Research. 2nd Edition, PHI Learning Private Ltd., New Delhi, 71. |

[2] |
Hitchcock, F.L. (1941) The Distribution of a Product from Several Sources to Numerous Localities. Journal of Mathematics and Physics, 20, 224-230. http://dx.doi.org/10.1002/sapm1941201224 |

[3] | Dantzig, G.B. (1951) Application of the Simplex Method to a Transportation Problem, Activity Analysis of Production and Allocation. Koopmans, T.C., Ed., John Wiley and Sons, New York, 359-373. |

[4] | Charnes, A., Cooper, W.W. and Henderson, A. (1953) An Introduction to Linear Programming. John Wiley & Sons, New York. |

[5] | Hamdy, A.T. (2007) Operations Research: An Introduction. 8th Edition, Pearson Prentice Hall, Upper Saddle River. |

[6] | Ray, G.C. and Hossain, M.E. (2007) Operation Research. Bangladesh, 103-104. |

[7] | Reinfeld, N.V. and Vogel, W.R. (1958) Mathematical Programming. Prentice-Hall, Englewood Cliffs. |

[8] | Rashid, A., Ahmed, S.S. and Uddin, M.S. (2013) Development of a New Heuristic for Improvement of Initial Basic Feasible Solution of a Balanced Transportation Problem. Jahangirnagar University Journal of Mathematics and Mathematical Sciences, 28, 105-112. |

[9] | Mhlanga, A., Nduna, I.S., Matarise, F. and Machisvo, A. (2014) Innovative Application of Dantzig’s North-West Corner Rule to Solve a Transportation Problem. International Journal of Education and Research, 2, 1-12. |

[10] | Khan, A.R. (2011) A Re-Solution of the Transportation Problem: An Algorithmic Approach. Jahangirnagar University Journal of Science, 34, 49-62. |

[11] | Khan, A.R. (2012) Analysis and Re-Solution of the Transportation Problem: A Linear Programming Approach. M.Phil. Thesis, Jahangirnagar University, Savar. |

[12] | Khan, A.R., Vilcu, A., Sultana, N. and Ahmed, S.S. (2015) Determination of Initial Basic Feasible Solution of a Transportation Problem: A TOCM-SUM Approach. Buletinul Institutului Politehnic Din Iasi, Romania, Sec?ia Automatica si Calculatoare, LXI (LXV), 39-49. |

[13] | Khan, A.R., Vilcu, A., Uddin, M.S. and Ungureanu, F. (2015) A Competent Algorithm to Find the Initial Basic Feasible Solution of Cost Minimization Transportation Problem. Buletinul Institutului Politehnic Din Iasi, Romania, Sec?ia Automatica si Calculatoare, LXI (LXV), 71-83. |

[14] | Khan, A.R., Banerjee, A., Sultana, N. and Islam, M.N. (2015) Solution Analysis of a Transportation Problem: A Comparative Study of Different Algorithms. Accepted for Publication in the Bulletin of the Polytechnic Institute of Iasi, Romania, Section Textile. |

[15] | Deshmukh, N.M. (2012) An Innovative Method for Solving Transportation Problem. International Journal of Physics and Mathematical Sciences, 2, 86-91. |

[16] |
Russell, E.J. (1969) Letters to the Editor—Extension of Dantzig’s Algorithm to Finding an Initial Near-Optimal Basis for the Transportation Problem. Operations Research, 17, 187-191. http://dx.doi.org/10.1287/opre.17.1.187 |

[17] | Kasana, H.S. and Kumar, K.D. (2005) Introductory Operations Research: Theory and Applications. Springer International Edition, New Delhi. |

[18] | 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. |

[19] | Uddin, M.S., Anam, S., Rashid, A. and Khan, A.R. (2011) Minimization of Transportation Cost by Developing an Efficient Network Model. Jahangirnagar Journal of Mathematics & Mathematical Sciences, 26, 123-130. |

[20] |
Mathirajan, M. and Meenakshi, B. (2004) Experimental Analysis of Some Variants of Vogel’s Approximation Method. Asia-Pacific. Asia-Pacific Journal of Operational Research, 21, 447-462.
http://dx.doi.org/10.1142/S0217595904000333 |

[21] | Amirul Islam, M.D., Khan, A.R., Uddin, M.S. and Abdul Malek, M. (2012) Determination of Basic Feasible Solution of Transportation Problem: A New Approach. Jahangirnagar University Journal of Science, 35, 101-108. |

[22] | Islam, M.A., Haque, M.H. and Uddin, M.S. (2012) Extremum Difference Formula on Total Opportunity Cost: A Transportation Cost Minimization Technique. Prime University Journal of Multidisciplinary Quest, 6, 125-130. |

[23] | Babu, M.A., Helal, M.A., Hasan, M.S. and Das, U.K. (2013) Lowest Allocation Method (LAM): A New Approach to Obtain Feasible Solution of Transportation Model. International Journal of Scientific and Engineering Research, 4, 1344-1348. |

[24] | Babu, M.A., Das, U.K., Khan, A.R. and Uddin, M.S. (2014) A Simple Experimental Analysis on Transportation Problem: A New Approach to Allocate Zero Supply or Demand for All Transportation Algorithm. International Journal of Engineering Research & Applications (IJERA), 4, 418-422. |

[25] | Babu, M.A., Helal, M.A., Hasan, M.S. and Das, U.K. (2014) Implied Cost Method (ICM): An Alternative Approach to Find the Feasible Solution of Transportation Problem. Global Journal of Science Frontier Research-F: Mathematics and Decision Sciences, 14, 5-13. |

[26] | Uddin, M.M., Khan, A.R., Roy, S.K. and Uddin, M.S. (2015) A New Approach for Solving Unbalanced Transportation Problem due to Additional Supply. Accepted for Publication in the Bulletin of the Polytechnic Institute of Iasi, Section Textile, Leather Ship, Romania. |

[27] | Hasan, M.K. (2012) Direct Methods for Finding Optimal Solution of a Transportation Problem are Not Always Reliable. International Refereed Journal of Engineering and Science (IRJES), 1, 46-52. |

[28] | Ahmed, M.M., Tanvir, A.S.M., Sultana, S., Mahmud, S. and Uddin, M.S. (2014) An Effective Modification to Solve Transportation Problems: A Cost Minimization Approach. Annals of Pure and Applied Mathematics, 6, 199-206. |

[29] | Ahmed, M.M. (2014) Algorithmic Approach to Solve Transportation Problems: Minimization of Cost and Time. M. Phil. Thesis, Department of Mathematics, Jahangirnagar University, Savar, Dhaka, Bangladesh. |

[30] |
Ahmed, M.M., Khan, A.R., Uddin, M.S. and Ahmed, F. (2016) A New Approach to Solve Transportation Problems. Open Journal of Optimization, 5, 22-30. http://dx.doi.org/10.4236/ojop.2016.51003 |

[31] | Pandian, P. and Natarajan, G. (2010) A New Approach for Solving Transportation Problems with Mixed Constraints. Journal of Physical Sciences, 14, 53-61. |

[32] |
Wagener, U.A. (1965) A New Method of Solving the Transportation Problem. Journal of the Operational Research Society, 16, 453-469. http://dx.doi.org/10.1057/jors.1965.80 |

[33] | Das, U.K., Babu, M.A., Khan, A.R., Helal, M.A. and Uddin, M.S. (2014) Logical Development of Vogel’s Approximation Method (LD-VAM): An Approach to Find Basic Feasible Solution of Transportation Problem. International Journal of Scientific & Technology Research (IJSTR), 3, 42-48. |

[34] | Das, U.K., Babu, M.A., Khan, A.R. and Uddin, M.S. (2014) Advanced Vogel’s Approximation Method (AVAM): A New Approach to Determine Penalty Cost for Better Feasible Solution of Transportation Problem. International Journal of Engineering Research & Technology (IJERT), 3, 182-187. |

[35] | Rashid, A., Uddin, M.S., Ahmed, F. and Kabir, M.R. (2012) An Effective Approach for Profit Maximization in a Transportation Problem. Jahangirnagar University Journal of Science, 35, 37-43. |

[36] | Rashid, A., Ahmed, S.S. and Uddin, M.S. (2014) A New Approach for Profit Maximization in an Assignment Problem. Jahangirnagar University Journal of Science, 37, 107-117. |

[37] | Islam, M.A., Uddin, M.S., Hasan, S.M.M., Rashid, F. and Malek, M.A. (2013) Profit Maximization of a Manufacturing Company: An Algorithmic Approach, Jahangirnagar Journal of Mathematics & Mathematical Sciences, 28, 29-37. |

[38] | Islam M.A., Ahmed, M.M., Uddin, M.S. and Malek, M.A. (2013) Application of a New Transportation Algorithm on Profit Maximization Problem. MIST Journal of Science and Technology, 2, 67-71. |

[39] | Uddin, M.S. (2012) Transportation Time Minimization: An Algorithmic Approach. Journal of Physical Sciences, 16, 59-64. |

[40] | Uddin, M.M., Rahaman, M.A., Ahmed, F., Uddin, M.S. and Kabir, M.R. (2013) Minimization of Transportation Cost on the Basis of Time Allocation: An Algorithmic Approach. Jahangirnagar Journal of Mathematics & Mathematical Sciences, 28, 47-53. |

[41] |
Ahmed, M.M., Islam, M.A., Katun, M., Yesmin, S. and Uddin, M.S. (2015) New Procedure of Finding an Initial Basic Feasible Solution of the Time Minimizing Transportation Problems. Open Journal of Applied Sciences, 5, 634-640.
http://dx.doi.org/10.4236/ojapps.2015.510062 |

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.