The transportation problem describes a situation where identical goods are to be transported from several supply points to several destination points via several routes. Each route from an individual supply point to an individual destination point has an associated cost, and the problem is to minimize the overall cost while meeting all the demand.
We can represent the problem in the form of a matrix. The matrix below shows the costs of transporting gravel from three quarries, A, B and C, to four building sites X, Y, W and Z.
|
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 total amount of gravel that can be supplied by quarries A, B and C are 23, 16 and 19 respectively, while site 1 has a demand of 12, site 2 has a demand of 13, site 3 has a demand of 11 and site 4 has a demand of 22.
The costs, in pounds, of transporting one ton of gravel from each quarry to each site are highlighted in yellow above. The cost of transporting one ton of gravel from quarry B to site 2 for example, is £110.
Solving the Transportation Problem
The process of solving the transportation problem is as follows:
-
Find an initial solution that uses all the gravel supplied and meets all the demands.
-
Calculate the total cost of the solution and see if it can be reduced by changing a route from a high cost route to a low cost route not currently used. If this is not possible the solution is optimal.
-
If the cost can be reduced by using a new route, allocate as many tons of gravel to this new route from from a high cost route.
-
Check the new solution as in 2 above. When no more savings are possible an optimal solution has been found.