TSP路径优化

什么是旅行商问题（TSP）？

TSP问：给定一组地点和它们之间的距离，访问每个地点恰好一次并返回起点的最短路径是什么？这是组合优化中研究最多的问题之一。

TSP是NP困难的，没有已知算法能在多项式时间内最优求解大规模实例。n个地点有(n-1)!/2条可能路径。实用解法依赖启发式：最近邻法（快速但比最优长约25%），Clarke-Wright节约法，以及2-opt等元启发式。

TSP直接应用于末端配送路由、现场服务调度、PCB钻孔和仓库拣货路径优化。即使10-15%的路径改进也能为车队运营带来显著的燃料和时间节省。

Formula: 目标: 最小化 Σ d(route[i], route[i+1]) (i = 0..n) 最近邻法: 贪心访问最近的未访问地点 节约法: s(i,j) = d(depot,i) + d(depot,j) − d(i,j)

计算示例

出发点(0,0)，4个停靠点(3,4),(6,1),(8,5),(2,7)。最近邻法：总距离25.1。Clarke-Wright可能找到23.4的更短路径。

何时使用此计算器

• 配送调度员为访问10-30个客户位置的单个司机规划日常路线时
• 现场服务经理优化技术人员路线以最小化服务点之间的行驶时间时
• 仓库工程师设计通过多个通道位置的最优拣货路径时
• 销售代表规划以最短驾驶距离访问客户的多城市出差时

应避免的常见错误

• 假设最近邻解是最优的——这是贪婪启发式算法，可能比最优路线长20-25%；始终尝试多种算法并比较
• 对基于道路的路由使用直线（欧几里得）距离——由于道路网络，实际驾驶距离可能长20-40%；对道路路由尽可能使用实际距离
• 忘记包含返回起点的行程——TSP要求返回出发点；省略返程会低估总路线距离
• 将TSP应用于实际上是VRP的问题——如果有容量约束、时间窗口或多辆车辆，请使用VRP工具以获得更好的结果

如何解读结果

• 比较Nearest Neighbor和Clarke-Wright结果：如果差异显著，问题有进一步使用更高级方法优化的空间
• 毫秒级的计算时间有助于评估对您的问题规模实时重新路由是否可行
• 路线地图可视化有助于识别启发式算法可能产生的明显低效，如交叉路线或不必要的回溯

相关标准与参考

• Nearest Neighbor 与 Clarke-Wright savings (1964) — 本工具所基准测试的构造式启发式
• Lin-Kernighan 局部搜索 — 用于求解高质量 TSP 路径的事实标准启发式
• TSPLIB — 用于比较 TSP 求解器质量的标准公开基准库

常见问题

应该使用哪种算法？

15个停靠点以下用最近邻法，在最优的20-25%以内且速度快。15-50个用Clarke-Wright后加2-opt改进，在5-10%以内。50+个用元启发式或Google OR-Tools等商业求解器。

TSP与实际配送路由有什么区别？

实际路由增加了时间窗、车辆容量、交通、单行道和多车辆。TSP是基础但实际软件会叠加这些约束。TSP解提供距离下界的基准。