Transportation

EXAMPLE FOR SOLUTION OF TRANSPORTATION PROBLEM 

An organization has four destinations and three sources for supply of goods. The
transportation cost per unit is given below. The entire availability is 700 units which exceeds
the cumulative demand of 600 units. Decide the optimal transportation scheme for this
case.

Solution

Step 1:           Check for balance of supply and demand

                        S Supply = 250 + 200 + 250 = 700 units

                        S Demand = 100 + 150 + 250 + 100 = 600 units

 
Decision Rule

(i)            If S Supply = S Demand

then go to next step.

(ii)          Else; if S Supply > S Demand

then, add a “dummy destination” with zero transportation cost.

(iii)         Or else; if S supply < S Demand

then, add a “dummy source” with zero transportation cost.

Since, in this problem

S supply > S Demand

Hence; add a “dummy destination” (say D5) with zero transportation cost and balance
demand which is difference in supply and demand (= 100 units).

The initial transportation matrix is now formulated with transportation cost in the small box
of each route. Note that each cell of the transportation matrix represents a potential route.

                             Introducing dummy column for balancing the supply and demand

Step 2:

(i)          Decide the nature of problem : Minimization of transportation-cost

(ii)         Make initial assignment

Initial assignment may be done by using any of the following approaches :

(i)         Least-cost method

(ii)        North-West corner method

(iii)       Vogel's approximation method

We would demonstrate all the three methods.

 
(i) Initial Solution by Least Cost method

Select the lowest transportation (or shipping) cost cell (or route) in the initial matrix. For
example: it is route S1D5, S2D5 and S3D5 in our problem with zero shipping cost.

Allocate the minimum of remaining balance of supply (in last column) and demand (in last
row).

Let us select S1D5 route. One can also select other route (S2D5 or S3D5) in case of tie. For S1D5,
available supply is 250 and available demand is 100 units. The lower is 100 units. Hence,
allocate 100 units-through this route (i.e, S1D5).

With this allocation, entire demand of route S1D5 is consumed but supply of
corresponding source, S1, is still (250-100) or 150 units left. This is marked in last column of
supply. The entire demand ofdestination, D5, is consumed. We get the following matrix (Fig.
12.6) by crossing out the consumeddestination (D5):

Now, we leave the consumed routes (i.e., column D5) and work for allocation of other
routes.

Next, least cost route is S1D1, with 13 per unit of shipping cost. For this route, the demand is
100 units and remaining supply is 150 units. We allocate minimum of the two, i.e., 100 units
in this route. With this destination, D1 is consumed but source S1 is still left with (150-100) =
50 units of supply. So, now leave the destination D1 and we get the following matrix.

                                                      With 100 units allocation in route S1D5

                                           Assignment for destination D1 and D5 consumed

Now, we work on remaining matrix, which excludes first column (D1) and last column (D5).
Next assignment is due in the least cost route, which is route S2D4. For this route, we can
allocate 100 units which is lesser of the corresponding demand (100 units) and (200 units).
By this allocation in route S2D4, the demand of destination D4 is consumed. So, this column is
now crossed out.

                               Assignment with destination D1, D4 and D5 consumed

Now, we work on the remaining matrix which excludes, column, D1, D4 and D5. Next
assignment is due in the least cost route of the remaining routes. Note that we have two
potential routes: S1D2 and S2D3. Both have 16 units of transportation cost. In case of any tie
(such as this), we select any of the routes. Let us select route, S1D2, and allocate 50 units
(minimum of demand of 150 and supply of remaining 50 units). With this, all supply of
source S1 is consumed. Therefore, cross out row of S1. We get the following matrix:

                                    Destination D1, D4 and D5 source S1 are consumed

Now, remaining allocation is done in route S2D3 (as 100 units). With this source, S2 is
consumed. Next allocation of 100 units is done in route S3D2 and 150 units in route S3D3.
Final initial assignment is as follows:

