## The Transportation Problem - The North West Corner Method

The transportation problem describes a situation where the total cost of transporting identical goods over several routes between various sources of supply and points of demand is to be minimized. A starting solution – one that meets all the demand and uses all the supply, can be found using the 'north west corner method'. The process is shown for the transportation problem below.

Gravel is to be transported from three quarries A, B and C, to four building sites 1, 2, 3 and 4. The quantity that each quarry can supply is shown in the rightmost column and the quantity that each building site demands is shown in the bottom row. The highlighted entries are the costs in £ of transporting a ton of gravel between quarry and site, so that the cost of transporting a ton of gravel between quarry C and site 1 is £120, for example.

 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

We can construct a feasible solution as shown below. Starting at the top left hand corner, allocate the maximum available quantity to meet the demand at this destination – 12.

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

We can construct a feasible solution as shown below. Starting at the top left hand corner, allocate the maximum available quantity to meet the demand at this destination, site 1, so that site 1 will be sent 12 tons of gravel from quarry A..

From quarry A, a possible 23-12=11 tons is available to be sent to site 2

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

Site 2 demands an extra 2 tons of gravel on top of the 11 sent from quarry A, and this can be supplied by quarry B.

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

Quarry B then has 14 units of gravel available to be sent to site 3.

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

Site 3 demands an extra 1 ton of gravel, which can be supplied by quarry C.

 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 19 Demand for Gravel (Tons) 12 13 15 18 58

Quarry C then has 18 units of gravel available to be sent to site 4.

 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

The total cost of this solution is 12*150+11*200+2*110+14*190+1*180+18*100=£7060.