An Effective Approach to Determine an Initial Basic Feasible Solution: A TOCM-MEDM Approach

Md. Munir Hossain¹, Mollah Mesbahuddin Ahmed², Md. Amirul Islam¹, Shirajul Islam Ukil¹

¹Department of Mathematics, Bangladesh Military Academy, Chattogram, Bangladesh.
²Principal, Birshreshtha Noor Mohammad Public College, Dhaka, Bangladesh.

DOI: 10.4236/ojop.2020.92003                

Abstract

Transportation of products from sources to destinations with minimal total cost plays an important role in logistics and supply chain management. In this article, a new and effective algorithm is introduced for finding an initial basic feasible solution of a balanced transportation problem. Number of numerical illustration is introduced and optimality of the result is also checked. Comparison of findings obtained by the new heuristic and the existing heuristics show that the method presented herein gives a better result.

Keywords

Initial Basic Feasible Solution, Total Opportunity Cost Matrix, Pointer Cost, Optimum Solution

1. Introduction

Transportation Problem (TP) is a special type of Linear Programming Problem (LPP). Transportation plan is mainly used to minimize transportation cost. Hitchcock [1] in 1941 presented a study entitled “The Distribution of a Product from Several Sources to Numerous Localities” which was the first formal contribution to the transportation problems. In 1947, Koopmans [2] presented a study called “Optimum Utilization of the Transportation System”. Systematic procedure for finding solution for TPs was developed, primarily by Dantzig [3] in 1951, and then by Charnes et al. [4] in 1953. The problem of minimizing transportation cost has been studied since long and is well known by Shenoy et al. (1991) [5], Kasana and Kumar (2005) [6], Hamdy (2007) [7], Pandian & Natarajan (2010) [8], Aminur Rahman Khan (2011; 2012) [9] [10], Sharif Uddin et al. (2011) [11], Md. Amirul Islam et al. (2012) [12], Sayedul Anam et al. (2012) [13], Md. Main Uddin et al. (2013b) [14], Mollah Mesbahuddin Ahmed et al. (2014) [15] [16], Utpal Kanti Das et al. (2014a; 2014b) [17] [18]. Several researchers have developed alternative methods for determining an initial basic feasible solution which takes costs into account. Well-known heuristics methods are North West Corner Method (NWCM), Matrix Minima Method (MMM), Vogel’s Approximation Method (VAM), Highest Cost Difference Method (HCDM), Extremum Difference Method (EDM), TOCM-MMM Approach, TOCM-VAM Approach, TOCM-EDM Approach, TOCM-HCDM Approach etc.

Reinfeld and Vogel (1958) [19] introduced VAM by describing penalty as the difference of lowest and next to lowest cost in each row and column of a transportation table and allocate to the lowest cost cell corresponding to the highest penalty. Kasana and Kumar (2005) [6] proposed EDM where they define the penalty as the difference of highest and lowest unit transportation cost in each row and column and allocate as like as the VAM procedure. Aminur Rahman Khan (2012) [10] presented HCDM by defining pointer cost as the difference of highest and next to highest cost in each row and column of a transportation table and allocate to the minimum cost cell corresponding to the highest three pointer cost. Sayedul Anam et al. (2012) [13] determine the impact of transportation cost on potato distribution in Bangladesh.

Kirca and Satir (1990) [20] first transform the cost matrix to the Total Opportunity Cost Matrix (TOCM). The TOCM is formed by adding the row opportunity cost matrix (ROCM) and the column opportunity cost matrix (COCM) where, for each row in the initial transportation cost matrix, the ROCM is generated by subtracting the lowest cost in the row from the other cost elements in that row and for each column in the initial transportation cost matrix, the COCM is generated by subtracting the lowest cost in the column from the other cost elements in that column. Kirca and Satir then essentially use the MMM with some tie-breaking rules on the TOCM to generate a feasible solution to the transportation problem.

