The Traveling-Salesman Problem

Merrill M. Flood
Additional contact information
Merrill M. Flood: Columbia University, New York, New York

Operations Research, 1956, vol. 4, issue 1, 61-75

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 \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$$a_{1i_2} + a_{i_2i_3} + a_{i_3i_4} + \cdots + a_{i_n1},$$\end{document} where the a (alpha)(beta) 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.

Date: 1956
References: Add references at CitEc
Citations: View citations in EconPapers (39)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.4.1.61 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:4:y:1956:i:1:p:61-75

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().