Solution of Transportation Problem with South-East Corner Method, North-East Corner Method and Comparison with Existing Method

Show more

1. Introduction

Transportation problem is famous in operation research for its wide application in real life. The transportation problem is one of the sub-classes of linear programming problems. The objective of Transportation Problem is to transport various amounts of a single homogeneous commodity that are initially stored in various origins and from there to different destinations in such a way that the total transportation cost is a minimum. The transportation problem received this name because many of its applications involved in determining how to optimally transport goods. Transportation problem is a logistical problem for organizations especially for manufacturing and transport companies.

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: Optimizing 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. 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) [4] , Least Cost Method (LCM) [4] , Vogel’s Approximation Method (VAM) [4] [5] , Balakrishnan [6] etc. Then in the next and last stage MODI (Modified Distribution) method was adopted to get an optimal solution. Charnes and Cooper [3] also developed a method for finding an optimal solution from IBFS named as “Stepping Stone Method”.

Recently, R. A. Lakshmi and P. L. Pallavi [7] , Vinoba and Palaniyappa [8] , Alfred Asase [9] , Francois Ndayiragije [10] proposed different methods to obtain initial basic feasible solutions.

In this paper, we introduce the South East Corner Method and North East Corner Methods used to obtain 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 show that the proposed methods give better result in comparison to the other existing methods available in the literature.

2. Network Representation and Mathematical Formulation of the 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.

In developing the Linear Programming model of a transportation problem the following notations are used

Transportation problem

$\text{Min}Z={\displaystyle \underset{i=1}{\overset{m}{\sum}}{\displaystyle \underset{j=1}{\overset{n}{\sum}}{C}_{ij}{X}_{ij}}}$

Subject to $\underset{j=1}{\overset{n}{\sum}}\text{\hspace{0.17em}}{x}_{ij}\le {S}_{i},\text{}i=1,2,\cdots ,m$

$\underset{i=1}{\overset{m}{\sum}}\text{\hspace{0.17em}}{x}_{ij}\ge {D}_{j},\text{}j=1,2,\cdots ,n$

and x_{ij} ≥ 0, for all i and j.

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.

Feasible solution: A set of non negative values x_{ij}, i = 1, 2, …, n and j = 1, 2, …, m that satisfies the constraints is called a feasible solution to the transportation problem.

Optimal solution: A feasible solution is said to be optimal if it minimizes the total transportation cost.

Non degenerate basic feasible solution: A basic feasible solution to a (m × n) transportation problem that contains exactly m + n - 1 allocations in independent positions.

3. Proposed Methods to Obtain Initial Basic Feasible Solution

3.1. South East Corner Method

The steps involved in solving the transportation problem using south east corner method is given below.

Step 1: Draw the general transportation problem table and verify that the problem is balanced.