Mathirajan and Meenakshi (2004) [21] applied VAM on the TOCM whereas Md. Amirul Islam et al. applied EDM on TOCM (2012) [22] and allocate to the minimum cost cell corresponding to the highest distribution indicator and again HCDM on TOCM (2012) and allocate to the minimum cost cell corresponding to the highest two distribution indicator. Aminur Rahman Khan et al. (2015) [23] obtain the pointer cost for each row and column of the TOCM by taking sum of all entries in the respective row or column and make maximum possible allocation to the lowest cost cell corresponding to the highest pointer cost.

Here in this article, the pointer cost has been calculated only one time by taking the difference between the highest and lowest cell cost for each row and column of the TOCM and make maximum possible allocation to the lowest cost cell corresponding to the highest pointer cost. It is to be mentioned that other allocation is obtained by Modified Extremum Difference Method without calculating the pointer cost time and again.

2. Mathematical Formulation of Transportation Problem

The Transportation Problem can be specified 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, $1\le i\le m$ and each destination has a demand of $b_j$ units, $1\le j\le n$. The objective is to determine which routes are to be opened and the size of the shipment on those routes, so that the total transportation cost of meeting demand, given the supply constraints, is minimized.

A transportation problem is a complete specification of how many units of the product should be transported from each source to each destination. So, the decision variables are:

$x_{ij}$ = The amount of the shipment from source i to destination j , where $i=1,2,\cdots ,m$ and $j=1,2,\cdots ,n$.

Therefore we get, Minimize: $Z={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}{x}_{ij}}}$.

3. Algorithm of Proposed Approach to Find an Initial Basic Feasible Solution

The proposed method named as “TOCM-MEDM Approach” comprises with the following steps:

4. Numerical Example with Illustration

4.1. Example-1

A company manufacture television and it has four factories $F_1$, $F_2$, $F_3$ and $F_4$ whose daily production capacities are 30, 25, 20 and 15 pieces of television respectively. The company supplies televisions to its four showrooms located at $D_1$, $D_2$, $D_3$ and $D_4$ whose daily demands are 30, 30, 20 and 10 pieces of television respectively. The transportation costs per piece of televisions are given in the transportation Table 1. Find out the schedule of shifting of television from factories to showroom with minimum cost.

4.2. Solution of Example-1

Iteration 1: In the first row 5 is the minimum element, so we subtract 5 from each element of the first row. Similarly, we subtract 3, 3 and 2 from each element of the 2nd, 3rd and 4th row respectively and place all the differences on the right-top of the corresponding elements in Table 1.

Iteration 2: In the similar way, we subtract 2, 3, 7 and 3 from each element of the 1st, 2nd, 3rd and 4th column respectively and place the result on the left-bottom of the corresponding elements in Table 1.

Iteration 3: The right-top and left-bottom entry of each element of the transportation table obtained in Iteration 1 and Iteration 2 is added and forms the TOCM as in Table 2.

Iteration 4: We determine the pointer cost for each row of the TOCM (Table 3) by taking the difference between the highest and the lowest cell cost in the respective row and write them in front of the row on the right [e.g. (14 − 2) = 12, (6 − 0) = 6, (10 − 1) = 9 and (7 − 0) = 7].

Table 1. Data of the Example-1.

Table 2. Formation of total opportunity cost matrix.

Table 3. Total opportunity cost matrix (TOCM).

Do the same for each column and place them in the bottom of the cost matrix below the corresponding columns [e.g. (7 − 0) = 7, (10 − 0) = 10, (10 − 5) = 5 and (14 − 1) = 13].

Iteration 5: In Table 4, maximum pointer cost is 13 and minimum transportation cost corresponding to this is 1 in the cell (4, 4). So we allocate min (15, 10) = 10 units to the cell (4, 4). We adjust the production capacity and demand requirements corresponding to the cell (4, 4) and since the demand is satisfied for the cell (4, 4), we crossed out 4th column.

Iteration 6: Now complete the allocation along 4th row by making the allocation in the smallest cost (0) in the cell (4, 1). Here 4th row is exhausted for the allocation min (30, 5) = 5 units at the cell (4, 1).

