Operations Management - Transportation Problems

 

Transportation Problems – Introduction

 

Transportation models deals with the transportation of a product manufactured at different plants or factories (supply origins) to a number of different warehouses (demand destinations). The objective is to satisfy the destination requirements within the plants’ capacity constraints at the minimum transportation cost. Transportation models thus typically arise in situations involving physical movement of goods from plants to warehouses, warehouses to wholesalers, wholesalers to retailers and retailers to customers. Solution of the transportation models requires the determination of how many units should be transported from each supply origin to each demands destination in order to satisfy all the destination demands while minimizing the total associated cost of transportation.

Transportation Tableau

Origin (i)	Destination (j)				Supply, ai
	1	2	***	n
1	X11 C11	X12 C12	***	X1n C1n	a1
2	X21 C21	X22 C22	***	X2n C2n	a2
***	***	***	***	***	***
m	Xm1 Cm1	Xm2 Cm2	***	Xmn Cmn	am
Demand, bj	b1	b2	***	bn	∑ai = ∑bj

 

 Here,

ai	=  Quantity of product available at origin i
bj	=  Quantity of product required at destination j
Cij	=  Cost of transporting one unit of product from        origin i to destination j
Xij	=  Quantity transported from origin i to destination j
m	=  Number of origins
n	=  Number of destinations

 

Basic Feasible Solution

If X_ij > 0, X_ij are called basic variables and if X_ij = 0, X_ij are called non-basic variables. Cells containing basic variables are called occupied cells, whereas cells containing non-basic variables are called empty cells or unoccupied cells. A basic feasible solution of a transportation problem has exactly (m + n – 1) basic variables, which means that the number of occupied cells in such a solution is exactly (m + n – 1). It may happen sometimes that the number of occupied cells is less than (m + n – 1). Such a solution is called a degenerate solution.

 

Steps to solve a transportation problem

A transportation problem can be solved in three steps as follows:

Step 1: Obtaining the initial basic feasible solution.

Step 2: Testing the optimality.

Step 3: Improving the solution.

 

Step 1: Obtaining the initial basic feasible solution

The initial basic feasible solution can be obtained by several methods. The commonly used methods among them are:

1. North-West Corner Method (NWCM);

2. Least Cost Method (LCM); and

3. Vogel’s Approximation Method (VAM)

 

North-West Corner Method (NWCM)

This method may be stated as follows:

Start with the north-west corner of the transportation tableau and consider the cell in the first column and first row. Corresponding to this cell are the values a₁ and b₁ respectively in roe 1 and column 1. Proceed as follows:

If a₁ > b₁, then assign quantity b₁ in this cell. This implies that we put X₁₁ = b₁. But, if a₁ < b₁, then assign quantity a₁ in the cell so that X₁₁ = a₁. Simply speaking put lower of a₁ and b₁ as X₁₁. If a₁ = b₁, then X₁₁ = a₁ = b₁.

 

Now, if a₁ > b₁, then move horizontally to the next column in the first row; if a₁ < b₁, then move vertically in the same column to the next row; and if a₁ = b₁, then move diagonally to the next column and next row.

Once in the next cell, again compare the supply available at the source and demand at the destination, corresponding to the cell chosen, and assign lower of the two values. Move to the next cell appropriately as explained earlier and again assign the quantity considering demand and available supply.

 

Continue the procedure until the last source and last destination are covered, so that south-east corner of the tableau is reached.

 

Least Cost Method (LCM)

As the name suggests, of all the routes (i.e. combinations of sources and destinations) select the one where shipping cost (i.e. transportation cost) is the least. Now, consider the supply available at the corresponding source and demand at the corresponding destination and put the lower of the two as the quantity to be transported through that route. After this, delete the source / destination, whichever is satisfied. Consider the remaining routes and again choose the one with the smallest cost and make assignments. Continue in this manner until all the units are assigned.

 

It may be mentioned that at any stage, if there is a tie in the minimum cost, so that two or more routes have the same least cost of shipping, then, conceptually, either of them may be selected. However, a better initial solution is obtained if the route chosen is the one where the largest quantity can be assigned. Thus, if there are three cells for which the least cost value is equal, then consider each one of these one by one and determine the quantity (by reference to the demand and supply quantities given) which can be despatched, and choose the cell with the largest quantity. If there is still a tie, then either of them may be selected.

 

Vogel’s Approximation Method (VAM)

1.     First, consider each row of the cost matrix individually and find the difference between two least cost cells in it. Then repeat the exercise for each of the columns.

