The Traveling Salesman Problem 1: Optimal Paths
A salesman, starting from his home city, needs to visit every city on his route exactly once and finally return home. As there are only a finite number of possibilities, it is plausible for him to select the visiting order so that the total distance traveled in his tour is as small as possible. All the data he needs is to know for each pair of cities the distance from one to the other.[more]
Because of its wealth of applications, this problem, called the traveling salesman problem (TSP), has received much attention since 1931. It has turned out to be not at all simple to use the data to get an answer, and so this problem has gained a reputation for being one of the most important unsolved problems of our time. The search for efficient methods to solve it (since it was shown to be NP-hard, which roughly means that the solution time by any method we apply to it exceeds any practical bounds) now concentrates mainly in heuristic approximation methods.[less]
 E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, New York: John Wiley & Sons, 1985.