Friday, July 12, 2013

The Stepping Stone Method

The Stepping Stone Method

Once an initial feasible solution to a transportation problem is determined by any of the previous methods, the next step is to solve the model for the optimal solution.
The Stepping Stone Method is an iterative technique used to evaluate the cost effectiveness of  the shipping routes not currently in the solution.
When applying it, we test each unused cell, or square, in the transportation table by asking : What would happen to the total shipping cost if one unit of product was tentatively shipped to an unused route?

To illustrate the same, let us look at the initial solution of the Bengal Plumbing Problem derived by the Northwest Corner Rule.

Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
100
Rs.50

Rs.40

Rs.30
100
Plant B
200
Rs.80
100
Rs.40

Rs.30
300
Plant C

Rs.90
100
Rs.70
200
Rs.50
300
Warehouse Requirement
300
200
200
700








The total shipping cost as computed by Northwest Corner Rule comes out to be Rs. 42000.00

To apply the Stepping Stone Method to the Bengal Plumbing data to evaluate unused shipping routes, we will take the following steps.

Step 1 : Select any unused square to evaluate.
In the above example we can see four currently unassigned routes.
  1. Plant A to Warehouse F (AF)
  2. Plant A to Warehouse G (AG)
  3. Plant B to Warehouse G (BG)
  4. Plant C to Warehouse E (CE)
Let us select the route (AF).

Step 2 : Beginning at this square, trace a closed path back to it via squares that are currently being used. Only horizontal and vertical moves are permissible, and we can take turns only at the occupied squares. we may however, step over either an empty or an occupied square.

Step 3 : Beginning with (+) sign at the unused square, place alternating (-) and (+) signs on each corner square of the closed path just traced as shown below.

Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
(-) 100
Rs.50
(+)
Rs.40

Rs.30
100
Plant B
(+) 200
Rs.80
(-) 100
Rs.40

Rs.30
300
Plant C

Rs.90
100
Rs.70
200
Rs.50
300
Warehouse Requirement
300
200
200
700

Because we are testing the cost effectiveness of shipping route (AF) against the current route selection, we try shipping one unit from Plant (A) to Warehouse (F) and represent the same by placing a (+) sign in the cell (AF).

By shipping an additional unit to route (AF) we are disagreeing with the supply restrictions of Plant (A) and demand constraints of Warehouse (F).

Hence to balance the status we need to ship one unit less to route (AE), by placing a (-) sign. Similarly we will place a (+) sign at route (BE) and a (-) sign at route (BF). Placing alternating positive and negative signs on all corners of the tracked closed path as mentioned in Step 3.

Step 4 : Calculate an Improvement Index for the proposed route by adding the unit figures of all the cells of the closed path as follows.

Evaluation of Plant (A) to Warehouse (F) route.
Route (AF) = (+) 1 X 40 = (+) 40
Route (AE) = (-) 1 X 50 = (-) 50
Route (BE) = (+) 1 X 80 = (+) 80
Route (BF) = (-) 1 X 40 = (-) 40

Result of proposed shift in allocation = +40-50+80-40 = (+) 30
Hence we can conclude that the Improvement Index for the route (AF) = (+) 30

This means that for every unit shipped via the Plant (A) to Warehouse (F) route, total transportation cost will increase by Rs.30 over their current level.

Step 5 : Repeat steps 1 to 4 to calculate the Improvement Index of all the unused cells. If all the indices computed are greater than or equal to zero, we have reached an optimal solution. If not the current solution can be improved further to decrease total shipping costs.

Let us now examine Plant (A) to Warehouse (G) route, which is slightly more difficult to trace with a closed path. 

Except for the route currently being evaluated we have to use only occupied squares to place (+) or (-) signs.

Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
(-) 100
Rs.50

Rs.40
(+)
Rs.30
100
Plant B
(+) 200
Rs.80
(-) 100
Rs.40

Rs.30
300
Plant C

Rs.90
(+) 100
Rs.70
(-) 200
Rs.50
300
Warehouse Requirement
300
200
200
700

In the above table, we have turned corners along the path only at squares with existing routes and have skipped over the empty cells (Route AF & Route BG) following Step 2. 

Evaluation of Plant (A) to Warehouse (G) route.
Route (AG) = (+) 1 X 30 = (+) 30
Route (AE) = (-) 1 X 50 = (-) 50
Route (BE) = (+) 1 X 80 = (+) 80
Route (BF) = (-) 1 X 40 = (-) 40
Route (CF) = (+) 1 X 70 = (+) 70
Route (CG) = (-) 1 X 50 = (-) 50

Result of proposed shift in allocation = +30-50+80-40+70-50 = (+) 40
Hence we can conclude that the Improvement Index for the route (AG) = (+) 40
Again, opening this route fails to lower our total shipping costs.

Two other routes can be evaluated in a similar fashion.

1. Plant (B) to Warehouse (G) route = (BG)

Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
100
Rs.50

Rs.40

Rs.30
100
Plant B
200
Rs.80
(-) 100
Rs.40
(+)
Rs.30
300
Plant C

Rs.90
(+) 100
Rs.70
(-) 200
Rs.50
300
Warehouse Requirement
300
200
200
700

Evaluation of Plant (B) to Warehouse (G) route.
Route (BG) = (+) 1 X 30 = (+) 30
Route (BF) = (-) 1 X 40 = (-) 40
Route (CF) = (+) 1 X 70 = (+) 70
Route (CG) = (-) 1 X 50 = (-) 50

