一、旅行商问题（TSP）与路径优化
做激光切割这些年，我碰到最多的问题就是：「明明同样的零件，为什么有的师傅切得快，有的切得慢？」
其实说白了，差距往往不在激光器本身，而在切割路径上。今天我们就来聊聊这个核心问题——旅行商问题（TSP）。
1.1 TSP问题定义
旅行商问题，英文叫 Traveling Salesman Problem，简称 TSP。它描述的场景很简单：
一个销售员要拜访 n 个城市，每个城市只去一次，最后回到出发城市。问：怎么走，总路程最短？
嗯，你想想看，这不就是我们激光切割时面临的问题吗？
切割头要从起点出发，依次经过所有切割轮廓，最后回到原点。每个轮廓就是一个「城市」，切割头就是那个「销售员」。
数学定义：
给定 n 个城市和两两之间的距离矩阵 D = [dij]，寻找一条经过所有城市恰好一次并返回起点的回路，使得总距离最小。
用公式表达：min Σ dπ(i)π(i+1) + dπ(n)π(1)
其中 π 是城市的一个排列。
这里有个关键点：TSP 是 NP-hard 问题。什么意思？就是当城市数量一多，暴力求解基本不可能。我记得有次算 20 个点的全排列，电脑跑了三天三夜没出结果……
1.2 TSP在激光切割中的应用场景
我在实际项目中，TSP 主要用在以下几个地方：
- 轮廓切割顺序优化：板子上有几十个零件，先切哪个后切哪个，直接影响空行程距离
- 穿孔点位置选择：每个轮廓的切入点选在哪，也会影响整体路径
- 微连接路径规划：有些零件需要留微连接，切割顺序要配合微连接的位置
- 多板材套料切割：一张大板上有多种零件，路径规划更复杂
给大家看一个我实际测过的数据：
| 零件数量 | 随机路径（米） | TSP优化路径（米） | 节省比例 |
|---|---|---|---|
| 10 | 8.5 | 5.2 | 38.8% |
| 20 | 16.3 | 9.1 | 44.2% |
| 50 | 42.7 | 21.5 | 49.6% |
看到没？零件越多，优化效果越明显。我曾经帮一个客户优化过 200 多个零件的切割路径，空行程直接砍掉了一半多，切割效率提升了 35%。
1.3 贪心算法求解TSP
说到求解 TSP，最简单直观的方法就是贪心算法。
贪心的思路很朴素：每一步都选当前最优的。就像你逛街，每到一个路口，都选最近的那条路走。
具体步骤：
- 从起点出发
- 找离当前点最近的未访问点
- 走过去，标记已访问
- 重复步骤 2-3，直到所有点都访问完
- 最后回到起点
我的经验：贪心算法虽然简单，但效果其实不差。对于 50 个点以内的切割任务，贪心解通常能达到最优解的 80%-90%。而且计算速度极快，毫秒级出结果。
但要注意，贪心算法有个毛病——短视。它只看眼前，不看长远。我曾经遇到过一个案例，贪心算法选了一条看似很短的路径，结果走到最后发现绕了个大圈……
避坑指南：我曾经在切割一个环形排列的零件时，贪心算法给出的路径在局部绕来绕去，总路径反而比手工排的还长。后来我加了「两两交换」的局部优化，才把结果拉回来。
1.4 最近邻算法实现与代码示例
最近邻算法（Nearest Neighbor）其实就是贪心思想在 TSP 上的具体实现。我习惯用 Python 写原型，然后移植到 C++ 做生产环境。
下面是我常用的一个实现：
import numpy as np
def nearest_neighbor_tsp(points, start_idx=0):
"""
最近邻算法求解TSP
points: 坐标点列表，格式 [(x1,y1), (x2,y2), ...]
start_idx: 起点索引
返回: 路径顺序和总距离
"""
n = len(points)
visited = [False] * n
path = [start_idx]
visited[start_idx] = True
total_dist = 0.0
current = start_idx
for _ in range(n - 1):
# 找最近的未访问点
min_dist = float('inf')
nearest = -1
for j in range(n):
if not visited[j]:
# 计算欧氏距离
dx = points[current][0] - points[j][0]
dy = points[current][1] - points[j][1]
dist = np.sqrt(dx*dx + dy*dy)
if dist < min_dist:
min_dist = dist
nearest = j
# 走过去
path.append(nearest)
visited[nearest] = True
total_dist += min_dist
current = nearest
# 回到起点
dx = points[current][0] - points[start_idx][0]
dy = points[current][1] - points[start_idx][1]
total_dist += np.sqrt(dx*dx + dy*dy)
path.append(start_idx)
return path, total_dist
# 使用示例
if __name__ == "__main__":
# 模拟10个切割轮廓的中心点
points = [
(10, 20), (35, 45), (60, 30), (80, 70),
(25, 80), (55, 10), (90, 50), (15, 60),
(70, 85), (40, 40)
]
path, distance = nearest_neighbor_tsp(points)
print(f"优化路径: {path}")
print(f"总空行程: {distance:.2f} mm")
代码说明：
- 输入是切割轮廓的中心点坐标列表
- 算法从指定起点开始，每次找最近的点
- 最后强制回到起点，形成闭合路径
- 时间复杂度 O(n²)，对于几百个点完全够用
实际用的时候，我一般会做几个改进：
- 多起点尝试：分别以不同点做起点，取最优结果
- 2-opt 优化：对贪心结果做局部边交换，能再提升 5%-10%
- 考虑切割方向：有些轮廓需要顺时针或逆时针切，要加约束
小技巧：我习惯在贪心之后加一轮 2-opt 优化。代码就多几十行，但效果立竿见影。特别是零件数量在 30-100 之间时，这个组合拳性价比最高。
最后给大家看一张我整理的 TSP 路径优化知识体系图：
嗯，以上就是 TSP 在激光切割路径优化中的基础内容。贪心算法虽然简单，但它是很多高级算法的基础。我建议你先把这个跑通，再去看遗传算法、模拟退火这些更复杂的方法。
一句话总结：TSP 路径优化，说白了就是让切割头少跑冤枉路。贪心算法虽然不完美，但胜在简单实用，是入门首选。