Step 2: The method starts at the south east corner cell of the table (variable (x_{mn}).

Step 3: Allocate as much as possible to the selected cell and adjust the associated amounts of supply and demand by subtracting the allocated amount.

Step 4: Cross out the row or column with zero supply or demand to indicate that no further assignments can be made in that row or column. If both a row and column net to zero simultaneously, cross out one only and leave a zero supply (demand in the uncrossed out row-column).

Step 5: If exactly one row or column is left uncrossed out, stop. Otherwise, move to the cell to the right if a column has just been crossed out. Go to step 3.

3.2. North East Corner Method Procedure

The steps involved in solving the transportation problem using north east corner method are given below.

Step 1: The method starts at the North east corner cell of the tableau (variable X1n).

Step 2: Allocate as much as possible to the selected cell and adjust the associated amounts of supply and demand by subtracting the allocated amount.

Step 3: Cross out the row or column with zero demand to indicate that no further assignments can be made in the row or column. If both row and column net to zero simultaneously cross out one only and leave a zero supply (demand in the uncrossed out row or column).

Step 4: If exactly one row or column is left uncrossed out or below if exactly one row or column is left uncrossed out, stop. Otherwise, move to the cell to the right if a column has just been crossed out or below if a row has been crossed out. Go to step 1.

Step 5: Start with X1n and end at Xm1.

3.3. Vogel’s Approximation Method (VAM)

The Vogel approximation method is an iterative procedure for computing a basic feasible solution of the transportation problem.

Step 1: Identify the boxes having minimum and next to minimum transportation cost in each row and write the difference (penalty) along the side of the table against the corresponding row.

Step 2: Identify the boxes having minimum and next to minimum transportation cost in each column and write the difference (penalty) against the corresponding column.

Step 3: Identify the maximum penalty. If it is along the side of the table, make maximum allotment to the box having minimum cost of transportation in that row. If it is below the table, make maximum allotment to the box having minimum cost of transportation in that column.

Step 4: If the penalties corresponding to two or more rows or columns are equal, select the top most row and the extreme left column.

Step 5: Continue the procedure until the total available quantity if fully allocated to the cells as required.

3.4. Test for Optimality

Once an initial solution is obtained, the next step is to check its optimality. An optimal solution is one where there is no other set of transportation routes (allocations) that will further reduce the total transportation cost. Thus, we have to evaluate each unoccupied cell (represents unused route) in the transportation table in terms of an opportunity of reducing total transportation cost. An unoccupied cell with the largest negative opportunity cost is selected to include in the new set of transportation routes (allocations). This is also known as an incoming variable. The outgoing variable in the current solution is the occupied cell (basic variable) in the unique closed path (loop) whose allocation will become zero first as more units are allocated to the unoccupied cell with largest negative opportunity cost. Such an exchange reduces total transportation cost. The process is continued until there is no negative opportunity cost. That is, the current solution cannot be improved further. This is the optimal solution. An efficient technique called the modified distribution (MODI) method (also called U-V Method). Now we discuss MODI method which gives optimal solution and is shown in below.

Modified Distribution (MODI) Method

Step 1: Determine an initial basic feasible solution using any one of the methods which are namely, North West Corner Method, Least Cost Method and Vogel’s Approximation Method.

Step 2: Determine the values of dual variables, U_{i} and V_{j} using U_{i} + V_{j} = C_{ij}.

Step 3: Compute the opportunity cost using d_{ij} = C_{ij} - (U_{i} + V_{j}) from unoccupied cell.

Step 4: Check the sign of each opportunity cost (d_{ij}). If the opportunity costs of all the unoccupied cells are either positive or zero, the given solution is the optimum solution. On the other hand, if one or more unoccupied cell has negative opportunity cost, the given solution is not an optimum solution and further savings in transportation cost are possible.

Step 5: Select the unoccupied cell with the smallest negative opportunity cost as the cell to be included in the next solution.

Step 6: Draw a closed path or loop for the unoccupied cell selected in the previous step. Please note that the right angle turn in this path is permitted only at occupied cells and the original unoccupied cell.

Step 7: Assign alternate plus and minus signs at the unoccupied cells on the corner points of the closed path with a plus sign at the cell being evaluated.

Step 8: Determine the maximum number of units that should be shipped to this unoccupied cell. The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell. Now, add this quantity to all the cells on the corner points of the closed path marked with plus signs and subtract it from those cells marked with minus signs. In this way an unoccupied cell becomes an occupied cell.

Step 9: Repeat the whole procedure until an optimum solution is obtained.

4. Numerical Examples with Illustration

4.1. Example

A company has three warehouses, W_{1}, W_{2} and W_{3}, which are supplied by three suppliers, S_{1}, S_{2} and S_{3}. The table shows the cost C_{ij} of sending one case of goods from supplier Si to warehouse W_{j}_{,} in appropriate units. Also shown in the table are the number of cases available at each supplier and the number of cases required at each warehouse.

Consider the following balanced transportation problem.

4.1.1. South East Corner Method

By applying South East Corner Method the allocations are obtained as follows:

It is a balanced transportation problem as $\underset{j=1}{\overset{n}{\sum}}{a}_{i}}={\displaystyle \underset{i=1}{\overset{m}{\sum}}{b}_{j}}=30.$

