A New Approach to Solve Transportation Problems

Mollah Mesbahuddin Ahmed^*, Aminur Rahman Khan, Md. Sharif Uddin, Faruque Ahmed

Department of Mathematics, Jahangirnagar University, Dhaka, Bangladesh.

DOI: 10.4236/ojop.2016.51003                

Abstract

Finding an initial basic feasible solution is the prime requirement to obtain an optimal solution for the transportation problems. In this article, a new approach is proposed to find an initial basic feasible solution for the transportation problems. The method is also illustrated with numerical examples.

Keywords

Transportation Problem, Transportation Cost, Initial Basic Feasible Solution, Optimal Solution

Received 24 November 2015; accepted 1 March 2016; published 4 March 2016

1. Introduction

Transportation problem is famous in operation research for its wide application in real life. This is a special kind of the network optimization problems in which goods are transported from a set of sources to a set of destinations subject to the supply and demand of the source and destination, respectively, such that the total cost of transportation is minimized. The basic transportation problem was originally developed by Hitchcock in 1941 [1] . Efficient methods for finding solution were developed, primarily by Dantzig in 1951 [2] and then by Charnes, Cooper and Henderson in 1953 [3] . Basically, the solution procedure for the transportation problem consists of the following phases:

・ Phase 1: Mathematical formulation of the transportation problem.

・ Phase 2: Finding an initial basic feasible solution.

・ Phase 3: Optimize the initial basic feasible solution which is obtained in Phase 2.

In this paper, Phase 2 has been focused in order to obtain a better initial basic feasible solution for the transportation problems. This problem has been studied since long and is well known by Abdur Rashid et al. [4] , Aminur Rahman Khan et al. [5] -[8] , Hamdy A. T. [9] , Kasana & Kumar [10] , Kirca and Satir [11] , M. Sharif Uddin et al. [12] , Mathirajan, M. and Meenakshi [13] , Md. Amirul Islam et al. [14] [15] , Md. Ashraful Babu et al. [16] -[18] , Md. Main Uddin et al. [19] [20] , Mollah Mesbahuddin Ahmed et al. [21] -[23] , Pandian & Natarajan [24] , Reinfeld & Vogel [25] , Sayedul Anam et al. [26] , Shenoy et al. [27] and Utpal Kanti Das et al. [28] [29] .

Again, some of the well reputed methods for finding an initial basic feasible solution of transportation problems developed and discussed by them are North West Corner Method (NWCM) [9] , Row Minimum Method (RMM) [6] [26] , Column Minimum Method (CMM) [6] [26] , Least Cost Method (LCM) [9] , Vogel’s Approximation Method (VAM) [9] [24] , Extremum Difference Method (EDM) [10] , Highest Cost Difference Method (HCDM) [5] [6] , Average Cost Method (ACM) [4] , TOCM-MMM Approach [11] , TOCM-VAM Approach [13] , TOCM-EDM Approach [15] , TOCM-HCDM Approach [14] , TOCM-SUM Approach [7] etc.

In this paper, a new algorithm is proposed to find an initial basic feasible solution for the transportation problems. A comparative study is also carried out by solving a good number of transportation problems which shows that the proposed method gives better result in comparison to the other existing heuristics available in the literature.

2. Network Representation and Mathematical Model of Transportation Problem

Generally the transportation model is represented by the network in Figure 1. There are m sources and n destinations, each represented by a node. The arcs represent the routes linking the sources and destinations. Arc (i, j) joining source i to destination j carries two pieces of information: the transportation cost per unit, c_ij and the amount shipped, x_ij. The amount of supply at source i is S_i, and the amount of demand at destination j is d_j. The objective of the model is to determine the unknowns’ x_ij that will minimize the total transportation cost while satisfying the supply and demand restrictions.

Figure 1. Network representation of transportation problem.

Considering the above notations, the transportation problem can be stated mathematically as a linear programming problem as:

Minimize:.

Subject to: ;.

;.

for all and.

The objective function minimizes the total cost of transportation (Z) between various sources and destinations. The constraint i in the first set of constraints ensures that the total units transported from the source i is less than or equal to its supply. The constraint j in the second set of constraints ensures that the total units transported to the destination j is greater than or equal to its demand.

3. Proposed Approach to Find an Initial Basic Feasible Solution

