Transportation Problems

RK Jana

1
 Outline
 Introduction
 Mathematical model formulation
 Basic feasible solution
 Setting up a transportation table
 Developing basic initial feasible solution using North West Corner
method, Least Cost method, and Vogel’s Approximation Method
(VAM)
 Degeneracy in transportation problems
 Optimality check using Modified Distribution (MODI) method
 Unbalanced transportation problems
 Maximizing transportation problems
 A Case Study on Distribution of
Medical Products of MedPlus
 MedPlus, a medical supply company, supplies packets
containing drugs & other medical products. The
company has three production plants at Dehradun,
Haridwar & Gurgaon. Same drugs and medical
products are produced at each plant. The company
has four distribution warehouses at the four major
metro cities - New Delhi, Mumbai, Kolkata & Chennai.
The packets are distributed directly to warehouses
from the production plants.

3
 Continued…

 MedPlus uses packets of volume 18 cubic inch for

transporting the medical products. These packets are
then transported to four warehouses by designated
vehicles. The transportation cost for MedPlus depends
on the distance of the warehouse from the plant. In the
ongoing production cycle, the transportation costs from
the Dehradun plant to New Delhi, Mumbai, Kolkata
and Chennai warehouses are Rs. 10, 27, 32, and 40,
respectively. The transportation costs from the
Haridwar plant to New Delhi, Mumbai, Kolkata and
Chennai warehouses are Rs. 15, 22, 28, and 36,
respectively.
 Continued…

 The transportation costs from the Gurgaon plant to

New Delhi, Mumbai, Kolkata and Chennai warehouses
are Rs. 5, 18, 25, and 30, respectively. The production
capacities of the Dehradun, Haridwar and Gurgaon
plants are 400, 300, 500 packets, respectively. The
demands of packets at New Delhi, Mumbai, Kolkata
and Chennai warehouses are 375, 250, 350, and 225,
respectively.
 Continued…
 Suggest a distribution plan for MedPlus based on the
following considerations:
1. There is no provision of storing the packets containing
medicinal products at the production plants. So, all
the products produced considering production
forecasts for the current production period must be
supplied to warehouses.
2. The demands at the warehouses must be fulfilled.
3. As per the agreement, the transporter will not change
the transportation cost for the production period.
4. MedPlus wants to minimize its transportation cost for
the entire distribution process.
Network Representation of TP

N D1
10
S1 D 27
32
40 M D2
15 22
H 28
S2 D3
36 K
5 18
25
30
S3 G C D4

Sources Destinations 7
 Continued…

WAREHOUSE
PLANT New Delhi Mumbai Kolkata Chennai
Dehradun 10 27 32 40
Haridwar 15 22 28 36
Gurgaon 05 18 25 30
Demand
Prod. Capacity New Delhi 375
Dehradun 400 Mumbai 250
Haridwar 300 Kolkata 350
Gurgaon 500 Chennai 225
----------- -------- 8
1200 1200
 Continued…

From TO WAREHOUSE Plant

Plant N M K C Capacity

D 10 27 32 40 400
H 15 22 28 36 300
G 05 18 25 30 500
Warehouse
Demand 375 250 350 225 1200

9
 Definition

The problem deals with transporting a product

manufactured at different plants/factories, known as
supply origins, to a number of different warehouses,
known as demand destinations. The objective is to
satisfy the destination requirements at the minimum
transportation cost.

10
 Main Concept

 Inputs
 Availability at sources

 Requirement at destinations

 Unit transportation cost from various sources to

destinations

 Objective
To determine transportation schedule to minimize
total transportation cost

11
 Assumptions in TP

1. The per item shipping cost remains constant,

regardless of the number of units shipped.
2. All the shipping from the sources to the
destinations occur simultaneously. No waiting
is allowed.
3. The total supply is equal to the total demand.

12
 Mathematical Model

 Define cij as the cost to ship one unit from supply origin
i to demand destination j.
 Demand at location j is Dj.
 Supply at origin i is Si
 xij is the quantity shipped from supply origin i to
demand destination j.

13
Continued…

Dest 1 Dest 2 … Dest n Available Supply

Origin 1 c11 c12 … c1n S1

Origin 2 c21 c22 … c2n S2

… … … … … …

Origin m cm1 cm2 … cmn Sm

