查看: 191|回复: 0

旅行商问题（TSP）：数模优化题里"最简单的难题"

字体大小: 正常放大

1198 主题	4 听众	2978 积分

该用户从未签到

电梯直达

1^#

发表于 2026-8-23 17:33 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

from itertools import permutations
( ]/ I$ A* D: Z6 J
import math\" f2 Y' J# ^/ @5 H. u- V4 j$ I( {
# f, ^+ }+ [. F1 L: j
def tsp_brute(dist):
6 f0 r9 b% K7 ^2 k$ |
"""dist: n×n 距离矩阵，返回 (最短长度, 最优回路)"""
' g5 `8 Z+ ]- k8 H4 h: H$ S; s, T
n = len(dist)
5 B1 O% Y: p: K9 `\" c2 a5 W. h) T
best_len, best_tour = math.inf, None& h6 n8 y; M. H: `3 e& T
for perm in permutations(range(1, n)): # 固定起点 0# P: W( ^7 j2 m- ?\" p% Z0 {
tour = [0] + list(perm)4 M( n5 D. g# i/ {2 I
L = sum(dist[tour[i]][tour[i+1]] for i in range(n-1)) + dist[tour[-1]][0]
# L: B& y\" t1 p( {5 d! O/ p- T( a
if L < best_len:* D; @5 a; V8 W, A( M
best_len, best_tour = L, tour7 e4 R# n8 t6 G) @1 C\" c
return best_len, best_tour6 K\" V' y7 s( J3 u
6 k5 Y7 C: {( U# _% J! E. y7 V
# ---------- 2-opt 局部搜索（中大规模） ----------: v+ H7 i/ H: c
def tsp_2opt(dist, max_iter=1000):- Q\" ~2 w; M5 v f* @7 |, @3 f& a' {
n = len(dist) N5 Y ]5 d) T3 [ R, J$ f- G: p- r
tour = list(range(n)) # 初始：自然顺序
6 C: C3 |( U( a# a
improved = True
- b; v2 b6 O: s
while improved and max_iter > 0:' P9 q, ~\" |2 {- X( j* }1 O& `4 V6 X; d
improved = False
4 k8 M4 b- _& {1 N4 ?2 c\" B4 S2 Z0 l
for i in range(1, n-2):
5 q8 M2 A\" m% S! u2 F, c9 ?8 J7 ^
for k in range(i+1, n):
7 V* P& S% b4 x- n2 c [
# 翻转 tour[i:k+1]
3 v* j4 Z9 W( \
new_tour = tour[:i] + tour[i:k+1][::-1] + tour[k+1:]
# n( `4 q. q- n& H% [0 n% {
cur = sum(dist[tour[j]][tour[j+1]] for j in range(n-1)) + dist[tour[-1]][tour[0]], ~, `& I( I$ S6 g& Q) O& V
new = sum(dist[new_tour[j]][new_tour[j+1]] for j in range(n-1)) + dist[new_tour[-1]][new_tour[0]]% O( S0 {! ?' ~% o4 M+ s3 G
if new < cur:
& L7 ^1 _ v# S) ~: j# ~+ \( s8 K
tour, improved = new_tour, True
$ p* i3 R h- ^% z: O& D
max_iter -= 1; f\" f/ L! g; W4 E2 ]
L = sum(dist[tour[j]][tour[j+1]] for j in range(n-1)) + dist[tour[-1]][tour[0]]* m\" e8 O\" u! y- o5 N5 ]
return L, tour
& G' O8 _; s. D
# h. D: Z\" C. a1 i7 o% y% i8 a
# ---------- 测试：4 城市 ----------9 y9 N& i2 y' B$ K6 Q, ?
dist = [
! {) W- F9 i: P) W
[0, 10, 15, 20],# ]( d: j( h4 [& f4 j
[10, 0, 35, 25],
3 r5 l& A5 m2 d- P2 E\" ~+ R
[15, 35, 0, 30],
* k) l; N9 A( j$ ^% u9 q
[20, 25, 30, 0]
7 G# e6 e U1 h6 p1 S
]
- T2 d* K4 y) I3 D; z: Z
print("暴力 DFS:", tsp_brute(dist)) # 最短长度 80，回路 0→1→3→2→0
2 H& V1 b( O9 Y/ c
print("2-opt :", tsp_2opt(dist))

复制代码

7.2 运行结果

暴力 DFS: (80, [0, 1, 3, 2]). r+ `$ l* ?5 E) n9 d\" [. E
2-opt : (95, [0, 1, 2, 3])

复制代码

观察：暴力 DFS 保证全局最优（时可行）。2-opt 从自然顺序出发卡在局部最优 95，未能到达最优解 80——这正是 2-opt 的经典陷阱：单次运行可能陷入局部最优。竞赛中应多次随机重启或结合其他启发式（如先用最近邻初始化再 2-opt）。这也是为什么论文里必须报告"与精确解的 gap"，而不是只报一个数字。

8. 竞赛真题映射

年份

CUMCM 题目方向

TSP 变体

1998B灾情巡视路线巡检 TSP（带时间窗 / 部分覆盖）
2001C公交车线路设计路径规划 + 容量约束（VRP 变体）
2008B啤酒运输问题配送路径优化
2011A高速公路收费站路网遍历 + 费用优化
2015A太阳能小屋设备布点 + 巡检路径
2017B煤炭产量预测无关（数据题）
2020A炉温曲线无关（拟合题）
近年物流配送 / 应急巡检 / 传感器网络TSP / VRP / 覆盖路径

核心规律：只要赛题出现"一条路走遍多个地点"，TSP 或其变体（VRP、TSP with Time Windows、多车 TSP）就是最自然的建模原型。先用 TSP 建原型，再根据约束升级为 VRP，是数模竞赛的成熟套路。

9. 常见误区与赛场自查

#

误区

正解

1"TSP 可以用贪心算法精确求解"贪心（最近邻）不保证最优，存在反例
2"2-opt 一定得到全局最优"2-opt 是局部搜索，可能陷入局部最优
3"TSP 和指派问题等价"TSP 要求单一回路，指派问题允许子回路
4"子回路消除约束可以一次性写完"数量  级别，实际用逐步加入（lazy constraint）
5"DP 复杂度 "准确是，每状态需  转移
6"所有 TSP 都有常数近似比"仅度量 TSP（三角不等式）有 Christofides  近似
7"对称 TSP 和非对称 TSP 一样"对称：种回路；非对称：种

赛场自查清单：

我确认了距离矩阵是否对称、是否满足三角不等式（影响算法选择）。
我估计了可行解数量，判断暴力 / B&B / 启发式的适用性。
若用 B&B：下界函数是否安全（不高于最优值）且紧？
若用 2-opt：是否报告了与精确解的偏差（小规模对比）？
若用 Christofides：是否验证了三角不等式成立？
论文中是否报告了运行时间与最优性差距（gap）？
是否对结果做了敏感性分析（距离矩阵微调时回路是否稳定）？
是否给出了子回路消除的处理方式（lazy constraint 或逐步加入）？
8 }" V7 r* D$ M( C1 L/ W

10. 参考文献

[1] Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a Large-Scale Traveling-Salesman Problem. Operations Research, 2(4), 393–410. DOI: 10.1287/opre.2.4.393. https://doi.org/10.1287/opre.2.4.393

[2] Held, M., & Karp, R. M. (1961). A dynamic programming approach to sequencing problems. Proceedings of the 1961 16th ACM National Meeting, pp. 71.201–71.204. DOI: 10.1145/800029.808532. https://doi.org/10.1145/800029.808532

[3] Held, M., & Karp, R. M. (1962). The traveling-salesman problem and minimum spanning trees: Part II. Operations Research, 18(6), 1138–1162. DOI: 10.1287/opre.18.6.1138.

[4] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (Eds.) (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics, Vol. 12. Chichester: John Wiley & Sons. ISBN 978-0-471-90413-7.

[5] Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2011). The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. ISBN 978-0-691-12993-8 (print), 978-1-400-84110-3 (ebook). https://press.princeton.edu/books/ebook/9781400841103/the-traveling-salesman-problem-pdf

[6] Cook, W. (2012). In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton, NJ: Princeton University Press. ISBN 978-0-691-16352-9.

[7] 姜启源, 谢金星, 叶俊. 数学模型. 5版. 北京: 高等教育出版社, 2018. ISBN 978-7-04-049222-4.

[8] 司守奎, 孙玺菁. 数学建模算法与应用. 3版. 北京: 国防工业出版社, 2021. ISBN 978-7-118-12278-7.

[9] 胡运权, 主编. 运筹学教程. 5版. 北京: 清华大学出版社, 2018. ISBN 978-7-302-48125-6. https://www.tup.tsinghua.edu.cn/wap/tsxqy.aspx?id=07656604

给参赛学生的一句话：TSP 是数模优化题里"最简单的难题"——问题描述一句话，求解却需要一整套组合优化工具箱。小规模用 B&B/DP 保证最优，大规模用 2-opt 给出好解并报告 gap，这是评委最认可的"务实"策略。记住：能证明最优的解，比看似漂亮但无保证的解更有说服力。