Which is the best method to solve transportation problem?

Photo by Zane Lee on Unsplash

this fast-moving world, the need for the commodity is increasing day by day. Accordingly, the importance of transportation has a great role to play in society. The profit and fortunes of the companies which are moving merchandise from one corner of the country to another are determined by transportation. This is especially true when transportation costs and transportation time are overwhelming than production costs and production time. What if the transportation in all areas of handled professionally and if the costs involved are made optimal, the productivity of the country goes up even if no other factor is touched!

The study of optimal transportation and allocation of resources is; transportation theory or transport theory. The French mathematician Gaspard Monge formalized this problem in 1781. Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich hence known as the Monge–Kantorovich transportation problem.

An important type of transportation problem which is addressed by the Linear Programming(LP) is in the area of physical distribution of goods and services from several supply centres to demand centres. In other words, transportation problems deal with the movement of commodities from different sources to different destinations, with the overall objective of minimizing transportation costs. Such a linear programming formulation of the transportation problem is also known as the Hitchcock–Koopmans transportation problem.

Applications of transportation model are used in the airline industry, Research and Development, Travelling Salesman, Transhipment, etc.

PREREQUISITES

To solve a transportation problem, the following information must be given:

• m= The number of sources.
• n= The number of destinations.
• The total quantity available at each source.
• The total quantity required at each destination.
• The cost of transportation of one unit of the commodity from each source to each destination.

ASSUMPTIONS

The following basic assumptions are made before using any transportation technique:

• The total quantity available at all the sources is equal to the total quantity required the destinations. If they do not match each other, dummy sources or dummy destinations are added.
• The unit transportation cost from one origin to a destination is known and certain.
• The unit cost is independent of the number of goods transported.
• The objective is to minimize the total transportation cost.
• Although transportation problems can be formulated as a LPP, other easier algorithms are developed for solving them.

SOLVING A TRANSPORTATION PROBLEM

There are basically 3 main steps

1. Formulation of the transportation model in LPP

2. Find a Basic feasible Solution (BFS)

3. Optimality test

Let’s go in detail

1. FORMULATION OF TRANSPORTATION MODEL in LPP

While solving an operation research problem, the key part lay in formulating the model by decoding the problem. For transportation problem usually, the problem will be given in a tabular form or matrix form called transportation table or cost-effective matrix.

Let’s check an example below.

Here,

Source = {A, B, C}

They represent sources with supply capacity 10,35,25 units of commodities respectively (given in orange)

Hence, total supply=10+35+25=70

Destinations= {1,2,3}

They represent destinations that require 20,25,25 units of commodities respectively (given in green).

Hence, total demand=20+25+25=70

The elements represented in the matrix (given in white) are called cost. i.e., the unit cost involved in moving unit commodity from one origin to another destination.

For example,

The cost incurred in moving 1 unit of the commodity from source A to destination 1= ₹2/-

Likewise,

The cost incurred in moving one unit of the commodity from source B to destination 2= ₹4/-

and so on. [Here, we are looking at the cross-section of source and destination]

TYPES OF TRANSPORTATION PROBLEM

Before going further, let’s check different types of transportation problem.

There are basically 2 types of transportation problem:

1. Balanced Transportation Problem

2. Unbalanced Transportation Problem

Let’s peep into it.

1. Balanced Transportation Problem

total quantity available = total quantity required

i.e., Total supply= Total demand

Let’s check the example below.

Here,

Total supply=75

Total demand=75

Hence, Total supply= Total demand

2. Unbalanced Transportation Problem

total quantity available ≠ total quantity required

i.e., Total supply≠ Total demand

The total quantity available at all the sources is equal to the total quantity required the destinations. If they do not match each other, dummy sources or dummy destination are added to make it a standard transportation problem.

There are 2 situations leading to this unbalanced condition

(i). Total Supply> Total Demand

(ii). Total supply< Total demand

(i). Total Supply> Total Demand

I.e., the total quantity available > total quantity required

Let’s check the example below.

Here,

Total supply=65

Total demand=60

Hence, Total supply> Total demand

In such cases, we add a dummy destination giving dummy demand with each cost as zero (0) but dummy demand for the dummy destination as total supply-total demand.

In this example, dummy demand= 65–60=5

Thus, total supply= total demand

(ii). Total supply< Total demand

I.e., the total quantity available <total quantity required

Let’s check the example below.

Here,

Total supply=65

Total demand=75

Hence, Total supply<Total demand

In such cases, we add a dummy source giving dummy supply with each cost as zero (0) but dummy supply for the dummy destination as total demand-total supply.

In this example, dummy supply= 75–65=10.

Thus, total supply= total demand

