Ejemplo de vendedor ambulante con óptimo global conocido

Question

Hice un algoritmo memético en Python para Problema de vendedor ambulante. Sin embargo, todos los datos de prueba (lista de distancias entre ciudades) que he encontrado carecen de la información de la mejor solución, por lo que no puedo saber qué tan cerca de Global Optimum Mi algoritmo está.

¿Alguien sabe dónde puedo encontrar algunos datos de prueba de TSP (preferiblemente en forma de matriz, pero cualquier cosa es buena) con la mejor solución conocida?

Answer 1

¿Google?

http://www.tsp.gatech.edu/data/index.html

Esa página proporciona varios casos de prueba de los cuales 16 tienen una solución óptima.

Answer 2

¿Quizás pueda generar sus propios datos de prueba?

Esto definitivamente no serán pruebas integrales, pero podría ayudar. Nota: El siguiente es sobre el camino hamiltoniano, y si está buscando ciclos, algo similar funcionará.

Puedes hacer lo siguiente:

Digamos que se le da un gráfico G no dirigido con N nodos.

Ahora crea un gráfico ponderado G ', estableciendo el peso de los bordes en g para ser 1, y agregando los bordes no en g, y dándoles un peso aleatorio> 1, es decir, g' es un gráfico completo con pesos asignados a todos sus bordes.

Ahora, si ejecuta un algoritmo TSP válido en G 'y genera una ruta de tamaño N-1, entonces G tiene una ruta hamiltoniana. De lo contrario, G no tiene un camino hamiltoniano.

Entonces ahora puedes usar gráficos saber que tienen/no tienen caminos hamiltonianos (por ejemplo: Hipercubo Tiene rutas hamiltonianas) y genere datos de prueba para su algoritmo TSP.

Esta página tiene algunas condiciones suficientes que podrían resultar útiles para generar gráficos que tienen rutas hamiltonianas: http://www-math.cudenver.edu/~wicerowi/courses/m4408/gtln12.html

Supongo que no tendrá dificultades para encontrar datos sobre gráficos con/sin rutas hamiltonianas.

Espero eso ayude. ¡Buena suerte!

Answer 3

TSPLIB es una biblioteca de instancias de muestra para TSP (y problemas relacionados) de varias fuentes y de varios tipos.

http://comopt.ifi.uni-heidelberg.de/software/tsplib95/