Vendedor ambulante en scipy

¿Cómo resuelvo un problema de vendedor ambulante en python? No encontré ninguna biblioteca, debería haber una manera de usar las funciones scipy para la optimización u otras bibliotecas.

Mi solución de fuerza bruta hacky-extremelly-lazy-pythonic es:

tsp_solution = min( (sum( Dist[i] for i in izip(per, per[1:])), n, per) for n, per in enumerate(i for i in permutations(xrange(Dist.shape[0]), Dist.shape[0])) )[2] 

donde Dist (numpy.array) es la matriz de distancia. Si Dist es demasiado grande esto tomará para siempre.

Sugerencias?

Las funciones de scipy.optimize no están scipy.optimize para permitir una adaptación sencilla al problema del vendedor ambulante (TSP). Para una solución simple, recomiendo el algoritmo 2-opt, que es un algoritmo bien aceptado para resolver el TSP y relativamente sencillo de implementar. Aquí está mi implementación del algoritmo:

 import numpy as np # Calculate the euclidian distance in n-space of the route r traversing cities c, ending at the path start. path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))]) # Reverse the order of all elements from element i to element k in array r. two_opt_swap = lambda r,i,k: np.concatenate((r[0:i],r[k:-len(r)+i-1:-1],r[k+1:len(r)])) def two_opt(cities,improvement_threshold): # 2-opt Algorithm adapted from https://en.wikipedia.org/wiki/2-opt route = np.arange(cities.shape[0]) # Make an array of row numbers corresponding to cities. improvement_factor = 1 # Initialize the improvement factor. best_distance = path_distance(route,cities) # Calculate the distance of the initial path. while improvement_factor > improvement_threshold: # If the route is still improving, keep going! distance_to_beat = best_distance # Record the distance at the beginning of the loop. for swap_first in range(1,len(route)-2): # From each city except the first and last, for swap_last in range(swap_first+1,len(route)): # to each of the cities following, new_route = two_opt_swap(route,swap_first,swap_last) # try reversing the order of these cities new_distance = path_distance(new_route,cities) # and check the total distance with this modification. if new_distance < best_distance: # If the path distance is an improvement, route = new_route # make this the accepted best route best_distance = new_distance # and update the distance corresponding to this route. improvement_factor = 1 - best_distance/distance_to_beat # Calculate how much the route has improved. return route # When the route is no longer improving substantially, stop searching and return the route. 

Aquí hay un ejemplo de la función que se está utilizando:

 # Create a matrix of cities, with each row being a location in 2-space (function works in n-dimensions). cities = np.random.RandomState(42).rand(70,2) # Find a good route with 2-opt ("route" gives the order in which to travel to each city by row number.) route = two_opt(cities,0.001) 

Y aquí está la ruta de solución aproximada que se muestra en una gráfica:

 import matplotlib.pyplot as plt # Reorder the cities matrix by route order in a new matrix for plotting. new_cities_order = np.concatenate((np.array([cities[route[i]] for i in range(len(route))]),np.array([cities[0]]))) # Plot the cities. plt.scatter(cities[:,0],cities[:,1]) # Plot the path. plt.plot(new_cities_order[:,0],new_cities_order[:,1]) plt.show() # Print the route as row numbers and the total distance travelled by the path. print("Route: " + str(route) + "\n\nDistance: " + str(path_distance(route,cities))) 

Solución aproximada de problema de vendedor ambulante de 2 opciones

Si la velocidad del algoritmo es importante para usted, le recomiendo que calcule las distancias y las guarde en una matriz. Esto disminuye dramáticamente el tiempo de convergencia.

Edición: Puntos de inicio y finalización personalizados

Para una ruta no circular (una que termina en una ubicación diferente de donde comienza), edite la fórmula de distancia de ruta para

 path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p+1]]-c[r[p]]) for p in range(len(r)-1)]) 

y luego reordenar las ciudades para trazar usando

 new_cities_order = np.array([cities[route[i]] for i in range(len(route))]) 

Con el código tal como está, la ciudad inicial se fija como la primera ciudad en cities y la ciudad final es variable.

Para hacer que la ciudad final sea la última en cities , restrinja el rango de ciudades intercambiables cambiando el rango de swap_first y swap_last en two_opt() con el código

 for swap_first in range(1,len(route)-3): for swap_last in range(swap_first+1,len(route)-1): 

Para hacer que las ciudades de inicio y final sean variables, en su lugar, expanda el rango de swap_first y swap_last con

 for swap_first in range(0,len(route)-2): for swap_last in range(swap_first+1,len(route)):