In the **Time Minimizing Transportation Problem** the
objective is to minimize the time.

This problem is same as the transportation
problem of minimizing the cost, expect that the unit transportation
cost is replaced by the time t_{ij}.

1. Determine an initial basic feasible solution using any one of the following:

2. Find T_{k} for this feasible plan and cross out all the
unoccupied cells for which t_{ij} ≥
T_{k}.

3. Trace a closed path for the occupied cells corresponding to T_{k}.
If no such closed path can be formed, the solution obtained is optimum
otherwise, go to step 2.

The following matrix gives data concerning the transportation times
t_{ij}

Destination | |||||||
---|---|---|---|---|---|---|---|

Origin | D1 | D2 | D3 | D4 | D5 | D6 | Supply |

O1 | 25 | 30 | 20 | 40 | 45 | 37 | 37 |

O2 | 30 | 25 | 20 | 30 | 40 | 20 | 22 |

O3 | 40 | 20 | 40 | 35 | 45 | 22 | 32 |

O4 | 25 | 24 | 50 | 27 | 30 | 25 | 14 |

Demand | 15 | 20 | 15 | 25 | 20 | 10 |

Solution.

We compute an initial basic feasible solution by north west corner rule which is shown in table 1.

Table 1

Destination | |||||||
---|---|---|---|---|---|---|---|

Origin | D1 | D2 | D3 | D4 | D5 | D6 | Supply |

O1 | 40 | 45 | 37 | 37 | |||

O2 | 30 | 25 | 40 | 20 | 22 | ||

O3 | 40 | 20 | 40 | 22 | 32 | ||

O4 | 25 | 24 | 50 | 27 | 14 | ||

Demand | 15 | 20 | 15 | 25 | 20 | 10 |

Here, t_{11} = 25, t_{12} = 30, t_{13} = 20,
t_{23} = 20, t_{24 }= 30, t_{34}= 35, t_{35} = 45, t_{45} =30, t_{46} = 25

Choose maximum from t_{ij}, i.e., T_{1} = 45. Now,
cross out all the unoccupied cells that are ≥
T1.

The unoccupied cell (O3D6) enters into the basis as shown in table 2.

Table 2

Choose the smallest value with a negative position on the closed path, i.e., 10. Clearly only 10 units can be shifted to the entering cell. The next feasible plan is shown in the following table.

Table 3

Destination | |||||||
---|---|---|---|---|---|---|---|

Origin | D1 | D2 | D3 | D4 | D5 | D6 | Supply |

O1 | 40 | 37 | 37 | ||||

O2 | 30 | 25 | 40 | 20 | 22 | ||

O3 | 40 | 20 | 40 | 32 | |||

O4 | 25 | 24 | 27 | 25 | 14 | ||

Demand | 15 | 20 | 15 | 25 | 20 | 10 |

Here, T_{2} = Max(25, 30, 20, 20, 20, 35, 45, 22, 30) = 45.
Now, cross out all the unoccupied cells that are ≥
T_{2}.

Table 4

By following the same procedure as explained above, we get the following revised matrix.

Table

Destination | |||||||
---|---|---|---|---|---|---|---|

Origin | D1 | D2 | D3 | D4 | D5 | D6 | Supply |

O1 | 37 | 37 | |||||

O2 | 30 | 25 | 20 | 22 | |||

O3 | 20 | 32 | |||||

O4 | 25 | 24 | 27 | 25 | 14 | ||

Demand | 15 | 20 | 15 | 25 | 20 | 10 |

T_{3} = Max(25, 30, 20, 20, 30, 40, 35, 22, 30) = 40. Now,
cross out all the unoccupied cells that are ≥
T_{3}.

Now we cannot form any other closed loop with T_{3}.

Hence, the solution obtained at this stage is optimal.

Thus, all the shipments can be made within 40 units.