The solution that every problem in transportation looks for is that of the quantity from each source should go to which destination so that all demands at and at the same time the costs are kept to a minimum.

For this, we have to convert every problem to a standard problem to go further.

2. BASIC FEASIBLE SOLUTION(BFS)

There are different methods available to obtain the initial basic feasible solution. They are:

(1). North-West(N-W) Corner Rule

(2). Least Cost Method (or The Matrix Minimum Method)

(3). Vogel’s Approximation Method [VAM] (or Penalty Method)

Let’s dive into each method.

For that let’s consider an example problem for better understanding.

The question is given below.

The first step is to make it a standard transportation problem.

For that check whether it is a balanced or unbalanced transportation problem.

The given problem is a balanced transportation problem. So, let’s proceed.

Now, we have to find a basic feasible solution. For the same, we have 3 different methods. Let’s check one by one with the help of this problem.

(1). North-West(N-W) Corner Rule

Select North-West Corner cell. i.e., cost of the intersection of 1st row and 1st column. [Here, 5(given in blue)]

Compare the demand and supply of that cell. [Here, 65 and 70 (given in red)]

Allocate the cell with the least value [Here, 65 (given in yellow)]

Subtract the excluded cell with the least value. i.e., the allocated cell vale. [Here, 70–65=5]

Eliminate the column or row accordingly by striking it off. [Here, the column with destination 1 (marked with red line)]

Always the total demand and supply will remain the same. (You can consider this method to verify whether you are going on the correct path or not.) Because we are allocating the cells with new values in such a way that the total demand and supply will remain the same.

[i.e., Here, 42+43+65=150 (total demand) and 5+30+50+65=150 (total supply)]

Now continue the process with remaining cells.

Again, find the North-West(N-W) cell and do the same steps as given above.

Let’s see the same in this example.

Here, both the demand and supply will be the same which will be further allocated in the remaining single cell. [Here, 43] (This is another method to verify whether all the above steps were correct or not.)

Methods to verify the correctness of the process:

The total demand and supply will remain the same throughout the steps.

In the last step, the single-cell will be allocated with the value in either with demand or supply as both will have the same values.

If the demand and supply have the same values; a tie, you can choose any one of them to allocate the cell making other value zero. (It’s purely user’s choice to decide which one to select.👍)

The final table with all allocated cell will be like this.

This gives the initial feasible solution by the N-W Corner method.

Now let’s calculate the cost associated with these allocations.

To find the same add all the products of all allocated cell values (given in yellow) and the cost of the respective cell (given in blue).

i.e., Total cost=(65x5) +(5x7) +(30x4) +(7x7) +(43x7)

=325+35+120+49+301

=830

Now, let’s understand what we have found out

₹830-represents the total cost involved in moving the commodities.

The path followed is represented by the red arrows as we found by the N-W Corner method.

Let’s represent the same in a table

This may or may not represent the optimal solution for this problem i.e., there may exist other ways of allocating which may give a better solution with a lower total cost.
An optimality test has to be carried out to test whether the obtained answer is optimal. If not, the optimality test leads us to one for a probable improvement.

(2). Least Cost Method (or Matrix Minimum method)

Let’s discuss with the same example.

Select the least value among all the costs (given in white). i.e., minimum cost. [Here, 4(given in blue)]

Here, there are two cells with the least cost. It’s purely user’s choice to decide which one to select.

If there are more than 1 cell with the same least cost; a tie, you can choose anyone among them. (It’s purely user’s choice to decide which one to select.👍)

Compare the demand and supply of that cell. [Here, 30 and 65 (given in red)]Allocate the cell with the least value [Here, 30 (given in yellow)]

Subtract the excluded cell with the least value. i.e., the allocated cell value. [Here, 65–30=35]

Eliminate the column or row accordingly by striking it off. [Here, the row with source B (marked with red line)]

Always the total demand and supply will remain the same. (You can consider this method to verify whether you are going on the correct path or not.) Because we are allocating the cells with new values in such a way that the total demand and supply will remain the same.

[i.e., here, 35+42+43+30=150 (total demand) and 70+50+30=150 (total supply)]

Now continue the process with remaining cells.

Again, find the least cost cell and do the same steps as given above.

Let’s see the same in this example.

Here, both the demand and supply will be the same which will be further allocated in the remaining single cell. [Here, 43] (This is another method to verify whether all the above steps were correct or not.)

Methods to verify the correctness of the process:

The total demand and supply will remain the same through the steps.

In the last step, the single the cell will be allocated with the value in either with demand or supply as both will have the same values.

If the demand and supply have the same values; a tie, you can choose any one of them to allocate the cell making other value zero. (It’s purely user’s choice to decide which one to select.👍)

