scipy 中的旅行推销员

Question

如何用Python解决旅行商问题？我没有找到任何库，应该有一种使用 scipy 函数进行优化或其他库的方法。

我的hacky-extremelly-lazy-pythonic bruteforcing解决方案是：

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 太大，这将花费很长时间。

建议？

Answer 1

scipy.optimize

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

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.

以下是正在使用的函数的示例：

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

这是绘图上显示的近似解路径：

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

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

编辑：自定义起点和终点

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

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

然后使用

重新排序城市以进行绘图

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

原代码中，起始城市固定为

cities

中的第一个城市，结束城市是可变的。

要使结束城市成为

cities

中的最后一个城市，请通过使用代码

更改

swap_first

中

swap_last

和

two_opt()

的范围来限制可交换城市的范围

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

要使起始城市和结束城市都可变，请使用

 扩大 

swap_first

 和 

swap_last

的范围

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

Answer 2

我最近发现这个选项可以使用线性优化来解决 TSP 问题

https://gist.github.com/mirrornerror/a684b4d439edbd7117db66a56f2483e0

尽管如此，我同意其他一些评论，只是剩下一点，那就是有办法使用线性优化来解决这个问题。

一些学术出版物包括以下内容 http://www.opl.ufc.br/post/tsp/ https://phabi.ch/2021/09/19/tsp-subtour-elimination-by-miller-tucker-zemlin-constraint/

Answer 3

在NetworkX - 用于网络问题的python包的文档（参考/算法/近似和启发式）中，您可以找到一个示例

"""
==========================
Traveling Salesman Problem
==========================

This is an example of a drawing solution of the traveling salesman problem

The function used to produce the solution is `christofides <networkx.algorithms.approximation.traveling_salesman.christofides>`,
where given a set of nodes, it calculates the route of the nodes
that the traveler has to follow in order to minimize the total cost.
"""

import matplotlib.pyplot as plt
import networkx as nx
import networkx.algorithms.approximation as nx_app
import math

G = nx.random_geometric_graph(20, radius=0.4, seed=3)
pos = nx.get_node_attributes(G, "pos")

# Depot should be at (0,0)
pos[0] = (0.5, 0.5)

H = G.copy()


# Calculating the distances between the nodes as edge's weight.
for i in range(len(pos)):
    for j in range(i + 1, len(pos)):
        dist = math.hypot(pos[i][0] - pos[j][0], pos[i][1] - pos[j][1])
        dist = dist
        G.add_edge(i, j, weight=dist)

cycle = nx_app.christofides(G, weight="weight")
edge_list = list(nx.utils.pairwise(cycle))

# Draw closest edges on each node only
nx.draw_networkx_edges(H, pos, edge_color="blue", width=0.5)

# Draw the route
nx.draw_networkx(
    G,
    pos,
    with_labels=True,
    edgelist=edge_list,
    node_color = 'r',
    edge_color="red",
    node_size=200,
    width=3,
)

print("The route of the traveller is:", cycle)
plt.show()