Apa solusi optimal dari Kontes TSP 1962 Procter and Gamble?

13

Pada tahun 1962, Anda bisa memenangkan hadiah $ 10.000 (sekitar $ 80.000 dalam bentuk uang hari ini) jika Anda menemukan solusi untuk masalah salesman keliling Euclidean yang ditentukan di 33 kota.

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

Melihat gambarnya, masalahnya sepertinya cukup mudah. Namun saya gagal menemukan sumber daya yang lebih rinci tentang masalah ini.

Adakah yang tahu lebih banyak detail, seperti jarak yang tepat dan solusi optimal?

optimization traveling-salesman Martin Drozdik
sumber
2
Ah, tahun 1960-an ... ketika tidak ada orang yang menatap perusahaan yang mengiklankan produk mereka dengan menunjukkan polisi melecehkan wanita berpakaian minim.
David Richerby

Jawaban:

16

Rincian lengkap ada di Robert L. Karg dan James L. Thompson, Pendekatan Heuristik untuk Memecahkan Masalah Salesman Perjalanan ( Ilmu Manajemen , 10 (2): 225–248, 1964). PDF tersedia dari JStor dan Informs.org (keduanya paywalled). Ini adalah karya yang menghasilkan tur optimal 10.861 mil. Ini juga termasuk tabel jarak penuh tapi saya tidak akan mereproduksi di sini karena terlalu banyak mengetik.

Solusi ini juga diilustrasikan pada halaman 15 dari The Traveling Salesman Problem oleh David L. Applegate, Robert E. Bixby, Vasek Chvátal dan William J. Cook (Princeton University Press, 2007). Pengantar buku itu, yang mencakup halaman yang relevan, tersedia secara bebas dari penerbit .

David Richerby
sumber
"Pendekatan yang lebih langsung tentu saja dengan hanya mempertimbangkan semua tur yang mungkin, tetapi jumlah ini tumbuh begitu cepat sehingga memeriksa semuanya untuk contoh ukuran sedang, katakanlah 50 kota, jauh melampaui kemampuan bahkan superkomputer tercepat saat ini. . " (dari tertaut Applegate, dkk.)
Jacob Krall