1) At the beginning we have a matrix of order 3X3, firstly we choose the south east corner cell of the table (x_{33}), i.e., from (3, 3) cell. Here min (S_{3}, W_{3}) = min (6, 12) = 6 units. Therefore the maximum possible units that can be allocated to this cell is 6 and it as 6 (7) in the cell (3, 3). This completes the allocation in the 3^{rd} row and cross the other cells, i.e., (3, 1) and (3, 2) in the row.

2) After completion of step.1 come to cell (2, 3) here min (10, 12 − 6 = 6) = 6 units can be allocated to the cell and write it as 6 (8). This completes the allocation in the 3^{rd} column and cross the other cells in that column.

3) Now come to second column, here the cell (2, 2) is min (10 − 6 = 4, 10) = 4 units can be allocated to this cell and write it as 4 (5). This completes the allocations in second row so cross the other cells in that row.

4) Again consider the position (1, 2). Here min (14, 10 − 4 = 6) = 6 units can be allocated to this cell and write it as 6 (4). This completes the allocations in second column.

5) Finally, allocate the remaining units to the cell (1, 1), i.e., 8 units to this cell and write it as 8 (10).

6) All allocations done in the above tables and complete the table as follows:

From the above table the initial basic feasible solution is given by X_{11} = 8, X_{12} = 6, X_{22} = 4, X_{23} = 6, X_{33} = 6.

The total cost associated with these allocations = 10 × 8 + 4 × 6 + 5 × 4 + 8 × 6 + 7 × 6 = 214.

4.1.2. North East Corner Method

By applying North East Corner Method the allocations are obtained as follows:

The initial basic feasible solution is given by X_{12} = 2, X_{13} = 12, X_{21} = 2, X_{22} = 8, X_{31} = 6.

The total cost associated with these allocations = 4 × 2 + 11 × 12 + 12 × 2 + 5 × 8 + 9 × 6 = 258.

4.1.3. Vogel’s Approximation Method (VAM Method) (Existing Method)

To find the initial basic feasible solution for the above example Vogel’s approximation method is used and allocations are obtained as follows:

By applying VAM process allocations are obtained as follows:

The initial basic feasible solution is given by X_{11} = 4, X_{12} =10, X_{23} = 10, X_{31} = 4, X_{33} = 2.

The total cost associated with these allocations = 10 × 4 + 4 × 10 + 8 × 10 + 9 × 4 + 7 × 2 = 210.

4.1.4. Optimal Solution Using MODI Method

Finding U_{i} and V_{j} values from occupied cells

Here we find U_{i} and V_{j} values by assuming U_{1} = 0 then we will find remaining U_{i} and V_{j} values.

From the occupied cells (U_{i} + V_{j} = C_{ij}).

U_{1} = 0;

U_{1} + V_{1} = 10 U_{1} + V_{2} = 4 U_{3} + V_{1} = 9 U_{3} + V_{3} = 7 U_{2} + V_{3} = 8.

0 + V_{1} = 10 0 + V_{2} = 4 U_{3} + 10 = 9 −1 + V_{3} = 7 U_{2} + 8 = 8.

V_{1} = 10 V_{2} = 4 U_{3} = 9 − 10 = −1 V_{3} =7 + 1 = 8 U_{2} = 0.

U_{1} = 0; U_{2} = 0; U_{3} = −1; V_{1} = 10; V_{2} = 4; V_{3} = 8.

Finding d_{ij} = C_{ij} − (U_{i} + V_{j}) for unoccupied cells

d_{13} = C_{13} − (U_{1} + V_{3}) = 11 − (0 + 8) = 3.

d_{21} = C_{21} − (U_{2} + V_{1}) = 12 − (0 + 10) = 2.

d_{22} = C_{22} − (U_{2} + V_{2}) = 5 − (0 + 4) = 1.

d_{32} = C_{32} − (U_{3} + V_{2}) = 6 − (−1 + 4) = 3.