Result of proposed shift in allocation = +30-40+70-50 = (+) 10
Improvement Index for the route (BG) = (+) 10
Opening this route also fails to lower our total shipping costs.

2. Plant (C) to Warehouse (E) route = (CE)

Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
100
Rs.50

Rs.40

Rs.30
100
Plant B
(-) 200
Rs.80
(+) 100
Rs.40

Rs.30
300
Plant C
(+)
Rs.90
(-) 100
Rs.70
200
Rs.50
300
Warehouse Requirement
300
200
200
700

Evaluation of Plant (C) to Warehouse (E) route.
Route (CE) = (+) 1 X 90 = (+) 90
Route (BE) = (-) 1 X 80 = (-) 80
Route (BF) = (+) 1 X 40 = (+) 40
Route (CF) = (-) 1 X 70 = (-) 70

Result of proposed shift in allocation = +90-80+40-70 = (-) 20
Improvement Index for the route (CE) = (-) 20
Because this last index is negative, we can realize cost savings by using the (currently unused) Plant (C) - Warehouse (E) route.

In the above example, we see that a better solution is indeed possible because we can calculate a negative improvement index on one of the unused routes.
Each negative index represents the amount by which total transportation costs could be decreased if one unit is shipped by that route.

Step 6 : The next step is to choose the route with the largest negative improvement index and ship the maximum allowable number of units on that route and reduce the total shipping cost accordingly.

The maximum quantity that can be shipped on our new money saving route can be found by referring to the closed path with the largest negative improvement index and selecting the square with the smallest number containing a negative sign.
To obtain a new solution, we add this number to all squares of the closed path containing positive signs and subtract it from all squares containing negative signs. 

In this case, the smallest cell with a negative sign is cell (CF), containing 100 units.
To improve our Bengal plumbing solution we have to take the following four steps.
  1. Add 100 units to cell (CE), assigning 100 units to route (CE)
  2. Subtract 100 units from cell (CF), limiting the supply of Plant (C) to 300 units.
  3. Add 100 units to cell (BF), assigning a total of 200 units to route (BF)
  4. Subtract 100 units from cell (BE), bringing down the allocation to 100 units for route (BE)
Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
100
Rs.50

Rs.40

Rs.30
100
Plant B
100
Rs.80
200
Rs.40

Rs.30
300
Plant C
100
Rs.90

Rs.70
200
Rs.50
300
Warehouse Requirement
300
200
200
700

After the above assignment,
The total shipping cost has been reduced by (100 units) X (Rs.20 saved per unit) = Rs.2000.00

Improved Solution of Bengal Plumbing
From
To
Units Shipped
Cost per unit
Total Cost
Plant A
Warehouse E
100
Rs.50
Rs.5000
Plant B
Warehouse E
100
Rs.80
Rs.8000
Plant B
Warehouse F
200
Rs.40
Rs.8000
Plant C
Warehouse E
100
Rs.90
Rs.9000
Plant C
Warehouse G
200
Rs.50
Rs.10000
Total Shipping Cost
Rs.40000

The total computed shipping cost has come down to to Rs.40000.00 as compared to Rs.42000.00 derived by Northwest Corner Rule.

One iteration of Stepping Stone method is now complete. We must test again to see if the solution is optimal or we can make any further improvements.
We do this by evaluating each unused square, as previously described.

Currently we have four unused routes.
  1. Plant A to Warehouse F (AF)
  2. Plant A to Warehouse G (AG)
  3. Plant B to Warehouse G (BG)
  4. Plant C to Warehouse F (CF)
Evaluating these four routes we can find that the Route (BG) has a negative Improvement Index.

Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
100
Rs.50

Rs.40

Rs.30
100
Plant B
(-) 100
Rs.80
200
Rs.40
(+)
Rs.30
300
Plant C
(+) 100
Rs.90

Rs.70
(-) 200
Rs.50
300
Warehouse Requirement
300
200
200
700

Evaluation of Plant (B) to Warehouse (G) route.
Route (BG) = (+) 1 X 30 = (+) 30
Route (BE) = (-) 1 X 80 = (-) 80
Route (CF) = (+) 1 X 90 = (+) 90
Route (CG) = (-) 1 X 50 = (-) 50

Result of proposed shift in allocation = +30-80+90-50 = (-) 10
Improvement Index for the route (BG) = (-) 10
Hence we can realize further cost savings by using the (currently unused) Plant (B) - Warehouse (G) route.

Following is the improved solution for Bengal Plumbing problem using Route (BG).

Transportation Matrix for Bengal Plumbing
From \ To
Warehouse E
Warehouse F
Warehouse G
Factory Capacity
Plant A
100
Rs.50

Rs.40

Rs.30
100
Plant B

Rs.80
200
Rs.40
100
Rs.30
300
Plant C
200
Rs.90

Rs.70
100
Rs.50
300
Warehouse Requirement
300
200
200
700

The total computed shipping cost with this iteration is Rs.39000.00 as compared to the previous result of Rs.40000.00

Improved Solution for Bengal Plumbing Problem by Stepping Stone Method
From
To
Units Shipped
Cost per unit
Total Cost
Plant A
Warehouse E
100
Rs.50
Rs.5000
Plant B
Warehouse F
200
Rs.40
Rs.8000
Plant B
Warehouse G
100
Rs.30
Rs.3000
Plant C
Warehouse E
200
Rs.90
Rs.18000
Plant C
Warehouse G
100
Rs.50
Rs.5000
Total Shipping Cost
Rs.39000
 











Hence we can say that we have realized considerable savings in the total shipping costs using the Stepping Stone method.