Iteration 7: In this stage, the allocation along 1st column will be in the smallest cost (1) which is at the cell (3, 1). By making the allocation of min (25, 20) = 20 units in the cell (3, 1) the 3rd row is crossed out but 1st column is yet to exhaust. Then we will go for next smallest cost along the 1st column corresponding to this is 3 in the cell (2, 1). Therefore 1st column is exhausted for the allocation min (25, 5) = 5 units at the cell (2, 1).

Iteration 8: In this case, we allocate min (30, 20) = 20 units along 2nd row in the smallest cost corresponding to this is 0 in the cell (2, 2). Since the production capacity is satisfied by the cells (2, 1) and (2, 2) then we crossed out 2nd row.

Iteration 9: Now complete the allocation along 2nd column by making the allocation in the smallest cost (2) in the cell (1, 2). Here 2nd column is exhausted for the allocation min (10, 30) = 10 units at the cell (1, 2).

Iteration 10: Since only the 1st row is remaining with one unallocated cell (1, 3), so we allocate rest 20 units to the cell (1, 3). Thereby in Table 5 we can see that all production capacity and demand values are exhausted.

Iteration 11: Now according to algorithm of Step 8, all these allocations are transferred to the original Transportation Table 1, which is shown in the Table 6. In this table it is observe that the numbers of basic cells are 7 i.e. (4 + 4 − 1) which represents the initial basic feasible solution according to the proposed algorithm.

Table 4. Initial basic feasible solution using TOCM-MEDM approach.

Table 5. Allocation on TOCM.

Table 6. Final allocation on original cost Table 1.

Iteration 12: Finally according to Step 9, for a flow of 90 units, total transportation cost is

$\left(10\times 5\right)+\left(20\times 9\right)+\left(5\times 4\right)+\left(20\times 3\right)+\left(20\times 3\right)+\left(5\times 2\right)+\left(10\times 3\right)=410$

5. Numerical Example without Illustration

5.1. Example-2

Consider the following transportation problem (Transportation Cost Table 7) comprising with three sources and five destinations. The cell entries represent the cost of transportation per unit. Obtain an initial basic feasible solution.

5.2. Solution of Example-2

After formulation and allocation on TOCM, we allocate the quantity on original cost table (i.e. Table 7) which is showed in Table 8.

Hence for the flow of 135 units, the total transportation cost is

$\left(45\times 1\right)+\left(15\times 2\right)+\left(18\times 2\right)+\left(17\times 2\right)+\left(22\times 3\right)+\left(5\times 2\right)+\left(13\times 4\right)=273$

5.3. Example-3

Consider that four products are produce in three machines and their per unit production costs are given in the following cost Table 9. Obtain an initial basic feasible solution for a suitable production plan which minimizes the total production cost.

5.4. Solution of Example-3

After formulation and allocation on TOCM, we allocate the quantity on original cost table (i.e. Table 9) which is showed in Table 10.

Hence for the flow of 1200 units, the total production cost is

$\left(300\times 1\right)+\left(250\times 2\right)+\left(150\times 5\right)+\left(50\times 3\right)+\left(250\times 3\right)+\left(200\times 2\right)=2850$

Table 7. Data of the Example-2.

Table 8. Final allocation on original cost Table 7.

Table 9. Data of the Example-3.

Table 10. Final allocation on original cost Table 9.

6. Result Analysis

The following Table 11 shows that the obtained result by our proposed TOCM-MEDM approach is compared with the results obtained by other existing methods and also with the optimal solution through the above three examples. The proposed method provides an initial basic feasible solution either optimal or too close to optimal for balanced transportation problem within less iteration, without making the calculation lengthy and time consuming. Comparative study shows that the proposed method gives better result in comparison to the other existing heuristics available in the literature.

7. Conclusions

The objective of the transportation problem is to determine the shipping schedule or supply route that minimizes the total shipping cost while satisfying the demand and supply limit. The proposed method can be one of the solution procedures to select this route.

