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 squyares and use the destination costs found earlier to establish the source cost for the row. This done, find any other unknown destination costs.

  5. 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 %theta 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-%theta

%theta


23

Quarry B


2+%theta

14-%theta


16

Quarry C



1

18

19

Demand for Gravel (Tons)

12

13

15

18

58

Maximise %theta that leave all the matrix entries positive. Inspection gives %theta = 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 %theta in the corresponding matrix cell.


Site 1

Site 2

Site 3

Site 4

Supply of Gravel (Tons)

Quarry A

12

0

11 - %theta

%theta

23

Quarry B


13

3


16

Quarry C



1+ %theta

18- %theta

19

Demand for Gravel (Tons)

12

13

15

18

58

Add comment

Security code
Refresh