En 1962, vous pourriez gagner un prix de 10 000 $ (environ 80 000 $ en argent d'aujourd'hui) si vous trouviez la solution à un problème de vendeur ambulant euclidien défini dans 33 villes.
http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html
En regardant l'image, le problème semble assez facile. Cependant, je n'ai pas réussi à trouver des ressources plus détaillées sur le problème.
Quelqu'un connaît-il plus de détails, tels que les distances exactes et une solution optimale?
optimization
traveling-salesman
Martin Drozdik
la source
la source
Réponses:
Les détails complets se trouvent dans Robert L. Karg et James L. Thompson, A Heuristic Approach to Solving Travelling Salesman Problems ( Management Science , 10 (2): 225–248, 1964). Le PDF est disponible auprès de JStor et Informs.org (tous deux paywallés). C'est le journal qui a produit le tour optimal de 10 861 milles. Il comprend également le tableau des distances complètes, mais je ne le reproduirai pas ici car c'est beaucoup trop de frappe.
La solution est également illustrée à la page 15 de The Traveling Salesman Problem de David L. Applegate, Robert E. Bixby, Vasek Chvátal et William J. Cook (Princeton University Press, 2007). L'introduction à ce livre, qui comprend la page pertinente, est disponible gratuitement auprès de l'éditeur .
la source