ABSTRACT
The traveling salesman problem (TSP) provides a classic example of a di- cult combinatorial optimization problem that can be easily explained to the layperson. A person located at a home base must visit a set of n cities and then return home, while traveling the least total distance (or incurring the lowest cost) possible. The data required in solving the problem includes the number of cities and the set of all pairwise inter-city distances. In the symmetric version of the TSP, the inter-city distance from city i to city j is the same as that from city j to city i; when considering straight-line Euclidean distances or two-way road travel distances, symmetric distances are not unlikely to apply. The general version of the TSP does not, however, impose such a symmetry requirement. Minimizing the total distance traveled serves as one possible goal; alternatively, one may wish to minimize the total cost incurred in visiting the set of cities, in which case asymmetric distances may be reasonable. For example, if air travel is involved, then it is not unlikely for the cost to travel from city i to city j to dier from the cost from j to i.
