scipy 中的旅行推销员 [英] Travelling Salesman in scipy

问题描述

如何在 python 中解决旅行商问题?我没有找到任何库，应该有使用scipy函数进行优化或其他库的方法.

How do I solve a Travelling Salesman problem in python? I did not find any library, there should be a way using scipy functions for optimization or other libraries.

我的 hacky-extremelly-lazy-pythonic 暴力破解解决方案是:

My hacky-extremelly-lazy-pythonic bruteforcing solution is:

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]

其中 Dist (numpy.array) 是距离矩阵.如果 Dist 太大，这将花费很长时间.

where Dist (numpy.array) is the distance matrix. If Dist is too big this will take forever.

建议?

推荐答案

scipy.optimize 函数的构造不能直接适应旅行商问题 (TSP).对于一个简单的解决方案，我推荐 2-opt 算法，这是一种被广泛接受的解决 TSP 的算法，并且实现起来相对简单.这是我对算法的实现:

The scipy.optimize functions are not constructed to allow straightforward adaptation to the traveling salesman problem (TSP). For a simple solution, I recommend the 2-opt algorithm, which is a well-accepted algorithm for solving the TSP and relatively straightforward to implement. Here is my implementation of the algorithm:

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.

这是一个正在使用的函数的例子:

Here is an example of the function being used:

# 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)

这是图上显示的近似解法路径:

And here is the approximated solution path shown on a plot:

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) + "

Distance: " + str(path_distance(route,cities)))

如果算法的速度对您很重要，我建议您预先计算距离并将它们存储在矩阵中.这大大减少了收敛时间.

If the speed of algorithm is important to you, I recommend pre-calculating the distances and storing them in a matrix. This dramatically decreases the convergence time.

自定义起点和终点

对于非圆形路径(结束位置与开始位置不同的路径)，将路径距离公式编辑为

For a non-circular path (one which ends at a location different from where it starts), edit the path distance formula to

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

然后重新排序城市以使用

and then reorder the cities for plotting using

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

照原样，起始城市固定为cities中的第一个城市，结束城市是可变的.

With the code as it is, the starting city is fixed as the first city in cities, and the ending city is variable.

为了使结束城市成为cities中的最后一个城市，通过改变swap_first和swap_last的范围来限制可交换城市的范围two_opt() 与代码

To make the ending city the last city in cities, restrict the range of swappable cities by changing the range of swap_first and swap_last in two_opt() with the code

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

为了使起始城市和结束城市都可变，而是用

To make both the starting and ending cities variable, instead expand the range of swap_first and swap_last with

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

这篇关于scipy 中的旅行推销员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！