Skip to main content

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.

Comments

Popular posts from this blog

The Intuitive Lowest Cost Method

The Intuitive Lowest Cost Method Or The Minimum Cell Cost Method The Intuitive Lowest Cost Method is a cost based approach to finding an initial solution to a transportation problem. It makes allocations starting with the lowest shipping costs and moving in ascending order to satisfy the demands and supplies of all sources and destinations. This straightforward approach uses the following steps. Identify the cell with the lowest cost. Allocate as many units as possible to that cell without exceeding the supply or demand. Then cross out the row or column or both that is exhausted by the above assignment. Move on to the next lowest cost cell and allocate the remaining units. Repeat the above steps as long as all the demands and supplies are not satisfied.  When we use the Intuitive Approach to the Bengal Plumbing problem, we obtain the solution as below. Transportation Matrix for Bengal Plumbing From \ To Warehouse E Warehouse F Warehou

Vogel's Approximation Method (VAM)

The Vogel's Approximation Method In addition to the North West Corner and Intuitive Lowest Cost Methods for setting an initial solution to transportation problems, we can use another important technique - Vogel's Approximation Method (VAM). Though VAM is not quite as simple as Northwest Corner approach, but it facilitates a very good initial solution, one that is often the optimal solution. Vogel's Approximation Method tackles the problem of finding a good initial solution by taking into account the costs associated with each alternative route, which is something that Northwest Corner Rule did not do. To apply VAM, we must first compute for each row and column the penalty faced if the second best route is selected instead of the least cost route . To illustrate the same, we will look at the Bengal Plumbing transportation problem. Transportation Matrix for Bengal Plumbing From \ To Warehouse E Warehouse F Warehouse G Factory Capacity Plant A