2.     Identify the column or row with the largest difference value.

3.     Now, consider the cell with the minimum cost in that column (or row, as the case may be) and assign the maximum possible units, looking to the demand and availability corresponding to that cell.

4.     In case of a tie in the largest cost difference, although either of them may be chosen, it is preferable to choose the cost difference corresponding to which the largest number of units may be assigned or corresponding to which the cell with the minimum cost may be chosen.

5.     Delete the column/row which has been satisfied.

6.     Again, find out the cost differences and proceed in the same manner as discussed above from Point: 1 to Point: 5.

7.     Continue until all the units have been assigned.

 

Step 2: Testing the optimality

After obtaining the initial basic feasible solution, the next step is to test whether it is optimal or not. There are two methods of testing the optimality of a basic feasible solution:

1.     Stepping-stone method, and

2.     Modified distribution method (MODI).

 

Modified distribution method (MODI)

STEPS:

1.     Add to the transportation tableau a column on the right hand side titled u_i and a row in the bottom of it titled v_j.

2.     Assign any value arbitrarily to a row or column variable u_i or v_j. Generally, a value 0 (zero) is assigned to the first row, i.e. u₁ = 0.

3.     Find out other u-values and v-values such that for all the occupied cells of all the rows and columns c_ij = u_i + v_j.

4.     Find out opportunity costs (Δ_ij) of all the unoccupied cells of all the rows and columns such that Δ_ij = u_i + v_j – c_ij.

5.     If all the unoccupied (empty) cells have negative opportunity costs, the solution is optimal and unique.

6.     If some empty cell(s) has a zero opportunity cost but if none of the other empty cells have positive opportunity cost, then it implies that the current solution is optimal but not unique i.e. there exists other solution(s) that would be as good as the current solution.

7.     If, however, the solution contains a positive opportunity cost for one or more of the empty cells, the solution is not optimal.

 

Step 3: Improving the solution

1.     In a situation where the solution is not optimal, the cell with the largest opportunity cost is selected, a closed loop is traced and transfers of units along the route are made in accordance with the method discussed in the note “Transportation Problems - Closed Loop”. Then the resulting solution is again tested for optimality and improved, if necessary. The process is repeated until an optimal solution is obtained.

 

2.     In a situation where the solution is optimal but not unique i.e. there exists other alternative optimal solution(s), to obtain an alternative optimal solution, a closed loop beginning with an empty cell having Opportunity Cost (Δ_ij) = 0 is traced, and the revised optimal solution in the same way as in Step 3(1) above is obtained. It may be observed that this revised optimal solution would also entail the same total cost as before, as in the case of the original optimal solution. Here, it should be understood and noted that for every empty cell having Opportunity Cost (Δ_ij) = 0 in the optimal solution, an alternative optimal solution can be obtained.

Transportation Problems – Degeneracy

 

A basic feasible solution of a transportation problem has (m + n – 1) basic variables, which means that the number of occupied cells in such a solution is one less than the number of rows plus the number of columns. It may happen sometimes that the number of occupied cells is less than (m + n – 1). Such a solution is called a degenerate solution.

 

The problem, when a solution is degenerate, is that it cannot be tested for optimality. Both, the stepping stone method and the modified distribution method (MODI) are inoperative in such a case.

 

To overcome the problem, an infinitesimally small amount, close to zero, is assigned to one (or more if the need be) empty cell and treat the cell as an occupied cell. This amount is represented by a Greek letter ε (epsilon) and is taken to be such an insignificant value that would not affect the total cost.

 

Although ε is, theoretically, non-zero, the operations with it in the context of transportation problem are as follows:

K + ε	=	K
K − ε	=	K
0 + ε	=	ε
ε + ε	=	ε
ε − ε	=	0
K × ε	=	0

 

When the initial basic feasible solution is degenerate, we assign ε to an independent empty cell. An independent cell is the one (originating) from which a closed loop cannot be traced. A ε may be assigned to any of the independent cells but preferably to one with the minimum per unit cost. After introducing epsilon(s) in the requisite and appropriate cell(s), we solve the problem in the usual manner.

Transportation Problems – Closed Loop

 

[How to locate or identify a closed loop in a transportation problem in order to shifting the allocations for minimising the total transportation cost?]

 

1.         Start with an empty cell (usually the cell with the largest opportunity cost as per the MODI method of optimality test) and move clockwise. Draw an arrow from the empty cell to an occupied cell in the same row or column.

2.         After that, move vertically or horizontally to another occupied cell and draw an arrow.