Here U_{i} + V_{j} values of each unoccupied cell are showing in the cell of top right corner value and d_{ij} values are in down right corner of each cell. All d_{ij} values are positive we get optimal solution.

So, the total cost associated with these allocations = 10 × 4 + 4 × 10 + 8 × 10 + 9 × 4 + 7 × 2 = 210.

To get optimal solution MODI (Modified Distribution) method is adopted and by applying MODI method the optimal solution is obtained as 210.

4.2. Example

Consider the transportation problem given by the following table of supply, demand and unit costs.

4.2.1. South East Corner Method

By applying south east corner rule process allocations are obtained as follows:

The initial basic feasible solution is given by X_{11} = 40, X_{21} = 30, X_{22} = 20, X_{32} = 30, X_{33} = 30.

The total cost associated with these allocations = 10 × 40 + 4 × 30 + 5 × 20 + 8 × 30 + 6 × 30 = 1040.

4.2.2. North East Corner Method

By applying North East Corner Method the allocations are obtained as follows:

The initial basic feasible solution is given by X_{12} = 10, X_{13} = 30, X_{21} = 10, X_{22} = 40, X_{31} = 60.

The total cost associated with these allocations = 12 × 10 + 9 × 30 + 4 × 10 + 5 × 40 + 11 × 60 = 1290.

4.2.3. VAM Method

To find the initial basic feasible solution for the above example Vogel’s approximation method is used and allocations are obtained as follows:

The total cost associated with these allocations = 10 × 20 + 9 × 20 + 4 × 50 + 8 × 50 + 6 × 10 = 1040.

4.2.4. Optimal Solution Using MODI Method

Here all d_{ij}’s are positive, we get optimal solution.

The total cost associated with these allocations = 10 × 20 + 9 × 20 + 4 × 50 + 8 × 50 + 6 × 10 = 1040.

5. Result Analysis

It can be shown that the value obtained by South-East Corner Method, North-East Corner Method is near to the optimal solution and also by the North-East Corner Method is not nearer to the optimal solution which obtained by MODI method(optimal solution). Since the South-East Corner Method is better initial solution than the North-East Corner Method.

6. Conclusion

In this paper, we gave the SECM and NECM which are new methods used to obtain initial basic feasible solutions in transportation problem and compared with Vogel’s approximation and Modified Distribution Method (existing) for optimal solution. Thus, it can be concluded that South-East Corner Method provides an optimal solution directly or in fewer iterations and North-East Corner Method gives an optimal solution for more iterations, for the transportation problems. So South-East Corner Method takes less time and easy to apply for the decision makers who are dealing with logistic and supply chain problems.

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] Dantzig, G.B. (1951) Application of the Simplex Method to a Transportation Problem, Activity Analysis of Production and Allocation. 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] Hamdy, A.T. (2007) Operations Research: An Introduction. 8th Edition, Pearson Prentice Hall, Upper Saddle River.

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

[6] Balakrishnan, N. (1990) Modified Vogel’s Approximation Method for Unbalanced Transportation Problem. Applied Mathematics Letters, 3, 9-11.

https://doi.org/10.1016/0893-9659(90)90003-T

[7] Lakshmi, R.A. and Pallavi, P.L. (2015) A New Approach to Study Transportation Problem Using South West Corner Rule. International Journal of Advanced Research Foundation, 2, 1-3.

[8] Vinoba, V. and Palaniyappa, R. (2014) A Study on North East Corner Method in Transportation Problem and Using of Object Oriented Programming Model (C++). International Journal of Mathematics Trends and Technology, 16, 1-8.

[9] Asase, A. (2011) The Transportation Problem; Case Study. A Thesis Submitted to the Department of Mathematics Faculty of Physical Science and Technology, Kumasi, 7 June 2011.

[10] Ndayiragije, F. (2017) South-East Corner Method and a Comparative Study on the North-West Corner, South-East Corner, North-East Corner and South-East Corner Methods. International Journal of Science and Engineering Investigations, 6, 37-39.