The final table with all the allocated cell will be like this.

This gives initially feasible solution by the least-cost method.

Now let’s calculate the cost associated with these allocations.

To find the same add all the products of all allocated cell values (given in yellow) and the cost of the respective cell (given in blue).

i.e., Total cost=(35x5) +(30x4) +(35x7) +(7x7) +(43x7)

=175+120+245+49+301

=890

Now, let’s understand what we have found out

₹890-represents the total cost involved in moving the commodities.

The path followed is reprinted by the red arrows as we found by the least-cost method.

Let’s represent the same in a table.

This may or may not represent the optimal solution for this problem i.e., there may exist other ways of allocating which may give a better solution with a lower total cost
An optimality test has to be carried out to test whether the obtained answer is optimal. If not, the optimality test leads us to one for a probable improvement.

(3). Vogel’s Approximation Method [VAM] (or Penalty Method)

Let’s discuss with the same example.

Selecting the cost cell to be allocated is not that easy in VAM as if we discussed in the N-W Corner method and least cost cell method. (Chill dude,😎 it’s not that difficult though. 😇But the process is a bit lengthier than before.😅)

In the VAM, we have to first in the differences between the two lowest costs in each row and column. These are known as penalties/ extra costs.

The difference between the two smallest values is considered.

[Here, Penalties= {2,0,1,1,3,1}]

Now find the maximum value among the penalties irrespective of row or column.

[Here, max (Penalties)=3 (given in pink)]

If there is a tie, choose anyone. (It’s purely user’s choice to decide which one to select.👍)

Now, look into the respective row or column accordingly.

[Here, the column (given in pink)]

Select the least value among all the costs (given in pink). i.e., minimum cost. [Here, 4(given in blue in the figure below)]

If there are more than 1 cell with the same least cost; a tie, you can choose anyone among them. (It’s purely user’s choice to decide which one to select.👍)

Compare the demand and supply of that cell [Here, 30 and 42 (given in red)]

Allocate the cell with the least value [Here, 30 (given in yellow)]

Subtract the excluded cell with the least value. i.e., the allocated cell vale. [Here, 42–30=12]

Eliminate the column or row accordingly by striking it off. [Here, the column with source B (marked with red line)]

Always the total demand and supply will remain the same. (You can consider this method to verify whether you are going on the correct path or not.) Because we are allocating the cells with new values in such a way that the total demand and supply will remain the same.

[i.e., here, 65+12+43+30=150 (total demand) and 70+50+30=150 (total supply)]

Now continue the process with remaining cells.

Again, find the penalty and do the same steps as given above.

Let’s see the same in this example.

Here, both the demand and supply will be the same which will be further allocated in the remaining single cell. [Here, 43] (This is another method to verify whether all the above steps were correct or not.)

Methods to verify the correctness of the process:

The total demand and supply will remain the same through the steps.

In the last step, the single the cell will be allocated with the value in either with demand or supply as both will have the same values.

If the demand and supply have the same values; a tie, you can choose any one of them to allocate the cell making other value zero. (It’s purely user’s choice to decide which one to select.👍)

The final table with all the allocated cell will be like this.

This gives an initial feasible solution by VAM.

Now let’s calculate the cost associated with these allocations.

To find the same add all the products of all allocated cell values (given in yellow) and the cost of the respective cell (given in blue).

i.e., Total cost=(65x5) +(5x7) +(30x4) +(7x7) +(43x7)

=325+35+120+49+301

=830

Now, let’s understand what we have found out

₹830-represents the total cost involved in moving the commodities.

The path followed is represented by the red arrows as we found by VAM.

Let’s represent the same in a table.

This may or may not represent the optimal solution for this problem i.e., there may exist other ways of allocating which may give a better solution with a lower total cost.
An optimality test has to be carried out to test whether the obtained answer is optimal. If not, the optimality test leads us to one for a probable improvement.

3. OPTIMALITY Test

While a basic feasible solution may take care of all the sources and location restrictions it need not give a solution with the least cost. There could be several basic feasible solutions but the one that minimizes the total transportation cost is said to be the optimal solution. After a basic feasible solution has been identified by anyone of the methods listed above, the solution is to be further tested for Optimality tests would verify whether the given solution is the best and if not it would lead us to the better or optimal solution (I would choose a bad option over worst.😉)
(We shall discuss it in detail in another article since this itself seems lengthy to me.😂)

[1]Dr. K. P. Phaneesh, Operations Research(2009), Sudha Publications

So far, we have discussed finding a basic feasible solution. We can only conclude our decision of choosing the right path after the optimality test which will be discussed in another article.😊

Please feel free to share your valuable thoughts💭, ideas💡 or even doubts😕😵.