In the proposed approach, an allocation table is formed to find the solution for the transportation problem. That’s why this method is named as Allocation Table Method (ATM) and the method is illustrated below:

・ Step-1: Construct a Transportation Table (TT) from the given transportation problem.

・ Step-2: Ensure whether the TP is balanced or not, if not, make it balanced.

・ Step-3: Select minimum odd cost (MOC) from all the cost cells of TT. If there is no odd cost in the cost cells of the TT, keep on dividing all the cost cells by 2 (two) till obtaining at least an odd value in the cost cells.

・ Step-4: Form a new table which is to be known as allocation table (AT) by keeping the MOC in the respective cost cell/cells as it was/were, and subtract selected MOC only from each of the odd cost valued cells of the TT. Now all the cell values are to be called as allocation cell value (ACV) in AT.

・ Step-5: At first, start the allocation from minimum of supply/demand. Allocate this minimum of supply/ demand in the place of odd valued ACVs at first in the AT formed in Step-4. If demand is satisfied, delete the column. If it is supply, delete the row.

・ Step-6: Now identify the minimum ACV and allocate minimum of supply/demand at the place of selected ACV in the AT. In case of same ACVs, select the ACV where minimum allocation can be made. Again in case of same allocation in the ACVs, choose the minimum cost cell which is corresponding to the cost cells of TT formed in Step-1 (i.e. this minimum cost cell is to be found out from the TT which is constructed in Step-1). Again if the cost cells and the allocations are equal, in such case choose the nearer cell to the minimum of demand/supply which is to be allocated. Now if demand is satisfied delete the column and if it is supply delete the row.

・ Step-7: Repeat Step-6 until the demand and supply are exhausted.

・ Step-8: Now transfer this allocation to the original TT.

・ Step-9: Finally calculate the total transportation cost of the TT. This calculation is the sum of the product of cost and corresponding allocated value of the TT.

4. Numerical Examples with Illustration

4.1. Example-1

A company manufactures motor cars and it has three factories F₁, F₂ and F₃ whose weekly production capacities are 300, 400 and 500 pieces of cars respectively. The company supplies motor cars to its four showrooms located at D₁, D₂, D₃ and D₄ whose weekly demands are 250, 350, 400 and 200 pieces of cars respectively. The transportation costs per piece of motor cars are given in the transportation Table 1. Find out the schedule of shifting of motor cars from factories to showrooms with minimum cost:

Table 1. Data of the Example-1.

4.1.1. Solution of Example 1 and Its Explanation

Allocation of various cells in the allocation table for Example-1 is shown in Allocation Table 2.

Table 2. Allocation of various cells are in the allocation table.

・ According to Step-2: It is found that the given problem is balanced. Because of the sum of supplies = sum of the demands = 1200.

・ As per Step-3, minimum odd cost is 1 in cost cell (1, 2) among all the cost cells of the Transportation Table 1.

・ Allocation Table 2, is formed according to Step-4, where minimum odd cost is in cell (1, 2) remains same, but this odd cost is subtracted from all other odd valued cost cells of the transportation Table 1. Like in cost cell (1, 1) it is 3 in Transportation Table 1, but in allocation table this cell value is 2 = (3 − 1).

・ According to Step-5, minimum supply/demand is 300 that is allocated in cell (1, 2). After allocating this value it is found that the supply is satisfied. For which F₁ row is to be exhausted.

・ After Step-5, only the cells of F₂ and F₃ rows are to be considered. Where 2 is the lowest cell value in the cells (2, 1), (3, 2), (3, 3) and (3, 4). Among these four cells 50 is the lowest allocation can be made in cell (3, 2). Now column D₂ is crossed out after allocating this amount.

・ Again it is found 2 is the lowest cell value in the remaining cells which appears in the cells (2, 1), (3, 3) and (3, 4). Among these three cells, minimum allocation 200 is made in cell (3, 4). So the cells of column D₄ are not to be considered for further calculation.

・ After doing the above allocation, it is found 2 is again the minimum cell value that appears in the cells (2, 1) and (3, 3). In both of these cells 250 is the minimum allocation can be made. But in between these two cells, it is found that the minimum cost cell appears in the cell (2, 1) in the Transportation Table 1, so the minimum allocation 250 is allocated in cell (2, 1). Now column D₁ is to be exhausted.

