Transportation Problem

Submitted by: Mrs. Kajal Puri (Asstt. Prof. in PG department of Commerce and Management)

​

OUTLINE

• Introduction

​

• Solution Procedure for Transportation Problem

• Finding an Initial Feasible Solution

• Finding the Optimal Solution

• Special Cases in Transportation Problems

• Maximisation in Transportation Problems

• Exercises

The main typical issues in OR :

​

• Formulate the problem

​

• Build a mathematical model
• Decision Variable
• Objective Function
• Constraints

​

• Optimize the model

​

OPERATION RESEARCH

Transportation models deal can be formulated as a standard LP problem. Typical situation shown in the manufacturer example

​

• Manufacturer has three plants P₁, P₂, P₃ producing same products.
• From these plants, the product is transported to three warehouses

W₁, W₂ and W₃.

• Each plant has a limited capacity, and each warehouse has specific

demand. Each plant transport to each warehouse, but transportation

cost vary for different combinations.

​

The problem is to determine the quantity each warehouse in order to minimize total transportation costs.

Introduction

SOLUTION PROCEDURE FOR TRANSPORTATION PROBLEM

• Conceptually, the transportation is similar to simplex method.
• Begin with an initial feasible solution.

This initial feasible solution may or may not be optimal. The only way you can find it out is to test it.

• If the solution is not optimal, it is revised and the test is repeated. Each iteration should bring you closer to the optimal solution.

The format followed in the above table will be used throughout the unit.

• Each row corresponds to a specific plant and each column corresponds to a specific warehouse.
• Plant supplies are shown to the right of the table and warehouse requirements are shown below the table.
• The larger box (also known as cells) at the intersection of a specific row and column will contain both quantity to be transported and per unit transportation cost.
• The quantity to be transported will be shown in the centre of the box and will be encircled and the per unit transportation cost is shown in the smaller rectangular box at the left hand side corner.

Solution Procedure for Transportation Problem

Finding an Initial Feasible Solution

There are a number of methods for generating an initial feasible solution for a transportation problem.

​

Consider three of the following

(i) North West Corner Method

(ii) Least Cost Method

(iii) Vogel’s Approximation Method

NORTH WEST CORNER METHOD (NWCM)

The simplest of the procedures used to generate an initial feasible solution is NWCM. It is so called because we begin with the North West or upper left corner cell of our transportation table. Various steps of this method can be summarised as under.

Step 1

Select the North West (upper left-hand) corner cell of the transportation table and allocate as many units as possible equal to the minimum between available supply and demand requirement i.e., min (S₁, D₁).

Step 2

Adjust the supply and demand numbers in the respective rows

And columns allocation.

Step 3

1. If the supply for the first row is exhausted, then move down to the first cell in t he second row and first column and go to step 2.

​

(b) If the demand for the first column is satisfied, then move

horizontally to the next cell in the second column and first

row and go to step 2.

​

If for any cell, supply equals demand, then the next allocation can be made in cell either in the next row or column.

Step 4

Step 5

Continue the procedure until the total available quantity id fully allocated to the cells as required.

Remark 1: The quantities so allocated are circled to indicated, the value of the corresponding variable.

Remark 2: Empty cells indicate the value of the corresponding variable as zero, I.e., no unit is shipped to this cell.

To illustrate the NWCM,

​

As stated in this method, we start with the cell (P₁ W₁) and Allocate the min (S₁, D₁) = min (20,21)=20. Therefore we allocate 20 Units this cell which completely exhausts the supply of Plant P₁ and leaves a balance of (21-20) =1 unit of demand at warehouse W₁

