Question

A natural truck-rental service has a surplus of one truck in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one truck in each of the cities 7, 8, 9, 10, 11 and 12. The distance (in kilometres) between the cities with a surplus and the cities with a deficit are displayed below:

How should the truck be dispersed so as to minimize the total distance travelled?

Answer 1

The number of rows equals the number of columns. So the problem is a balanced assignment problem and we can get an optimal solution. 

Step 1: Subtract the minimum element of each row from all elements of that row.

Step 2: Subtract the least element of each column from all elements of that column.

Step 3: (Assignment)

We are not able to assign city for starting place 4. We proceed as follows. 

Draw a minimum number of lines to cover all the zeros of the matrix. Subtract the smallest element from all uncovered elements and add to the elements which lie at the intersection of two lines.

Then we obtain a new reduced matrix for fresh assignment.

Final dispersal

Thus the minimum total distance the trucks should travel is 125 km.