多起点旅行商问题（All Source TSP）精确求解方法咨询

数据老陈

2026-6-17

问题：多起点TSP精确解的高效实现方式

我有一个小规模的旅行商问题（TSP），其精确解可通过如下方式轻松计算。我希望实现“多起点”TSP路径输出，无需固定起始节点，可从任意节点出发，想获取每个顶点对应的所有最优路径。请问除了每次重新标记顶点并生成多个距离矩阵这种繁琐方法外，还有什么可行方案？

注：我只需要精确解，不需要近似解。

import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming

distance_matrix = np.array([
    [0,437,23,21,41,300,142,187,81,171,98],
    [545,0,10,19,54,339,142,201,78,170,143],
    [95,147,0,186,273,93,29,55,731,76,164],
    [45,60,930,0,518,28,10,13,298,31,71],
    [74,111,495,490,0,62,25,21,407,87,143],
    [122,126,2,1,13,0,2057,241,17,45,26],
    [328,313,5,20,34,527,0,560,70,107,76],
    [208,200,5,9,24,442,159,0,41,61,41],
    [122,174,53,44,110,98,25,40,0,878,798],
    [214,340,12,37,66,162,54,96,199,0,789],
    [265,423,12,27,90,173,73,86,312,701,0]])

distance_matrix = distance_matrix * -1
solve_tsp_dynamic_programming(distance_matrix)
# 输出结果：([0, 5, 6, 7, 4, 3, 2, 8, 9, 10, 1], np.int64(-7727))

解决方案

TSP的最优解本质是一条哈密顿回路，只需计算一次固定起点的最优回路，再通过循环移位即可得到所有节点作为起点的最优路径，无需重复执行动态规划计算。具体步骤如下：

计算一次固定起点的最优回路
先以任意节点（比如节点0）为起点，求解TSP的最优路径，再将路径补全为闭合回路（即回到起点）。
循环移位生成多起点路径
对闭合回路进行循环移位，每个节点对应的移位结果就是以该节点为起点的最优路径。此外，原路径的逆序也是一条最优路径（因为TSP回路是双向的）。

代码实现

import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming

# 原始距离矩阵
distance_matrix = np.array([
    [0,437,23,21,41,300,142,187,81,171,98],
    [545,0,10,19,54,339,142,201,78,170,143],
    [95,147,0,186,273,93,29,55,731,76,164],
    [45,60,930,0,518,28,10,13,298,31,71],
    [74,111,495,490,0,62,25,21,407,87,143],
    [122,126,2,1,13,0,2057,241,17,45,26],
    [328,313,5,20,34,527,0,560,70,107,76],
    [208,200,5,9,24,442,159,0,41,61,41],
    [122,174,53,44,110,98,25,40,0,878,798],
    [214,340,12,37,66,162,54,96,199,0,789],
    [265,423,12,27,90,173,73,86,312,701,0]])

# 转为负矩阵适配最大化求解逻辑，对应最小化实际距离
neg_distance_matrix = distance_matrix * -1
path, total_neg_dist = solve_tsp_dynamic_programming(neg_distance_matrix)
total_dist = -total_neg_dist

# 补全为闭合回路
closed_path = path + [path[0]]

# 生成每个节点对应的最优路径
all_optimal_paths = {}
for idx, node in enumerate(closed_path[:-1]):
    # 循环移位得到正向路径
    shifted_path = closed_path[idx:-1] + closed_path[:idx]
    all_optimal_paths[node] = {
        "forward_path": shifted_path,
        "reverse_path": shifted_path[::-1],
        "total_distance": total_dist
    }

# 打印结果
for node, info in all_optimal_paths.items():
    print(f"以节点{node}为起点的最优路径：")
    print(f"正向路径: {info['forward_path']}")
    print(f"反向路径: {info['reverse_path']}")
    print(f"总距离: {info['total_distance']}\n")

原理说明
TSP的最优解是一个闭合回路，所有循环移位后的路径本质是同一个回路的不同起始形式，总距离完全一致，均为最优值。这种方法仅需一次动态规划计算，效率远高于多次重新计算的方式。

内容的提问来源于stack exchange，提问作者Gopala