如何在Python中解决旅行商问题？我没有找到任何库，但可以使用scipy函数进行优化或其他库来解决问题。
我的草率、极其懒惰的Python蛮力破解方案是：
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太大，这将需要很长时间。
有什么建议吗？
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)])
然后使用xx重新排列城市以进行绘图
new_cities_order = np.array([cities[route[i]] for i in range(len(route))])
代码中，起始城市被固定为cities中的第一个城市，而结束城市是可变的。
为了使结束城市成为cities中的最后一个城市，在two_opt()函数中改变swap_first和swap_last的范围限制交换城市的范围即可：
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)):
path_distance函数，但我不确定2-opt在非对称情况下是否有效 :? - jjmontes我最近发现了使用线性优化解决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/
"""
==========================
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()