A tourist in New York City uses local transportation to visit 8 sites. The start and end and the order in which the sites are visited are unimportant. What is important is to spend the least amount of money on transportation. Matrix ‘cij ‘ below provides the fares in dollars between the different locations.

‘cij ‘ = ®

0 20 30 25 12 33 44 57 22 0 19 20 20 29 43 45 28 19 0 17 38 48 55 60 25 20 19 0 28 35 40 55 12 18 34 25 0 21 30 40 35 25 45 30 20 0 25 39 47 39 50 35 28 20 0 28 60 38 54 50 33 40 25 0



The tourist is budgeting $120 for cab cost to all eight sites. Is this a realistic expectation?

(Hint: This is an open-tour TSP.)