Total Demand
Demand D1 D2 … Dn = Total supply

14
Solution

x11 x12 … x1n S1

x21 x22 … x2n S2

… … … … …

xm1 xm2 … xmn Sm

D1 D2 … Dn

15
 Mathematical Model

m n
m in :  i 1 j 1
c ij x ij

n
s .t . 
j 1
x ij  S i , f o r i  1, K , m


i 1
x ij  D j , f o r j  1, K , n

x ij  0 , f o r a ll i , j
16
 Basic Feasible Solution

x11 x12 … x1n

x21 x22 … x2n

… … … …

xm1 xm2 … xmn

 In a balanced TP, the basic feasible solution will

contain (m + n – 1) positive variables.

17
 Methods for Solving TP

 North West Corner Method

 Least Cost Method
 VAM Method

18
 How to solve a TP?

1. Define the objective function to be minimized.

2. Set up a transportation table with m rows
representing the supply origins and n columns
representing the demand destinations.
3. Develop an initial feasible solution to the problem by
any of these methods
(a) The North west corner rule
(b) Lowest cost entry method
(c) Vogel’s approximation method.

19
 Continued…

4. Examine whether the initial solution is feasible or not

(if the solution has allocations in (m+n-1) cells with
independent positions).

5. Test whether the solution obtained in the above step is

optimum or not.

6. If the solution is not optimum, modify the shipping

schedule. Repeat the above until an optimum solution
is obtained.

20
 North-West Corner Method

1. Select the northwest corner cell of the transportation