Total cost in this assignment is (13 × 100 + 16 × 50 + 100 × 0 + 16 × 100 + 15 × 100 + 17 ×

                                             Initial assignment by least cost method

 
Step 3:          Count the number of filled (or allocated) routes.

Decision rule

(i)             If filled route = (m + n – 1) then go for optimality check (i.e. step 5).

(ii)            If filled route < (m + n – 1) then the solution is degenerate. Hence, remove
degeneracy and go to step 4.

Here, m = number of destinations, including dummy column, if any

n = number of source, including dummy, row, if any

For our problem (m + n- l) = 5 + 3-1 = 7.

The number of filled route is equal to 7. Hence, problem is not degenerate. Therefore,
proceed to step 5.

Optimization of Initial Assignment

The initial feasible assignment is done by using least-cost method or North-West corner
method or Vogel's approximation method. However, none of these methods guarantees
optimal solution. Hence, next step is to check the optimality of the initial solution.

Step 5:   Check the optimality of the initial solution

For this, we have to calculate the opportunity cost of un-occupied routes.

 
First, we start with any row (or column). Let us select row 1, i.e., source S1; For this row, let
us define row value, u1 = 0. Now consider all filled routes of this row. For these routes,
calculate column values v. using following equation:

u1 + v1 = Cij (For any filled route)

where             u1 = row value

vj = column value

Cij = unit cost of assigned route

Once first set of column values (vj is known, locate other routes of filled cells in these
columns. Calculate next of ui (or vj values using above equation. In this way, for all rows and
columns, ui and vjvalues are determined for a non- degenerate initial solution.

Step 6:           Check the optimality

Calculate the opportunity of non-allocated orunfilled routes. For this, use the following
equation:

                                               Opportunity unassigned route = ui + vj – Cij

where             ui = row value

vj = column value

Cij = unit cost of unassigned route

If the opportunity cost is negative for all unassigned routes, the initial solution is optimal. If
in case any of the opportunity costs is positive, then go to next step.

Step 7:           Make a loop of horizontal and vertical lines which joins some filled routes with
the unfilled route, which has a positive opportunity cost. Note that all the corner points of
the loop are either filled cells or positive opportunity cost un-assigned cells.

Now, transfer the minimal of all allocations at the filled cells to the positive opportunity cost
cell. ¥orthis, successive corner points from unfilled cell are subtracted with this value.
Corresponding addition is done at alternate cells. In this way, the row and column addition
of demand and supply is maintained. We show the algorithm with our previous problem.

Let us consider the initial allocation of least-cost method (Fig. 12.10) :

For this, we start with row, S1and take u1 = 0. Now S1DpS1D2,and S1D5are filled cells. Hence,
for filled cells; (vj = Cij – ui).

v1 = 13 – 0 = 13

v2 = 16 – 0 = 16

v5 = 0 – 0 = 0

                               Calculation for ui and vj in least cost initial assignment

Now, cell S3D2 is taken, as this has a vj value. For this cell u3 = 17 – 16 = 1
 

Now, cell S3D3 is selected, as this has a ui value. For this cell v3 = 17 – 1 = 16

Now, cell S2D3 is selected, as it has a vj value. For this cell u2 = 16 – 16 = 0

Now, cell S2D4 is selected, as it has a ui value. For this cell v4 = 15 – 0 = 0

Thus, all ui and vj are known.

Step 6: Calculate opportunity cost of un-assigned routes.

Unassigned route Opportunity cost (ui + vj – Cij)

S1D3 0 + 16 – 19 = –3

S1D4 0 + 15 – 17 = –2

S2D1 0 + 13 – 17 = –4

S2D2 0 + 16 – 19 = –3

S2D5 0+0–0=0

S3D1 1 + 13 – 15 = –2

S3D4 1 + 15 – 16 = 0

S3D5 1 + 0 – 0 = +1

Since route S3D5 has positive opportunity cost, the solution is non-optimal; hence, we go to
next step and make a loop as follows.

                                               Closed loop for cell S3D5

The revised allocation involves 100 units transfer from cells S1D5 and S3D2 to cells S3D5 and
S1D2.

Thus, revised allocation is as follows:

                                                       Revised allocation in least-cost assignment

Since above solution is degenerate now, we allocate  to the least-cost un-filled cell S1D5.
Fresh calculation of ui and vj is also done in the similar way as explained in Step 5.

For this assignment, the opportunity cost of unassigned cells is as follows.

Now, since un-allocated routes have negative (or zero) opportunity cost, the present
assignment is the optimal one. Thus, optimal allocation of route is given in Figure.

Note that total cost is less than the initial assignment cost of least-cost method (= Rs. 9450).

Similarly, optimality of North-West corner method solution is done.

Unassigned route Opportunity cost (ui + vj – Cij)

S1D3 0 + 17 – 19 = –2
 S1D4 0 + 16 – 17 = –1

S2D1 –1 + 13 – 17 = –5

S2D2 –1 + 16 – 19 = –4

S2D5 –1 + 0 – 0 = –1

S3D1 0 + 13 – 15 = –0

S3D2 0 + 16 – 17 = –1

S3D4 0 + 16 – 16 = 0

                                                                  Opportunity cost

Route Unit Cost in this route

S1D1 100 13 × 100 = 1300

S1D2 150 16 × 150 = 2400

S2D3 100 16 × 100 = 1600

S2D4 100 15 × 100 = 1500

S3D3 150 17 × 150 = 2550

S3D5 100 0 × 100 = 0

Total cost = Rs.9350

                                        Optimal allocation in different routes