Here in this article, we have used mainly two methods, the Extremum Difference Method (EDM) and Modified Extremum Difference Method (MEDM). Basically the proposed algorithm is set up by applying MEDM on TOCM. It is observed that the proposed method performs either same or better than EDM and MEDM. The uniqueness of this method is the computational procedure which is easier (less iteration) than the existing VAM, EDM, HCDM as the

Table 11. Comparison of the results.

penalty is required to find only for the first allocation. But in case of VAM, EDM and HCDM the penalty is needed to bring out for each and every allocation. By using the proposed method we conclude that we obtain an efficient and modified algorithm for finding an initial basic feasible solution which is optimal or close to optimal as compared to existing methods. It will help to calculate cost related to transportation which plays a vital role to minimize cost or maximize profit.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

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. https://doi.org/10.1002/sapm1941201224
[2]	Koopmans, T.C. (1947) Optimum Utilization of the Transportation System. Econometrica, 17, 3-4.
[3]	Dantzig, G.B. (1951) Application of the Simplex Method to a Transportation Problem. In: Koopmans, T.C., Ed., Activity Analysis of Production and Allocation, 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]	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.
[6]	Kasana, H.S. and Kumar, K.D. (2005) Introductory Operations Research: Theory and Applications. Springer International Edition, New Delhi.
[7]	Hamdy, A.T. (2007) Operations Research: An Introduction. 8th Edition, Pearson Prentice Hall, Upper Saddle River.
[8]	Pandian, P. and Natarajan, G. (2010) A New Approach for Solving Transportation Problems with Mixed Constraints. Journal of Physical Sciences, 14, 53-61.
[9]	Khan, A.R. (2011) A Re-Solution of the Transportation Problem: An Algorithmic Approach. Jahangirnagar University Journal of Science, 34, 49-62.
[10]	Khan, A.R. (2012) Analysis and Resolution of the Transportation Problem: An Algorithmic Approach. M. Phil. Thesis, Dept. of Mathematics, Jahangirnagar University, Jahangirnagar.
[11]	Sharif Uddin, M., 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.
[12]	Islam, Md.A., Khan, A.R., Sharif Uddin, M. and Abdul Malek, M. (2012) Determination of Basic Feasible Solution of Transportation Problem: A New Approach. Jahangirnagar University Journal of Science, 35, 101-108.
[13]	Anam, S., Khan, A.R., Haque, Md.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.
[14]	Uddin, Md.M., Rahaman, Md.A., Ahmed, F., Sharif Uddin, M. and Kabir, Md.R. (2013) Minimization of Transportation Cost on the Basis of Time Allocation: An Algorithmic Approach. Jahangirnagar Journal of Mathematics & Mathematical Sciences, 28, 47-53.
[15]	Ahmed, M.M., Tanvir, A.S.M., Sultana, S., Mahmud, S. and Uddin, Md.S. (2014) An Effective Modification to Solve Transportation Problems: A Cost Minimization Approach. Annals of Pure and Applied Mathematics, 6, 199-206.
[16]	Ahmed, M.M. (2014) Algorithmic Approach to Solve Transportation Problems: Minimization of Cost and Time. M. Phil. Thesis, Dept. of Mathematics, Jahangirnagar University, Jahangirnagar.
[17]	Das, U.K., Babu, Md.A., Khan, A.R. and Uddin, Md.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, 3, 182-187.
[18]	Das, U.K., Babu, Md.A., Khan, A.R., Helal, Md.A. and Uddin, Md.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, 3, 42-48.
[19]	Reinfeld, N.V. and Vogel, W.R. (1958) Mathematical Programming. Prentice-Hall, Englewood Cliffs.
[20]	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. https://doi.org/10.1057/jors.1990.124
[21]	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. https://doi.org/10.1142/S0217595904000333
[22]	Amirul, I., 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.
[23]	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. Universitatea Tehnică “Gheorghe Asachi” din Iasi Tomul LXI (LXV), Fasc. 1.