En 1962, podría ganar un premio de $ 10 000 (aproximadamente $ 80 000 en dinero de hoy) si encuentra la solución a un problema de vendedor ambulante euclidiano definido en 33 ciudades.
http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html
Mirando la imagen, el problema parece bastante fácil. Sin embargo, no pude encontrar recursos más detallados sobre el problema.
¿Alguien sabe más detalles, como las distancias exactas y una solución óptima?
optimization
traveling-salesman
Martin Drozdik
fuente
fuente
Respuestas:
Los detalles completos se encuentran en Robert L. Karg y James L. Thompson, Un enfoque heurístico para resolver problemas de vendedores ambulantes ( Management Science , 10 (2): 225–248, 1964). El PDF está disponible en JStor e Informs.org (ambos pagos). Este es el papel que produjo el recorrido óptimo de 10,861 millas. También incluye la tabla de distancia completa, pero no la reproduciré aquí, ya que es demasiado escribir.
La solución también se ilustra en la página 15 de The Travelling Salesman Problem de David L. Applegate, Robert E. Bixby, Vasek Chvátal y William J. Cook (Princeton University Press, 2007). La introducción a ese libro, que incluye la página relevante, está disponible gratuitamente en el editor .
fuente