First Mentions of TSP

Although the Traveling Salesman Problem (TSP) has become a really important problem in mathematical and computational research, it is not clear when was first stated and called in this way.

Here we mention some references to the TSP what could give us an idea of its origins:

In 1587 William Hamilton invented the “Icosian game”, that consists in a dodecahedron whose vertices had the name of well-known cities. The challenge is to determine a tour through all the cities, visiting each one only once. In fact, such paths through the vertices of a graph are named after him as hamiltonian circuits.

The publication of 1832 German Traveling Salesman handbook by Heiner Müller-Merbach. In its content we can find an explanation about the relevance of having good tours for a business, nothing mathematical however.

In 1930s at Princeton, Hassler Whitney was working in the “48 States Problem” and Merril Flood in school bus routing for the State of West Virginia, when it was introduced the name of Traveling Salesman Problem by Whitney in a seminar talk. And by the end of the 1940s TSP had gotten fame in Princeton and RAND Corporation, where Flood was working at.

About RAND Corporation:

“is a nonprofit institution that helps improve policy and decisionmaking through research and analysis.

RAND focuses on the issues that matter most such as health, education, national security, international affairs, law and business, the environment, and more. With a research staff consisting of some of the world’s preeminent minds, RAND has been expanding the boundaries of human knowledge for more than 60 years.”

In RAND Corporation, Julia Robinson was working too. And she published On the Hamiltonian game (a traveling salesman problem) in 1949. This is the first reference using the term TSP. Her approach used the integer programming and she formulated the problem as “the shortest route for a salesman starting from Washington, visiting all the state capitals and then returning to Washington”.

As from that date, many mathematicians started being interested in the TSP, its variations and its applications to solve a large amount of “real world” problems.

Applegate, D. L., Cook, W. J., Chvatal, V., & Bixby, R. E. (2011). The Traveling Salesman Problem : A Computational Study. Princeton University Press.

Chartrand, G. (1977). Introductory Graph Theory. Courier Dover Publications.

Jünger, M., Liebling, T. M., et. al. (2009) 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer.

http://www.rand.org/about/history.html consulted in November, 2013.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s