## 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.

 Site 1 Site 2 Site 3 Site 4 Supply of Gravel (Tons) Quarry A 150 200 140 160 23 Quarry B 130 110 190 220 16 Quarry C 120 170 180 100 19 Demand for Gravel (Tons) 12 13 11 22 58

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

 Site 1 Site 2 Site 3 Site 4 Supply of Gravel (Tons) Quarry A 12 11 23 Quarry B 2 14 16 Quarry C 1 18 19 Demand for Gravel (Tons) 12 13 15 18 58

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.

 C(1) C(2) C(3) C(4) C(A) 150 200 C(B) 110 190 C(C) 180 100

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.

 C(1)150 C(2)200 C(3)280 C(4) 200 C(A)0 150 200 C(B)-90 110 190 C(C)-100 180 100

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.

 Site 1 Site 2 Site 3 Site 4 Supply of Gravel (Tons) Quarry A 12 11-Θ Θ 23 Quarry B 2+Θ 14-Θ 16 Quarry C 1 18 19 Demand for Gravel (Tons) 12 13 15 18 58

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

 Site 1 Site 2 Site 3 Site 4 Supply of Gravel (Tons) Quarry A 12 0 11 23 Quarry B 13 3 16 Quarry C 1 18 19 Demand for Gravel (Tons) 12 13 15 18 58

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.

 Site 1 Site 2 Site 3 Site 4 Supply of Gravel (Tons) Quarry A 12 0 11 - Θ Θ 23 Quarry B 13 3 16 Quarry C 1+ Θ 18- Θ 19 Demand for Gravel (Tons) 12 13 15 18 58 