Transportation Problem
1. Introduction to the Transportation Problem
The Transportation Problem is a special class of linear programming problems. It involves
finding the most efficient way to transport goods from a set of sources/origins (e.g., factories,
warehouses) to a set of destinations (e.g., stores, distribution centers) while minimizing
transportation costs. This problem is used in supply chain management, logistics, and
optimization in various industries.
2. Components of the Transportation Problem
• Origins: Locations where goods are produced or available for shipment (e.g., factories
or warehouses).
• Destinations: Locations where goods are required or need to be delivered (e.g., stores
or customers).
• Supply: The quantity of goods available at each origin.
• Demand: The quantity of goods needed at each destination.
• Transportation Cost: The cost of transporting one unit of goods from an origin to a
destination. This is usually given in a cost matrix.
The objective of the transportation problem is to minimize the total transportation cost while
satisfying both supply and demand constraints.
3. Basic Assumptions in the Transportation Problem
1. Additivity of costs: The total cost of transporting goods is the sum of the individual
costs for each route.
2. Supply equals demand: The total supply from all sources equals the total demand at
all destinations. If this condition is not met, the problem is adjusted by adding dummy
sources or dummy destinations.
3. Homogeneous goods: The goods being transported are identical in nature and do not
vary in value or quality.
4. Fixed transportation routes: The cost per unit of transportation between a source and
a destination is fixed.
4. Mathematical Formulation of the Transportation Problem
Let there be m origins 𝑂1 , 𝑂2 , … … . . , 𝑂𝑚 and the goods available at origin 𝑂𝑖 be 𝑎𝑖 , 𝑖 =
1, 2, … . . , 𝑚. Let there be n destinations 𝐷1 , 𝐷2 , … … … , 𝐷𝑛 and goods required at destination 𝐷𝑗
be 𝑏𝑗 , 𝑗 = 1, 2, … . . , 𝑛.
So, the transportation problem can be written in tabular form as follows:
Destinations
𝐷1 𝐷2 … 𝐷𝑗 … 𝐷𝑛 Supply
𝑂1 𝑐11 𝑐12 𝑐1𝑗 𝑐𝑖𝑛 𝑎1
𝑂2 𝑐21 𝑐22 𝑐2𝑗 𝑐2𝑛 𝑎2
…
Origins
𝑂𝑖 𝑐𝑖1 𝑐𝑖2 𝑐𝑖𝑗 𝑐𝑖𝑛 𝑎𝑖
𝑂𝑚 𝑐𝑚1 𝑐𝑚2 𝑐𝑚𝑗 𝑐𝑚𝑛 𝑎𝑚
Demand 𝑏1 𝑏2 𝑏𝑗 𝑏𝑛
The transportation problem can be formulated as a linear programming (LP) problem as
follows:
Objective Function:
Minimize the total transportation cost:
𝑚 𝑛
𝑍 = ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗
𝑖=1 𝑗=1
Where:
• 𝑐𝑖𝑗 = Transportation cost per unit from origin i to destination j
• 𝑥𝑖𝑗 = Amount of goods transported from origin i to destination j
• m = Number of origins
• n = Number of destinations
Constraints:
1. Supply constraints (for each origin i):
∑𝑛𝑗=1 𝑥𝑖𝑗 = 𝑎𝑖 for all i = 1, 2, …., m
2. Demand constraints (for each destination jj):
∑𝑛𝑖=1 𝑥𝑖𝑗 = 𝑏𝑗 for all j = 1, 2, ….., n
3. Non-negativity constraints:
𝑥𝑖𝑗 ≥ 0 for all i, j
5. Types of Transportation Problems
• Balanced Transportation Problem: The total supply is equal to the total demand, i.e.,
𝑚 𝑛
∑ 𝑎𝑖 = ∑ 𝑏𝑗
𝑖=1 𝑗=1
• Unbalanced Transportation Problem: The total supply is not equal to the total
demand. In this case, dummy sources or dummy destinations are added with a supply
of 0 or demand of 0, respectively, to balance the problem.
6. Methods to find Initial basic feasible solution of a Transportation Problem
There are several methods for solving transportation problems:
6.1. North-West Corner Rule
This is a heuristic method used to find an initial feasible solution:
1. Start at the top-left corner (north-west corner) of the transportation table.
2. Allocate as much as possible to the first cell (min between the supply and demand at
that cell).
3. Move right if the demand is satisfied, or move down if supply is exhausted, and repeat
the process until the entire transportation plan is filled.
Consider the following problem
𝐷1 𝐷2 𝐷3 𝐷4 𝑎𝑖
𝑂1 9 6 9 5 16
𝑂2 2 6 4 1 12
𝑂3 5 7 2 9 15
𝑏𝑗 12 14 9 8
Here
𝑚 𝑛
∑ 𝑎𝑖 = 43 = ∑ 𝑏𝑗
𝑖=1 𝑗=1
So, it is a balanced problem. We can proceed to the next step.
Select the north-west cell i.e. (O1, D1). Supply for this cell is 16 and demand is 12.
Minimum between these two is 12. So, allocate 12 unit in that cell. Therefore, demand for D1
is fulfilled. Move to the next north-west cell i.e. (O1, D2). Remaining supply for this cell is 4
and demand is 14. Minimum between these two is 4. So, allocate 4 unit here. Supply of O1 is
exhausted now. Move down and repeat the same process. Thus, we will get the following table.
𝐷1 𝐷2 𝐷3 𝐷4 𝑎𝑖
𝑂1 12 9 4 6 9 5 16
𝑂2 2 10 6 2 4 1 12
𝑂3 5 7 7 2 8 9 15
𝑏𝑗 12 14 9 8
Number of allocated cells = 6 (m+n-1).
Total cost = 12 × 9 + 4 × 6 + 10 × 6 + 2 × 4 + 7 × 2 + 8 × 9 = 226 𝑢𝑛𝑖𝑡𝑠.
6.2. Least Cost Method
This method focuses on selecting the lowest cost cells in the transportation table:
1. Find the cell with the lowest transportation cost.
2. Allocate as much as possible to that cell.
3. Remove the row or column (supply or demand) that is satisfied and repeat the process
with the remaining rows and columns.
𝐷1 𝐷2 𝐷3 𝐷4 𝑎𝑖
𝑂1 9 6 9 5 16
𝑂2 2 6 4 1 12
𝑂3 5 7 2 9 15
𝑏𝑗 12 14 9 8
Cell with lowest cost is (O2, D4). Minimum between demand and supply for this cell is 8.
Allocate 8 units here. So, demand for D4 is fulfilled. Remaining supply is 4 units. So, we get
next table
𝐷1 𝐷2 𝐷3 𝐷4 𝑎𝑖
𝑂1 9 6 9 5 16
𝑂2 2 6 4 8 1 12 4
𝑂3 5 7 2 9 15
𝑏𝑗 12 14 9 8
Next cell with lowest cost are (O2, D1) and (O3, D3). One can select anyone. I am selecting (O2,
D1). Minimum between demand and supply for this cell is 4. Allocate 4 units here. So, supply
for O2 is exhausted. Remaining demand of D1 is 8 units. So, we get next table
𝐷1 𝐷2 𝐷3 𝐷4 𝑎𝑖
𝑂1 9 6 9 5 16
𝑂2 4 2 6 4 8 1 12 4
𝑂3 5 7 2 9 15
𝑏𝑗 12 14 9 8
Select (O3, D3). Minimum between demand and supply for this cell is 9. Allocate 9 units here.
So, demand of D3 is satisfied. Remaining supply of O3 is 6 units. So, we get next table
𝐷1 𝐷2 𝐷3 𝐷4 𝑎𝑖
𝑂1 9 6 9 5 16
𝑂2 4 2 6 4 8 1 12 4
𝑂3 5 7 9 2 9 15 6
𝑏𝑗 12 14 9 8
Cell with lowest cost is (O3, D1). Minimum between demand and supply for this cell is 6.
Allocate 6 units here. So, supply for O3 is exhausted. Remaining demand of D1 is 2 units. So,
we get next table
𝐷1 𝐷2 𝐷3 𝐷4 𝑎𝑖
𝑂1 2 9 14 6 9 5 16
𝑂2 4 2 6 4 8 1 12 4
𝑂3 6 5 7 9 2 9 15 6
𝑏𝑗 12 14 9 8
8 2
Now allocate 2 units in (O1, D1) and 14 units in (O1, D2).
Number of allocated cells = 6 (m+n-1).
Total cost = 2 × 9 + 14 × 6 + 4 × 6 + 8 × 1 + 6 × 5 + 9 × 2 = 182 𝑢𝑛𝑖𝑡𝑠.
6.3. Vogel’s Approximation Method (VAM)
VAM is a more advanced heuristic method:
1. Calculate the penalty for each row and column. The penalty is the difference between
the smallest and second smallest costs in that row or column.
2. Select the row or column with the highest penalty and allocate as much as possible to
the lowest cost cell in that row or column.
3. Repeat the process by eliminating the satisfied row or column and recalculating the
penalties.
