The Traveling-Salesman Problem

Abstract

The traveling-salesman problem is that of finding a permutation P = (1 i 2 i 3 … i n ) of the integers from 1 through n that minimizes the quantity [Formula: see text] where the a αβ are a given set of real numbers. More accurately, since there are only (n − 1)′ possibilities to consider, the problem is to find an efficient method for choosing a minimizing permutation. This problem was posed, in 1934, by Hassler Whitney in a seminar talk at Princeton University. There are as yet no acceptable computational methods, and surprisingly few mathematical results relative to the problem.