Dynamic Programming Treatment of the Travelling Salesman Problem¶
Authors: Richard Bellman
Published: 1962 (Journal Paper)
Source: Journal of the ACM
DOI: 10.1145/321105.321111
Summary¶
Abstract¶
The well-known travelling salesman problem is the following: "A salesman is required to visit once and only once each of n different cities starting from a base city, and returning to this city. What path minimizes the total distance travelled by the salesman?" The problem has been treated by a number of different people using a variety of techniques; cf. Dantzig, Fulkerson, Johnson, where a combination of ingenuity and linear programming is used, and Miller, Tucker and Zemlin, whose experiments using an all-integer program of Gomory did not produce results in cases with ten cities although some success was achieved in cases of simply four cities. The purpose of this note is to show that this problem can easily be formulated in dynamic programming terms, and resolved computationally for up to 17 cities. For larger numbers, the method presented below, combined with various simple manipulations, may be used to obtain quick approximate solutions. Results of this nature were independently obtained by M. Held and R. M. Karp, who are in the process of publishing some extensions and computational results.