Time Minimizing Transportation Problem

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.

Steps in Time Minimizing Problem

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

• North West Corner Rule
• Matrix Minimum Method
• Vogel Approximation Method

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.

Example 1: Time Minimizing Transportation Problem

The following matrix gives data concerning the transportation times t_ij

Solution.

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

Table 1

On small screens, scroll horizontally to view full calculation

Here, t₁₁ = 25, t₁₂ = 30, t₁₃ = 20, t₂₃ = 20, t₂₄ = 30, t₃₄= 35, t₃₅ = 45, t₄₅ =30, t₄₆ = 25

Choose maximum from t_ij, i.e., T₁ = 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

Use Horizontal Scrollbar to View Full Table Calculation

Here, T₂ = Max(25, 30, 20, 20, 20, 35, 45, 22, 30) = 45. Now, cross out all the unoccupied cells that are ≥ T₂.

Table 4

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

Table

T₃ = Max(25, 30, 20, 20, 30, 40, 35, 22, 30) = 40. Now, cross out all the unoccupied cells that are ≥ T₃.

Now we cannot form any other closed loop with T₃.
Hence, the solution obtained at this stage is optimal.
Thus, all the shipments can be made within 40 units.