Qual é a solução ideal para o Concurso TSP de 1962 da Procter and Gamble?

13

Em 1962, você poderia ganhar um prêmio de US $ 10.000 (cerca de US $ 80.000 em dinheiro de hoje) se encontrasse a solução para um problema de vendedor ambulante euclidiano definido em 33 cidades.

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

Olhando para a foto, o problema parece bastante fácil. No entanto, não consegui encontrar recursos mais detalhados sobre o problema.

Alguém conhece mais alguns detalhes, como as distâncias exatas e uma solução ideal?

optimization traveling-salesman Martin Drozdik
fonte
2
Ah, a década de 1960 ... quando ninguém pisou nas pálpebras de empresas que anunciam seus produtos, mostrando policiais assediando mulheres com pouca roupa.
David Richerby

Respostas:

16

Os detalhes completos estão em Robert L. Karg e James L. Thompson, Uma Abordagem Heurística para a Solução de Problemas do Vendedor Viajante ( Management Science , 10 (2): 225–248, 1964). O PDF está disponível no JStor e Informs.org (ambos paywalled). Este é o documento que produziu o passeio ideal de 10.861 milhas. Também inclui a tabela de distância total, mas não a reproduzirei aqui, pois é muita digitação.

A solução também é ilustrada na página 15 de O Problema do Vendedor Viajante, de David L. Applegate, Robert E. Bixby, Vasek Chvátal e William J. Cook (Princeton University Press, 2007). A introdução desse livro, que inclui a página relevante, está disponível gratuitamente no editor .

David Richerby
fonte
"É claro que uma abordagem mais direta seria simplesmente considerar todos os roteiros possíveis, mas esse número cresce tão rapidamente que verificar todos eles em busca de uma instância de tamanho modesto, digamos 50 cidades, está muito além das capacidades dos supercomputadores mais rápidos de hoje . " (de Applegate vinculado, et al.) #
2926 Jacob Krall