13
$\begingroup$

In 1962, you could win a prize of \$ 10 000 (about \$ 80 000 in today's money) if you found the solution to an Euclidean travelling salesman problem defined on 33 cities.

http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html

Looking at the picture, the problem seems pretty easy. However I failed to find more detailed resources on the problem.

Does anybody know some more details, such as the exact distances and an optimal solution?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Ah, the 1960s... when nobody batted an eyelid at companies advertising their products by showing policemen harassing scantily-clad women. $\endgroup$
    – David Richerby
    Commented Mar 18, 2015 at 11:21

1 Answer 1

Reset to default
17
$\begingroup$

Full details are in Robert L. Karg and James L. Thompson, A Heuristic Approach to Solving Traveling Salesman Problems (Management Science, 10(2):225–248, 1964). The PDF is available from JStor and Informs.org (both paywalled). This is the paper that produced the optimal tour of 10,861 miles. It also includes the full distance table but I'll not reproduce that here as it's way too much typing.

The solution is also illustrated on page 15 of The Traveling Salesman Problem by David L. Applegate, Robert E. Bixby, Vasek Chvátal and William J. Cook (Princeton University Press, 2007). The introduction to that book, which includes the relevant page, is freely available from the publisher.

Improve this answer
$\endgroup$
1
  • $\begingroup$ "A more direct approach would of course be to simply consider all possible tours, but this number grows so quickly that checking all of them for a modest-size instance, say 50 cities, is well beyond the capabilities of even the fastest of today’s supercomputers." (from linked Applegate, et al.) $\endgroup$
    – Jacob Krall
    Commented Mar 18, 2015 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.