PROCEDURE FOR OPTIMIZING TRANSPORTATIUON COST

 

 

Step 1:  Feasible Solution:     North West

                                                Cheapest Cell

                                                Vogell’s Aproximation Method

 

 

Step 2.  Verify that the number of non empty cells is: r + c- 1

 

(Number of Rows + Number of Columns –1).  This is the number of independent

 

constraints in a transportation problem.  If the number of empty cells fall short, add  zero to empty cell(s) and consider them as non empty cells with zero to bring the total number of considered non empty cells to r + c- 1.

 

 

 

Step 3.  For Non Empty Cells only:

 

              Factor the transportation cost per unit  to a row r_i and a column k_j  effects.

 

Since you have r + c- 1 independent constraints you can determine the score r₁ = 0.

 

Next solve for the rest of the r_i s and k_j s.

 

 

Step 4.  For Empty Cells only:

 

             Calculate the maximal improvement per unit shipped,

 

 -  r_i - k_j

 

 

Step 5:  Identify a cell with the highest improvement per unit shipped: 

              This improvement must be a negative number with a highest absolute value.

  If no negative improvement number is available, stop!  You have achieved the  Minimum Cost arrangement.  Calculate the overall optimal cost.

 

             This is your entering cell.

 

Step 6.  Find a balanced path that adds a unit at the entering cell where the net            improvement per unit on units shipped on the path is equal to the improvement

per unit shipped of the entering cell.  

 

 

Notice.  In a balanced path the number of + and – are equal in every row and in every column, thus the net effect on every row and column is zero

Notice:  In a balanced path at cells where minus signs are present there must be some quantity shipped because it is impossible to subtract quantity from empty cells.

 

Notice:  There may be more than one balanced path, but we are looking for a balanced path where the total net improvement per unit shipped  is identical with that of the entering cell.

 

Step 7.  Maximizing the improvement.

On the selected path identify the cells where minus signs (-) are present.  These   are the cells where quantity shipped must be reduced.   By maximizing the reduction we will reduce the overall transportation cost maximally.  The maximal quantity that can be reduced is the minimal quantity available in these cells.   For example, if the initial quantities in the cells from which we subtract are 100, 200 and 300, in an example with three cells, with minus signs, then the maximal quantity we can reduce is 100 units.  After subtraction of 100 units the cell that contained initially the 100 units becomes empty and we cannot subtract any additional units from it.  We refer to this cell as the exiting cell.

 

Suppose the maximal improvement per unit is 19 and the maximal number of units that can be subtracted is 100, then the maximal improvement is

19 times 100 = 1900 reduction in the overall transportation cost.

 

 

            Notice, it is possible that two or more cells will be exiting.  For example, suppose

             we subtract from three cells with initial quantities of 100, 100 and 300.  The

minimal quantity of 100 is now found at 2 cells.  As a result after subtraction of this minimal quantity two cells will become empty and the third will contain 200 units.  Two cells will exit. 

In this case, the number of non empty cells drops to r + c-2 because one cell enter and two exit. To bring the number of non empty cells to the required

 r + c-1 it is necessary to introduce a zero to one of the empty cells and consider it as a non empty cell with a zero quantity.

 

      The process repeats itself from step 2 and on.