3.         Follow the same procedure to other occupied cells before returning to the original empty cell.

4.         Move from one occupied cell to another only vertically or horizontally, but never diagonally. Step over empty or occupied cells, if required.

5.         A closed loop will always have right-angled turns with corners only on the occupied cells.

6.         Place “+” or “−“signs alternately in the cells on each turn of the loop, beginning with a “+” sign in the empty cell where the loop started. There must be exactly one cell with a “+” sign and one cell with a “−“sign in any row or column of the loop.

7.         At least 4 cells must participate in a closed loop. But the number of cells participating in a closed loop must always be even. An occupied cell can be considered for a closed loop only once, not more.

8.         All cells that receive “+” or “−“sign, except the starting empty cell, must be the occupied cells.

9.         Closed loops may or may not be square or rectangular in shape. In large transportation problems, a closed loop may even cross over itself.

10.     Finally, to obtain a revised solution, consider cells with “−“signs and determine the least of the quantities (x_ij) assigned to each of these cells. Add this quantity to the cells bearing “+” signs and subtract from cells bearing “−“signs.

Transportation Problems – Some Special Cases

 

Unbalanced Transportation Problems

For solving transportation problems it is required that the aggregate supply (∑a_i) is equal to the aggregate demand (∑b_j). But in practice, situations may arise when the two are not equal. The different possibilities may be

1.     When the aggregate supply exceeds the aggregate demand (i.e. ∑a_i > ∑b_j), and

2.     When the aggregate supply falls short of the aggregate demand (i.e. ∑a_i < ∑b_j).

Transportation problems having these situations are called unbalanced transportation problems. Balancing must be done before such problems can be solved.

 

When the aggregate supply exceeds the aggregate demand, the excess supply is assumed to go to inventory costing nothing for shipping. A column of slack variables is added to the transportation tableau which represents a dummy destination with a requirement (i.e. demand) equal to the amount of excess supply and the transportation costs equal to zero. On the other hand, when the aggregate demand exceeds the aggregate supply in a transportation problem, balance is restored by adding a dummy origin. A row representing the dummy origin is added with an assumed total availability equal to the difference between the total demand and total supply, each of the cells of the dummy row having a zero unit cost. In some cases, however, when the penalty of not satisfying the demand of a particular destination(s) is given, such penalty value should be considered for the respective cell(s) of the dummy row and not the zero unit cost.

 

Once the transportation problem is balanced, its solution will proceed in exactly the same manner as discussed earlier.

 

Prohibited Routes

Sometimes in a given transportation problem some route(s) may not be available. This could be due to a variety of reasons like the unfavourable weather conditions on a particular route, strike on a particular route, etc. In such situations, there is a restriction on the routes available for transportation. To handle a situation of this type, a very large cost represented by ‘M’ is assigned to each of such routes which are not available. Then the problem is solved in the usual way.

 

The effect of adding a large cost element would be that such routes would automatically be eliminated in the final solution.

 

Unique vs Multiple Optimal Solutions

The optimal solution to a given transportation problem may, or may not, be unique. As we know, the solution to a transportation problem is optimal, if all the Δ_ij values (under the MODI method of testing the optimality) are less than, or equal to zero. For a given solution, if all the Δ_ij values are negative, then it is unique. If, however, some cell (or cells) has Δ_ij = 0, then multiple optimal solutions can be obtained involving the same total cost.

 

To obtain an alternative optimal solution, trace a closed loop beginning with a cell having Δ_ij = 0, and get the revised solution in the same way as a solution is improved. It may be observed that this revised solution would also entail the same total cost as before. In the same way, for every ‘zero’ value of Δ_ij value in the optimal solution table, a revised solution can be obtained.

 

Maximisation Problem

The classical transportation problem is one of the minimisation types. However, a transportation table may contain unit profits instead of unit costs and the objective function may be the maximisation of total profit. In such and other maximisation types of problems, the transportation method is applied as in the case of the minimisation type of problems, except with the difference that in the first stage all the values of the profit matrix are subtracted from the highest profit value in the matrix. Once this is done and the optimal solution is obtained as for the minimisation problems, the value of the objective function is determined with reference to the original profit matrix.

 

It is to be remembered, however, that if a maximisation type transportation problem is unbalanced, then it should be balanced by introducing the necessary dummy row/column for a source/destination, before converting it into a minimisation type problem. Similarly, if such a maximisation type transportation problem has a prohibited route, then the payoff element for such a route should be substituted by (−M) before proceeding to convert it into a minimisation type problem.