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

2744557306

# J' I  O- }. b2 Z( J6 B
1 z# h# ~, r- g6 c; j7 g9 S

1. from itertools import permutations
   6 b. Y# D0 j3 A0 T, j) u
2. import math1 X  Q  N1 t( F1 u
   
3. 
   7 z5 ?$ {( `& U' g! ~* _+ w
4. def tsp_brute(dist):
   2 J; g: R. W) _9 s8 V) g
5.     """dist: n×n 距离矩阵，返回 (最短长度, 最优回路)"""
   ) A  L8 X/ y; T4 B3 T
6.     n = len(dist)
   7 H3 }$ f* c( @2 j- P\" A
7.     best_len, best_tour = math.inf, None$ {/ C6 c8 z; q2 b; ~0 V
   
8.     for perm in permutations(range(1, n)):          # 固定起点 0
   ' m1 L3 }8 S7 A% J& b  E+ g
9.         tour = [0] + list(perm)+ F* M# D) d\" `& g7 ], L. m0 f
   
10.         L = sum(dist[tour[i]][tour[i+1]] for i in range(n-1)) + dist[tour[-1]][0]
    0 S$ x( M: |8 C0 r
11.         if L < best_len:
    ! z% L1 G1 |/ c' N; M0 |/ y1 s
12.             best_len, best_tour = L, tour& w& ?2 t6 a7 @$ ~2 R5 n
    
13.     return best_len, best_tour1 X' }$ N) \$ H4 u4 m
    
14. 
    3 _! S% A- a; j+ _3 Z) K\" h6 P' s; w+ ?
15. # ---------- 2-opt 局部搜索（中大规模） ----------* K! h* y+ x9 D9 U7 i
    
16. def tsp_2opt(dist, max_iter=1000):2 k: ?$ F4 E  k, o/ `7 W
    
17.     n = len(dist); w: L( m% G+ |) D+ G3 x
    
18.     tour = list(range(n))                          # 初始：自然顺序
    $ v* E! T5 |; j5 X/ ?
19.     improved = True
    ( q/ p7 e2 h3 V9 y
20.     while improved and max_iter > 0:
    % z0 B% ?* v5 b# J/ `* Y
21.         improved = False  t1 v\" B! _/ e6 V9 S) d
    
22.         for i in range(1, n-2):$ ~2 x$ |2 t4 ]2 P
    
23.             for k in range(i+1, n):
    8 w, G: u0 o$ D3 E! W% t( `2 x' r
24.                 # 翻转 tour[i:k+1]0 ~% H3 N* S* g
    
25.                 new_tour = tour[:i] + tour[i:k+1][::-1] + tour[k+1:]
    ' W8 ]3 @6 `4 X  X7 ^. ~
26.                 cur = sum(dist[tour[j]][tour[j+1]] for j in range(n-1)) + dist[tour[-1]][tour[0]]
    9 X, |  e+ r% {
27.                 new = sum(dist[new_tour[j]][new_tour[j+1]] for j in range(n-1)) + dist[new_tour[-1]][new_tour[0]]% K5 g% S% t% D/ m# X+ T: a% U
    
28.                 if new < cur:4 _* m2 h6 k+ |: v\" [, }
    
29.                     tour, improved = new_tour, True1 [\" M- G; ?! J, h$ D
    
30.                     max_iter -= 1
    2 _2 r$ @; Y% A3 Z, Y! j
31.     L = sum(dist[tour[j]][tour[j+1]] for j in range(n-1)) + dist[tour[-1]][tour[0]]
    , F( l( L+ d2 K  [
32.     return L, tour- I3 s3 R6 @4 G: z7 m  j1 q
    
33. 7 a/ E7 h- `+ K: P
    
34. # ---------- 测试：4 城市 ----------\" Y4 E# j; o  S+ m2 Z2 O
    
35. dist = [
      |  q+ i5 U, c
36.     [0, 10, 15, 20],+ @: `! w3 k0 }
    
37.     [10, 0, 35, 25],
    3 l% \* n0 c, R' K; d' G\" Y5 v
38.     [15, 35, 0, 30],
    - j1 @( g4 ^* x7 C- S: S
39.     [20, 25, 30, 0]
    / U( _' c2 u8 i9 V( [# _4 [1 z% K
40. ]
    / K! R; O2 X. D9 Q. C4 R
41. print("暴力 DFS:", tsp_brute(dist))   # 最短长度 80，回路 0→1→3→2→0
    ' ^. ?- w1 c2 @: z1 f
42. print("2-opt   :", tsp_2opt(dist))

复制代码

7.2 运行结果

1. 暴力 DFS: (80, [0, 1, 3, 2])3 ?! k6 V, H. @9 K2 M8 n
   
2. 2-opt   : (95, [0, 1, 2, 3])

复制代码

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

---

8. 竞赛真题映射

年份

CUMCM 题目方向

TSP 变体

8 v5 ]4 r  C2 Z  O. Y0 ~7 q& y1998B灾情巡视路线巡检 TSP（带时间窗 / 部分覆盖）
2001C公交车线路设计路径规划 + 容量约束（VRP 变体）
2008B啤酒运输问题配送路径优化
+ L, e1 G# x. H# Z2 r. q2011A高速公路收费站路网遍历 + 费用优化
" Z+ o7 x4 _8 N) c$ ]2015A太阳能小屋设备布点 + 巡检路径
" f+ d9 i+ D& v( V0 p) l2 b( c2017B煤炭产量预测无关（数据题）
2020A炉温曲线无关（拟合题）
近年物流配送 / 应急巡检 / 传感器网络TSP / VRP / 覆盖路径

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

---

9. 常见误区与赛场自查

#

误区

正解

6 b5 k8 v0 z2 t0 l1"TSP 可以用贪心算法精确求解"贪心（最近邻）不保证最优，存在反例
+ u" O" c; Z1 b: p2"2-opt 一定得到全局最优"2-opt 是局部搜索，可能陷入局部最优
% @8 s6 U& C, Q$ W5 D3"TSP 和指派问题等价"TSP 要求单一回路，指派问题允许子回路
. V; l. \, q7 C0 \$ ~7 K4"子回路消除约束可以一次性写完"数量  级别，实际用逐步加入（lazy constraint）
5"DP 复杂度 "准确是 ，每状态需  转移
5 p# e  z( G2 w2 L: V6"所有 TSP 都有常数近似比"仅度量 TSP（三角不等式）有 Christofides  近似
7"对称 TSP 和非对称 TSP 一样"对称： 种回路；非对称： 种

赛场自查清单：

• 我确认了距离矩阵是否对称、是否满足三角不等式（影响算法选择）。
• 我估计了可行解数量 ，判断暴力 / B&B / 启发式的适用性。
• 若用 B&B：下界函数是否安全（不高于最优值）且紧？
• 若用 2-opt：是否报告了与精确解的偏差（小规模对比）？
• 若用 Christofides：是否验证了三角不等式成立？
• 论文中是否报告了运行时间与最优性差距（gap）？
• 是否对结果做了敏感性分析（距离矩阵微调时回路是否稳定）？
• 是否给出了子回路消除的处理方式（lazy constraint 或逐步加入）？
  % N# ^( |, U! n+ E$ }/ C* 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，这是评委最认可的"务实"策略。记住：能证明最优的解，比看似漂亮但无保证的解更有说服力。