For all of its complexity, given more than four or five cities, the TSP may still be unable to deal with the real world. Consider the "too simple" problem of three cities, mentioned on the Module 3 Home page. A is an airline hub, such as Atlanta; B and C are satellite cities. There are flights between A and B, and also between A and C; but there are no flights between B and C,other thanthrough A. Here's the relevant information.

Via Air:Flying Time (hrs:mins)AirfareAB1:30$500BA1:30$420AC0:50$380CA0:50$300CB (via A)2:30 (incl. layover at A)$400BC (via A)3:50 (incl. layover at B)$590Via rental carDriving timeMileage + drop-off feeBC3:45$120CB3:45$100A salesman wants to visit all three cities on one day, starting and finishing in A.

1. What's his best plan, if he wants to minimize time?
2. What's his best plan if he wants to minimize cost?