Now, we move vertically downward to cell (P2 W1) At this stage the largest allocation possible is the (S₂, D₁ –20) =min (28, 1)= 1. This allocation of 1 unit to the cell (P1 W2). Since the demand of warehouse W2 is 25 units while supply available at plant P2 is 27 units, therefore, the min (27-5) = 25 units are located to the cell (P₁ W₂). The demand of warehouse W2 is now satisfied and a balance of (27-225) = 2 units of supply remain at plant P2. Moving again horizontally, we allocated two units to the cell (P2 W3) Which Completely exhaust the supply at plant P2 and leaves a balance of 17 units to this cell (P3, W3).. At this, 17 Units ae availbale at plant P3 and 17 units are required at warehouse W3. So we allocate 17 units to this cell (P3, W3). Hence we have made all the allocation. It may be noted here that there are 5 (+3+1) allocation which are necessary to proceed further. The initial feasible solution is shown below. The Total transportation cost for this initial solution is

​

Total Cost = 20x7 +1 X 5 + 25 x 7 + 2 X 3 + 17 + 8 = Rs. 462

LEAST COST METHOD

The allocation according to this method is very useful as it takes into consideration the lowest cost and therefore, reduce the computation as well as the amount of time necessary to arrive at the optimal solution.

​

Step 1

1. Select the cell with the lowest transportation cost among all the rows or columns of the transportation table.
2. If the minimum cost is not unique, then select arbitrarily any cell with this minimum cost.

Step 2

Allocate as many units as possible to the cell determined in Step 1 and eliminate that row (column) in which either supply is exhausted or demand is satisfied.

Repeat Steps 1 and 2 for the reduced table until the entire supply at different plants is exhausted to satisfied the demand at different warehouses.

VOGEL’S APPROXIMATION METHOD (VAM)

This method is preferred over the other two methods because the initial feasible solution obtained is either optimal or very close to the optimal solution.

Step 1:

Compute a penalty for each row and column in the transportation table.

Step 2:

Identify the row or column with the largest penalty.

Step 3:

Repeat steps 1 and 2 for the reduced table until entire supply at plants are exhausted to satisfy the demand as different warehouses.

FINDING THE OPTIMAL SOLUTION

Once an initial solution has been found, the next step is to test that solution for optimality. The following two methods are widely used for testing the solutions:

• Stepping Stone Method
• Modified Distribution Method

​

The two methods differ in their computational approach but give exactly the same results and use the same testing procedure.

STEPPING-STONE METHOD

In this method we calculate the net cost change that can be obtained by introducing any of the unoccupied cells into the solution.

​

The Stepping Stone Method

1. Make sure that the number of occupied cells is exactly equal to m=n-1, where m=number of rows and n=number of columns.
2. Evaluate each unoccupied cells by following its closed path and determine its net cost change.
3. Determine the quality to be shipped to the selected unoccupied cell. Trace the closed path for the unoccupied cell and identify the minimum quality by considering the minus sign in the closed path.

MODIFIED DISTRIBUTION (MODI) METHOD

The MODI method is a more efficient procedure of evaluating the unoccupied cells. The modified transportation table of the initial solution is shown below

SPECIAL CASES IN TRANSPORTATION PROBLEM

​

• Multiple Optimal Solutions

​

• Unbalanced Transportation Problems

​

• Degeneracy in Transportation Problem

​

Maximization In Transport Problems

​

Prohibited Routes

​

The initial feasible solution

• North West Corner Rule
• Least cost
• Vogel’s Approach method

​

The Optimal solution

• Stepping Stone Method
• Modified Distribution Method

​

EXAMPLE

Problem

i = number of sources

j = number of demands

i = number of sources

j = number of demands

Decision variable

Number of millions energy (kWh) produced from sources and sent to demands

x (i,j) = number of sources

x (i,j) > 0 (i = 1,2,3) and j=1,2,3,4)

j = number of demands

Constraints

• Constraints of Demands

• Constraints of Supply

• Constraints of number of Supply and demand

cost =

Objective function

• Minimize cost

Model to be optimized

cij = variable cost

xij = number of unit transported from supply point i

to demand j

Objective function

Model to be optimized

cij = variable cost

xij = number of unit transported from supply point i

to demand j

REVIEW QUESTIONS AND EXERCISES

• What is unbalanced transport problem?
• What is degeneracy?
• Solve the following transportation problem.