Using the Stepping Stone Method to Find an Improved Solution to the Transportation Problem

The stepping stone method is an algorithm for swapping the routes between sites that supply and receive goods.

We start with the matrix below, representing the costs of transporting from each quarry to each site, together with the supply capacity of each quarry and the receiving capacity of each site.

The 'North West Corner Method' gives the starting solution shown below.

To find an improved solution, we must find the shadow costs associated with each quarry and building site. The process is:

1. Set the cost associated with the source (quarry) to zero. The destination cost is then the total cost of transportation.

2. Move along the row to any other non empty squares and find the destination costs in the same way, by setting the source costs to zero.

3. When all possible destination costs for that row have been determined, go to the start of the next row.

4. Move along the row to any non empty squares and use the destination costs found earlier to establish the source cost for the row. This done, find any other unknown destination costs.

Repeat 3 and 4 above until all source and destination costs have been found.

For example, destination and source costs are shown for the table at the top of the page in the table below, only the costs corresponding to the routes in the north west corner solution being considered.

We have

C(A)+C(1)=150 (1)

C(A)+C(2)=200 (2)

C(B)+C(2)=110 (3)

C(B)+C(3)=190 (4)

C(C)+C(3)=180 (5)

C(C)+C(4)=100 (6)

Setting the cost associated with quarry A, C(A) to zero gives C(1)=150.

Then from (2), C(2)=200

From (3), C(B)=110-C(2)=110-200=-90

From (4), C(3)=190—C(B)=190- -90=280

From (5), C(C)=180-C(3)=180- 280=-100

From (6), C(4)=100-C(C)=100- -100=200.

We can put the costs for each site in the matrix.

Now find the improvement indices for routes not included in the initial north west corner solution (the empty squares above).

I(B1)=130-C(B)-C(1)=130—90-150=70

I(C1)=120-C(C)-C(1)=120—100-150=70

I(C2)=170-C(C)-C(2)=170—100-200=70

I(A3)=140-C(A)-C(3)=140-0-280=-140

I(A4)=160-C(A)-C(4)=160-0-200=-40

I(B4)=220-C(B)-C(4)=220—80-200=100

The most negative is I(A3)= -140 so we can reduce the cost by introducing route A3. Put Θ in the box A3 and make the rows and columns satisfy supply and demand constraints.

Maximise Θ that leave all the matrix entries positive. Inspection gives Θ = 11. We have the table below.

Compute the new improvement indices.

I(B1)=130-C(B)-C(1)=130—90-150=70

I(C1)=120-C(C)-C(1)=120—100-150=70

I(C2)=170-C(C)-C(2)=170—100-200=70

I(A2)=200-C(A)-C(2)=0

I(A4)=160-C(A)-C(4)=160-0-200=-40

I(B4)=220-C(B)-C(4)=220—80-200=100

The most negative is I(A4)=-40 so we can reduce the cost by introducing route A4. The Θ in the corresponding matrix cell.