table and allocate as many units as possible
[minimum between available supply and demand
requirements i.e., (min (S1, D1)].
2. Adjust the supply and demand numbers in the
respective rows and columns allocation.
3. If the supply for the first row is exhausted, then move
down to the first cell in the second row and first
column and go to step 2.
4. 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.
21
 Continued…

5. If for any cell, supply equals demand, then the next

allocation can be made in cell either in the next row or
column.
6. Continue the procedure until the total available quantity
is fully allocated to the cells as required.

Advantages: It is simple and reliable. Easy to compute,

understand and interpret.
Disadvantages: This method does not take into considerations the
shipping cost, consequently the initial solution obtained by this
method require improvement.

22
 Example 1
A manufacturing company which produces a specific component of a
car has three plants with a weekly production capacities of 100, 300
and 200 units, respectively. The company supplies its products to
four destinations which have demands of 150, 100, 200 and 150
units, respectively. The per unit transportation cost from three plants
to four destinations are shown below:

To D1 D2 D3 D4
Find an initial feasible solution
From
using North-West Corner method.
S1 19 7 3 21

S2 15 21 18 6

S3 11 14 15 22
20
 Continued…

To D1 D2 D3 D4 Capacity
From
S1 19 7 3 21
100

S2 15 21 18 6 300

S3 11 14 15 22 200

Demand 150 100 200 150 600

24
 To
D1 D2 D3 D4
Capacity
From
100
S1 19 7 3 21
100

S2 15 21 18 6
300

S3 11 14 15 22
200

Demand 150 100 200 150 600

Start in the upper left-hand corner, “north-west corner” of

the schedule and place the largest amount of capacity and
demand available in that cell. 25
 To
D1 D2 D3 D4
Capacity
From
100
S1 100
19 7 3 21

50
S2 300
15 21 18 6

S3 200
11 14 15 22

Demand 150 100 200 150 600

Since capacity of S1 is exhausted, move down to repeat the process for the S2
to D1 cell. S2 has sufficient capacity but D1 can only take 50 packs.

26
 To
D1 D2 D3 D4
Capacity
From
100
S1 19 7 3 21
100

50 100 150
S2 15 18 6
300
21

50 150
S3 11 14 15 22
200

Demand 150 100 200 150 600

Now move to the next cells to the right and assign capacity for S2 to demand
until depleted. Then move down to the S3 row and repeat the process.

27
 To
D1 D2 D3 D4
Capacity
From
19 7 3 21 1900
S1 1900 100
750
15 21 18 6

S2 750 2100 2700 300 2100

11 14 15 22 2700
S3 750 3300 200
750
Demand 150 100 200 150 600 3300

C =11,500
Multiply the quantity in each cell by the cost.
28
 Example 2
The distribution of commodities from three warehouses is planned to four
destinations. The supply, demand and per unit transportation cost are as
follows:
To Supply
D1 D2 D3 D4
From
O1 1 2 1 4 30
O2 3 3 2 1 50
O3 4 2 5 9 20
Demand
20 40 30 10
Obtain initial solution of the transportation problem by using North-West
corner method. 29
 Continued…

To Supply
D1 D2 D3 D4
From
20 10
O1 1 2 1 4 30
30 20
O2 3 3 2 1 50
10 10
O3 4 2 5 9 20
Demand
20 40 30 10
30
 Least Cost Method

1. Select the cell with the lowest transportation cost

among all the rows and columns of the transportation
table.
2. If the minimum cost is not unique, then select
arbitrarily any cell with this minimum cost (preferably
where maximum allocation is possible).
3. Repeat steps 1 and 2 for the reduced table until the
entire supply at different factories is exhausted to
satisfy the demand at different warehouses.

31
 Example 3

Consider Example 2. Obtain an initial solution by using Least Cost

method

To Supply
D1 D2 D3 D4
From
O1 1 2 1 4 30
O2 3 3 2 1 50
O3 4 2 5 9 20
Demand
20 40 30 10
32
 Continued…

To Supply
D1 D2 D3 D4
From
30
O1 1 2 1 4 30
O2 20
3 20
3 2 10
1 50
20
O3 4 2 5 9 20
Demand
20 40 30 10
33
 Vogel’s Approximation Method (VAM)

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

table. The penalty for a given row and column is merely the
difference between the smallest cost and next smallest cost in
that particular row or column.

2. Identify the row or column with the largest penalty. In this

identified row or column, choose the cell which has the smallest
cost and allocate the maximum possible quantity to the lowest
cost cell in that row or column so as to exhaust either the supply
at a particular source or satisfy demand at warehouse (if a tie
occurs in the penalties, select that row/column which has
minimum cost. If there is a tie in the minimum cost also, select the
row/column which will have maximum possible assignments).

34
 Continued…

3. Reduce the row supply or the column demanded by the assigning

to the cell.
4. If the row supply is now zero, eliminate the row, if the column
demand is now zero, eliminate the column, if both the row supply
and the column demand are zero, eliminate both the row and
column.
5. Re-compute the row and column difference for the reduced
transportation table, omitting rows or columns crossed out in the
preceding step.
6. Repeat the above procedure until the entire supply at factories are
exhausted to satisfy demand at different warehouses.
35
 Example 4

Consider Example 2. Obtain an initial solution by using Vogel’s

Approximation method.

To Supply
D1 D2 D3 D4
From
O1 1 2 1 4 30
O2 3 3 2 1 50
O3 4 2 5 9 20
Demand
20 40 30 10
36
 Continued…

Supply
D1 D2 D3 D4
20 10 (0) (0) (0) (1) *
O1 1 2 1 4 30
20 20 10 (1) (1) (1) (1) (1)
O2 3 3 2 1 50
20 (2) (2) * * *
O3 4 2 5 9 20
Demand
20 40 30 10
(2) (0) (1) (3)
(2) (0) (1) *
(2) (1) (1) *
* (1) (1) *
* (1) (1) *
37
 Optimality Test

The Modified Distribution Method

1. Determine an initial basic feasible solution consisting of (m + n -1)
allocations using any of the three methods.
2. Determine a set of numbers ui ( i= 1,2,..m) for each row and vj (j =
1,2..n) for each column. Calculate cij = (ui + vj ) for occupied cells.
In practice, this is done by choosing the ui or vj value as zero
corresponding to the row or column containing maximum number
of occupied cells.
3. Compute the opportunity cost
Δij = Cij - (Ui + Vj ) for each unoccupied cells.

38
 Continued…

4. Check the sign of each opportunity cost:

If all the Δij are positive or zero, then the solution is optimum. If one
of the values is zero then there exists an alterative solution for the
same transportation cost. If any value is negative, then the given
solution is not optimum & further improvement is possible.
5. Select the unoccupied cell with the largest negative opportunity cost
as the cell to be included in the next solution.
6. Draw a closed path or loop for the unoccupied cells selected in step
5. It may be noted that right angle turns in this path are permitted
only at occupied cells and at the unoccupied cells.

39
Continued…

40
 Continued…

7. Assign alternative 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.

8. Determine the maximum number of units that should be shipped to

this unoccupied cell. The smallest one with a negative sign on the
closed path indicates the number of units that can be shipped to
the entering cell. This quantity is added to all the cells on the path
marked with plus sign and subtracted from those cells marked with
minus sign. In this way, the unoccupied cell under consideration
becomes an occupied cell making one of the occupied cells as
unoccupied cell.

9. Repeat the whole procedure until an optimum solution is found i.e.,

Δij are positive or zero. Finally, calculate new transportation cost.
41
 Example 4: Continued…

Supply ui
D1 D2 D3 D4
20 10 -1
O1 1 2 1 4 30
20 20 10 0
O2 3 3 2 1 50
20 -1
O3 4 2 5 9 20
Demand
20 40 30 10
vj 2 3 2 1

42
 Continued…

ui
D1 D2 D3 D4
20 0 10 4 -1
O1 1 2 1 4
1 20 20 10 0
O2 3 3 2 1
3 20 4 9 -1
O3 4 2 5 9
vj 2 3 2 1

Here all Δij are greater than or equal to zero. Hence the solution
is optimum. Optimum solution is x11 = 20, x13 = 10, x22 = 20,
x23 = 20, x24 = 10, x32 = 20 & minimum cost is 180.
43
 Example 5

Solve the following transportation problem by using Vogel’s

Approximation method:

To Supply
D1 D2 D3
From
O1 6 8 4 14
O2 4 9 3 12
O3 1 2 6 5
Demand
6 10 15 31
44
Continued…

Supply ui

1 10 3
6 8 4 14 0

-1 2 12 -1
4 9 3 12
5 -1 7 -5
1 2 6 5
Demand
6 10 15
vj 6 8 4
45
Continued…

1 10 3

6 8 4
-1 12

4 9 3
5

1 2 6

46
Continued…

1 10 3

-1 12

47
Continued…

1-1 3+1

+1 12-1

Min{1, 12} = 1

48
Continued…

Supply ui

1 10 4
6 8 4 14 0

1 2 11 -1
4 9 3 12
5 -2 6 -4
1 2 6 5
Demand
6 10 15
vj 5 8 4
49
 Continued…

10 4
10-5 4+5

1 11
1+5
5 -2
11-5

5-5 +5

Min{5, 10, 11} = 5

50
 Continued…

Supply ui

1 5 9
6 8 4 14 1

6 2 6 0
4 9 3 12
2 5 8 -5
1 2 6 5
Demand
6 10 15
vj 4 7 3

x12 = 5, x13 = 9, x21 = 6, x23 = 6, x32 = 5, Min cost = 128 51

 Example 6
The distribution of commodity from sources A, B, C and D to three
destinations P, Q, R and S, and the corresponding transportation
costs are shown below. Find the optimum solution.
To P Q R Supply
From
A 2 7 4 5

B 3 3 1 8

C 5 4 7 7

D 1 6 2 14
Demand 7 9 18

x11 = 5, x22 = 2, x23 = 6, x32 = 7, x41 = 2, x43 = 12 Min cost = 76. 52

 Degeneracy in TP

 If at every initial stage or in any subsequent iteration

the number of allocations be less than (m + n – 1) then
we have a case of degeneracy.
 To resolve this case, we allocate a very small positive
quantity epsilon to one or more (as many required) of
the empty cells and consider these cells to be the
occupied cells such that it does not form a loop with
the existing basic cells. With this choice of epsilon, the
original problem is not changed. Epsilon is considered
as a real positive allocation as long as is required.
Finally, it will be omitted.
53
 Example 7

Solve the following transportation problem by using Vogel’s

Approximation method:

To Supply
D1 D2 D3
From
O1 8 7 3 60
O2 3 8 9 70
O3 11 3 5 80
Demand
50 80 80
54
Continued…

Supply
D1 D2 D3

60
O1 8 7 3 60
50 20
O2 3 8 9 70
80
O3 11 3 5 80
Demand
50 80 80

55
 Continued…

 We now add a small positive quantity  to a

cell such that this does not result in forming a
loop with the existing basic cells. For a
dependent set of cells unique determination of
ui and vj will not be possible.

56
Continued…

Supply ui
D1 D2 D3

O1
11
8 7 60
3 60 0

-5 6
O2 50
3 8 20
9 70
18 6 -4
O3 11 80
3 5 80
Demand
50 80 80
vj -3 7 3
57
 Continued…

11  60

50 -5 20

18 80 6
   60  

 20  

58
 Continued…

11 5 60

8 7 3 -6
50  20

3 8 9 0
13 80 1

11 3 5 -5

3 8 9

Here all Δij are greater than zero. Hence the solution
is optimum. Optimum solution is x13 = 60, x21 = 50, x23 = 20,
x32 = 80 & minimum cost is 750.
59
 Special Cases in TP

 Unbalanced TP
 Maximizing TP
 No allocation in a particular cell
 Some positive allocation in a particular
cell

60
 Unbalanced TP

In a TP, if the sum of available resources is not

equal to sum of demands then the TP is known
as an unbalanced TP.

m n
 a   j 1 b j
i 1 i

61
 Adding Fictitious Source

A B C S

1 10 2 9 50

2 25 12 6 30

D 20 50 40

A B C S
1 10 2 9 50
2 25 12 6 30

3 0 0 0 30
D 20 50 40
62
 Adding Fictitious Destination

X Y Z S

1 15 8 7 80

2 20 3 4 50

D 30 30 40

X Y Z T S

1 15 8 7 0 80

2 20 3 4 0 50

D 30 30 40 30
63
 Example 8
 The transportation cost matrix for a given situation for supply of the
commodity from source A, B and C to the point of usages P, Q and R
is given below. Find the optimum solution.

To Supply
P Q R
From
A 4 8 8 76
B 16 24 16 82
C 8 16 24 77
Demand
72 102 41
64
 Continued…

Optimum allocation using MODI method is as follows:

Supply
P Q R S

A 4
76
8 8 0 76 Optimum cost
= Rs 2424.
21 41 20
B 16 24 16 0 82 Here, Δ21 = 0
and all other
72 5
C 8 16 24 0 77 Δij are > 0.
Demand
72 102 41 20
65
 Continued…

We include (2, 1) cell into the basis and find optimum solution:

Supply
P Q R S

A 4
76
8 8 0 76 Optimum cost
= Rs 2424.
21 41 20
B 16 24 16 0 82
51 26
C 8 16 24 0 77
Demand
72 102 41 20
66
 Example 9
Find the optimum solution of the following transportation problem:
To Supply
P Q R S T
From
A 5 8 6 6 3 8
B 4 7 7 6 5 5
C 8 4 6 6 4 9
Demand
4 4 5 4 8
Optimum solution is x14 = 8, x21 = 4, x24 = 1, x32 = 4, x33 = 2,
x34 = 3, x43 = 0 & minimum transportation cost is 92.
67
 Example 10

Solve the following unbalanced TP:

D1 D2 D3 S

O1 4 3 2 10

O2 1 5 0 13

O3 3 8 6 12

D 8 5 4

(Minimum Cost = 23 units) 68

 Maximizing TP

A maximizing TP is first converted into a

minimizing TP by subtracting all the costs from
the highest cost involved in the cost matrix.
Then the problem is solved as usual.

69
 Example

Solve the following maximizing TP:

D1 D2 D3 S

O1 8 6 5 150

O2 6 6 6 150

O3 10 8 4 150

O4 8 6 4 150

D 200 200 200

(Maximum profit = 4250 units) Alternate optimum exits. 70

 No allocation in a particular
cell
If there is no allocation in a particular cell then
it indicates that the route corresponding to that
particular cell from the source to destination is
prohibited. In such a case, a large positive cost
is assigned to that cell so that no allocation will
be made on that cell. The solution procedure
remains same.

71
 Some positive allocation in a
particular cell
If it is necessary to allocate a given quantity in
a particular cell then adjust the availability &
requirements accordingly & solve the
remaining part of the problem in the usual
manner.

72
 Example

Solve the following TP. Given that 8 units must be

assigned to (3, 3) cell.
D1 D2 D3 S D1 D2 D3 S
O1 2 3 11 40
O1 2 3 11 40
O2 9 6 7 50
O2 9 6 7 50
O3 1 5 4 30
8
O3 1 5 4 22
O4 3 12 2 30
D 50 50 50 O4 3 12 2 30
D 50 50 42

73