・ Finally complete the allocation by allocating 250 and 150 in the cells (3, 3) and (2, 3) respectively. All these allocations are made according to Step-6 and Step-7 of the proposed algorithm.

・ Now according to Step-8, all these allocations are transferred to the Transportation Table 1, which is shown in the Final Allocation Table 3. In this table it is found that the number of basic cells are 6 (=4 + 3 − 1) which represents the initial basic feasible solution according to the proposed algorithm.

Table 3. Initial basic feasible solution according to ATM.

・ Finally according to the Step-9, total transportation cost is (300 × 1 + 250 × 2 + 150 × 5 + 50 × 3 + 250 × 3 + 200 × 3) = 2850.

4.2. Example-2

Consider the following transportation problem (Transportation Table 4) involving three sources and four destinations. The cell entries represent the cost of transportation per unit. Obtain an initial basic feasible solution.

Table 4. Data of the Example-2.

4.2.1. Solution of Example 2 and Its Explanation

From the Transportation Table 4, it is seen that total supply and total demand are equal. Hence the given transportation problem is a balanced one. Now it is found all the cell values are even number in the Transportation Table 4. So according to the Step-3 of proposed algorithm, these cells values are to be continuously divided by 2 until obtain at least an odd value in the cost cells. The obtaining cell values, after dividing each of the cell values by 2 of the transportation Table 4 for the first time is shown in Table 5.

Table 5. All the cost cells of Example-2 are divided by 2.

・ Allocation of various cells in the allocation table for Example 2 is shown in Allocation Table 6.

Table 6. Allocation of various cells are in the allocation table.

・ As per Step-3, minimum odd cost is 15 in cost cell (3, 3) among all the cost cells of Table 5.

・ Allocation Table 6, is formed according to Step-4, where minimum odd cost is in cell (3, 3) remains same, but this odd cost is subtracted from all other odd valued cost cells of Table 5.

・ According to Step-5, minimum supply/demand is 16 that is allocated in cell (3, 3). After allocating this value it is found that the supply is satisfied. Hence F₃ row is crossed out.

・ After Step-5, only F₁ and F₂ rows are to be considered, where 10 is the lowest cell value among the remaining cells, which appears in the cells (1, 1), (1, 4) and (2, 4). Among these three cells 10 is the lowest allocation is made in the cell (1, 1). For this allocation column D₁ to be exhausted.

・ After the above allocation, again it is found 10 is the minimum cell value that appears in the cells (1, 4) and (2, 4). In these two cells 10 and 24 are the allocations can be made. But according to the proposed algorithm 10 is the minimum allocation between these two allocations which is made in the cell (1, 4). This allocation satisfies the supply of F₁ row and this row is not to be considered for further allocation.

・ Now complete the allocation by allocating 14, 6 and 18 respectively to the cells (2, 4), (2, 3) and (2, 2). All these allocations are made according to Step-6 and Step-7 of the proposed algorithm.

・ Now according to Step-8, all these allocations are transferred to the Transportation Table 4, which is shown in the Final Allocation Table 7. Where it is found that the number of basic cells are 6 (=4 + 3 − 1) which represents the initial basic feasible solution according to the proposed algorithm.

Table 7. Initial basic feasible solution according to ATM.

・ Finally according to the Step-9, total transportation cost is (10 × 50 + 10 × 50 + 18 × 40 + 6 × 70 + 14 × 50 + 16 × 30) = 3320.

5. Numerical Examples without Illustration

5.1. Example-3

Consider the following transportation problem (Transportation Table 8) involving four sources and four

destinations. The cell entries represent the cost of transportation per unit. Obtain an initial basic feasible solution.

Table 8. Data of the Example-3.

5.1.1. Solution of Example-3

Initial basic feasible solution according to the proposed algorithm is shown in the Final Allocation Table 9.

Table 9. Initial basic feasible solution according to ATM.

・ Hence the total transportation cost is (5 × 7 + 5 × 5 + 20 × 9 + 25 × 3 + 20 × 3 + 5 × 2 + 10 × 3) = 415.

5.2. Example-4

Consider the following transportation problem (Transportation Table 10) involving three origins and three destinations. The cell entries represent the cost of transportation per unit. Obtain an initial basic feasible solution.

Table 10. Data of the Example-4.

5.2.1. Solution of Example-4

Initial basic feasible solution according to the proposed algorithm is shown in the Final Allocation Table 11.

