Travelling And Salesman Problems In Assignment Model

Solution:  COCM

We can make only 4 assignments. Hence modify the matrix. Smallest element in the uncovered cells is 3, deduct this from all other uncovered cells and add this to the elements at the crossed cells. Do not alter the elements in cells covered by the line.

TOCM

We can make only 4 assignments. Hence once again modify the matrix. Sequencing: A to C, C to B, B to E, E to D, and D to A. As there is a tie

TOCM

Sequencing: A to C, C to B, B to E, E to D and D to A. as there is a tie between the zero cells, the problem has alternate solution. The total distance traveled by the salesman is: 18 14 14 11 12 = 69 Km.

A to C to B to E to D to A, the distance traveled is 69 Km.

Note: See that no city is visited twice by sales man.