Computer Solutions of the Traveling Salesman Problem

The traveling salesman problem may be stated as follows: "A salesman is required to visit each of the n given cities once and only once, starting from any city and returning to the original place of departure. What route, or tour, should he choose in order to minimize the total distance traveled?" Instead of distance, other notions such as time, cost, etc., can be considered as well. In this paper, we shall use the term "cost" to represent any such notion. Mathematically, the problem may be stated in the following two equivalent ways: (1) Given a "cost matrix" D = (dij), where dij = cost of going from 2245 2246 THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1965 city i to city j, (i, j = 1, 2, · · · , n), find a permutation P = (ii, i2, u , · · · , in) of the integers from 1 through n that minimizes the quantity u » I Jo + d + · · · + dini, (2) Given a "cost matrix" D as above, determine x^ which minimizes the quantity Q = y^ij difca subject to (a) (b) (c) and (d) for any subset S -- [i, , · · · , iT) of the integers from 1 through