Table 11. Initial basic feasible solution according to ATM.

・ Hence, the total transportation cost is (90 × 3 + 30 × 5 + 50 × 4 + 70 × 8 + 30 × 7) = 1390.

6. Result Analysis

After obtaining an IBFS by the proposed “Allocation Table Method (ATM)”, the obtained result is compared with the results obtained by other existing methods is shown in Table 12.

Table 12. Comparison of the results obtained by various methods.

As observed from Table 12, the proposed allocation table method provides comparatively a better initial basic feasible solution than the results obtained by the traditional algorithms which are either optimal or near to optimal. Again the performance of the solution varies for other methods which may happen also in case of the proposed method. It happens because it is quite difficult to assume a prior which of the methods will result in the best solution.

7. Conclusions

In today’s highly competitive market, various organizations want to deliver products to the customers in a cost effective way, so that the market becomes competitive. To meet this challenge, transportation model provides a powerful framework to determine the best ways to deliver goods to the customer.

In this article, a new approach named allocation table method (ATM) for finding an initial basic feasible solution of transportation problems is proposed. Efficiency of allocation table method has also been tested by solving several number of cost minimizing transportation problems and it is found that the allocation table method yields comparatively a better result.

Finally it can be claimed that the allocation table method may provide a remarkable Initial Basic Feasible Solution by ensuring minimum transportation cost. This will help to achieve the goal to those who want to maximize their profit by minimizing the transportation cost.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	Dantzig, G.B. (1951) Application of the Simplex Method to a Transportation Problem, Activity Analysis of Production and Allocation. In: Koopmans, T.C., Ed., John Wiley and Sons, New York, 359-373.
[3]	Charnes, A., Cooper, W.W. and Henderson, A. (1953) An Introduction to Linear Programming. John Wiley & Sons, New York.
[4]	Rashid, A., Ahmed, S.S. and Uddin, Md.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.
[5]	Khan, A.R. (2011) A Re-Solution of the Transportation Problem: An Algorithmic Approach. Jahangirnagar University Journal of Science, 34, 49-62.
[6]	Khan, A.R. (2012) Analysis and Re-Solution of the Transportation Problem: A Linear Programming Approach. M.Phil. Thesis, Department of Mathematics, Jahangirnagar University.
[7]	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, Sectia Automatica si Calculatoare, Tomul LXI (LXV), Fasc. 1, 39-49.
[8]	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. Leathership.
[9]	Hamdy, A.T. (2007) Operations Research: An Introduction. 8th Edition, Pearson Prentice Hall, Upper Saddle River.
[10]	Kasana, H.S. and Kumar, K.D. (2005) Introductory Operations Research: Theory and Applications. Springer International Edition, New Delhi.
[11]	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.
[12]	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.
[13]	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. http://dx.doi.org/10.1142/S0217595904000333
[14]	Islam, M.A., Khan, A.R., Uddin, M.S. and Malek, M.A. (2012) Determination of Basic Feasible Solution of Transportation Problem: A New Approach. Jahangirnagar University Journal of Science, 35, 101-108.
[15]	Islam, M.A., Haque, M. 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.
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	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. Bulletin of the Polytechnic Institute of Iasi, Romania, Section Textile, Leathership. (In Press)
[21]	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.
[22]	Ahmed, M.M. (2014) Algorithmic Approach to Solve Transportation Problems: Minimization of Cost and Time. M. Phil. Thesis, Dept. of Mathematics, Jahangirnagar University, Savar.
[23]	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
[24]	Pandian, P. and Natarajan, G. (2010) A New Approach for Solving Transportation Problems with Mixed Constraints. Journal of Physical Sciences, 14, 53-61.
[25]	Reinfeld, N.V. and Vogel, W.R. (1958) Mathematical Programming. Prentice-Hall, Englewood Cliffs.
[26]	Anam, S., Khan, A.R., Haque, M.M. and Hadi, R.S. (2012) The Impact of Transportation Cost on Potato Price: A Case Study of Potato Distribution in Bangladesh. The International Journal of Management, 1, 1-12.
[27]	Shenoy, G.V., Srivastava, U.K. and Sharma, S.C. (1991) Operations Research for Management. 2nd Edition, New Age International (P) Limited Publishers, New Delhi.
[28]	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.
[29]	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.