The Salesperson's Journey


The following table presents the airplane fares (in dollars) among pairs of seven cities. A salesperson needs to visit each of the cities at least once. Find the minimum fare for the salesperson to visit each city at least once and return to the home city. In otherwords, assuming the salesperson lives in NYC, what travel route should be followed to visit each city at least once and return home?

 

   ATL CHI MIA STL DLS SF NYC
ATL  0 153 152 136 174 411 177
CHI   153 0 239 87 204 368 204
MIA  152  239 0 224 247 394 227
STL   136 87 224 0 148 336 216
DLS   174 204 247 148
0
283 264
SF   411 368 394 336 283 0 478
 NYC  177 204 227 216 264 478 0



 

Does it matter which city is the home city? Does a map help to understand the problem? With seven cities we probably are not wanting to do an exhaustive calculation of all possible routes, but rather we need a heuristic search for an algorithm that gives the "best" route, or at least one of the better routes.


Return to the EMAT 4600/6600 Page

Taken from a problem presented in a TWA travel magazine many years ago.