Mr Iyer is a salesman with Delite Manufacturing Company. He wants to visit six cities, say, 1, 2, 3, 4, 5 and 6, starting with city 1 where he is stationed. The distances between various cities are given in the Table 7.10.

Mr Iyer wants to develop a tour through the five other cities and return to his home city in such a way that he has to travel the minimum distance.

It may be noted that the matrix of the distances between different cities is not a symmetrical one. For instance, the distance from city 1 to 2 is not given to be the same as the distance from city 2 to 1. Such situations may develop because of several reasons. In the one-way traffic system, for example, the distance to be covered to reach a point might be different from the distance to be covered while returning.