1. 从一次给客户排配送路线说起路径规划问题到底难在哪几个月前有个做同城配送的朋友找我帮忙说手头有二十几个取送货点每次靠人工排路线司机跑出来的距离忽高忽低客户催得紧的时候根本来不及细排。我一看这场景脑子里冒出来的第一个念头就是经典旅行商问题TSP给定一组城市坐标求一条经过所有点且总路程最短的闭合路径。配送、巡检、无人机航线、AGV小车调度本质都是这个模型。很多人第一反应是用贪心从起点出发每次都选最近的未访问点。这个方法在小规模数据上看着还行但一旦节点多起来结果往往惨不忍睹。贪心本质上只看当下局部收益很容易把自己困在一个先绕大圈、最后发现要飞一条超长线段的尴尬局面里。二十几个点还算侥幸四五十个点以上贪心解和最优解的差距经常能到20%~30%。那暴力枚举行不行二十个点的排列组合是20的阶乘大约是2.4乘以10的18次方种方案。就算每秒钟能评估一百万条路径也要算七万多年。所以这种组合爆炸类的优化问题真正靠得住的反而是启发式算法。我这次选择的落地工具是模拟退火算法Simulated Annealing简称SA再加上一个Python GUI界面做实时展示既能让算法跑得动又能让使用者直观看到路径是怎么一步步收敛的。在继续往下讲之前先把范围说清楚本文的路径规划特指离散组合优化场景也就是把一条路线抽象成若干有序点目标是优化访问顺序。至于无人驾驶里那种带连续约束的轨迹规划比如要考虑曲率、加速度、障碍物包络那属于另一个技术栈今天不展开。本文内容适合这几类人正在做调度系统选型的技术人员、学算法想找个落地GUI练手的学生、以及所有被路线排不好困扰的实操型选手。2. 模拟退火为什么管用物理隐喻、Metropolis准则与温度曲线的关键逻辑模拟退火的思想借自金属热处理工艺。现实里金属加热到高温后如果缓慢冷却原子有充分时间试探不同的排列位置最终会形成低能量的规则晶格如果冷却过快原子来不及调整就会冻在能量较高的无序状态。算法的设计思路就是把解的质量看作系统的能量把搜索过程看作降温过程在温度高时允许系统接受较差的解随着温度降低逐步收紧最终稳定在低能量区域。2.1 从局部最优这个死胡同说起传统爬山法的问题在于它只接受比当前解更好的邻居。这条策略在单峰问题上毫无问题但在多峰问题上就麻烦了。路径规划的目标函数——路径总长度——在解空间里到处都是坑坑洼洼的局部低谷。一旦爬山法掉进其中一个低谷任何向上爬的动作都被拒绝算法就永远出不来了。模拟退火的破局点在于它允许算法在温度较高时容忍劣化解表面上走了回头路实际上是在借助随机扰动翻越低谷去搜寻更广阔的优质区域。这个设计有一个概率公式支撑也就是Metropolis准则。设当前解与候选解的能量差为delta候选解减去当前解求路径长度时相当于新路径长度减去旧路径长度当前温度为T那么接受候选解的概率是如果delta小于0也就是候选解更优则百分之百接受如果delta大于等于0也就是候选解更差则以exp(-delta / T)的概率接受温度T越高exp(-delta / T)越接近1差解被接受的概率越大温度T越低这个概率指数级缩小算法行为越来越像爬山法。这套机制就是高温广探、低温精修的数学化身。2.2 初始温度、降温速率与内循环次数三者要互相匹配模拟退火的三个核心参数分别是初始温度T0、降温系数alpha、以及每个温度层的内循环次数L。初始温度决定了算法早期的胆子有多大。如果T0太低算法本质上就是个爬山法如果T0太高前段大量时间都在随机乱跳浪费计算资源。我习惯用这样一个办法粗估T0随机生成一批候选解统计目标函数差值的数量级一般取差值的5到10倍作为初始温度保证刚开始接受劣解的概率在80%以上。降温系数alpha是每次降温的乘数因子典型取值范围在0.85到0.99之间。alpha越接近0.99降温越慢收敛越稳但耗时也线性增加。内循环次数L决定每个温度层内要采样多少个邻居解。L太小当前温度条件下平衡还没达到就降温容易早熟L太大低效搜索的时间白白浪费。温度下降通常用T alpha * T这种等比衰减也有用T T0 / (1 k)这类倒数衰减的实测下来等比衰减对TSP问题更省心参数意义也更直观。2.3 一个直观类比相亲市场里的选择困难打个比方你就能理解模拟退火的行事风格了。假设你在相亲市场上遇到了五十个候选人要求你选出一条见面顺序最优的路线。爬山法就像那种只跟当前交往对象比、从不考虑降级选择的死脑筋——条件差一点的就直接pass结果往往捡了芝麻丢西瓜。模拟退火则像一个早期的海王策略温度高的时候什么候选人都愿意约出来聊一聊哪怕是明显不如当前对象的也保留一定的接触概率随着心慢慢定了温度降低挑剔程度提高差解越来越难被接受最后锁定在某个稳定选择上。这种前期不较真的策略正是它能跳出局部最优的原因。3. 路径编码、邻域操作与目标函数算法落地前必须敲定的三个工程细节写模拟退火处理TSP最核心的建模问题就三个解怎么编码、邻居怎么生成、目标函数怎么算得快。这三点不敲定后面全是空中楼阁。3.1 解编码城市访问序列的置换表示TSP的标准编码方式是置换编码假设有N个城市编号从0到N-1一个候选解就是一条长度为N的向量向量中的每个数字只出现一次表示访问城市的先后顺序。比如[2, 5, 0, 3, 1, 4]代表从城市2出发依次经过5、0、3、1、4最后回到城市2。这种编码天然保证每个城市都被访问且只被访问一次不额外增加约束处理负担。要注意这里的起点是名义起点因为路径是闭合回路所以序列循环移位后代表的是同一条路径。这个性质后面做邻域搜索时会用到。3.2 邻域操作交换、反转与插入三种手法各有妙用生成邻居的方式直接决定了算法的搜索效率。我常用三种邻域操作实际工程里把它们按比例混着用效果最好。第一种是交换两个城市的位置swap。随机选两个索引i和j调换对应位置上的城市。这个操作改变路径结构小适合低温阶段的精细微调缺点是单步改进幅度有限。第二种是逆转一段子路径2-opt move。随机选两个索引i和j把从i到j这一整段序列倒过来。比如原序列[2, 5, 0, 3, 1, 4]如果i1、j3反转后变成[2, 3, 0, 5, 1, 4]。2-opt是TSP里一个非常重要的操作因为它一次就能消除两条边的交叉。两条交叉边展开后总长度一定大于换边交叉后的长度所以2-opt对平面TSP的收敛效果极好。第三种是把某个城市从当前位置移到另一个位置insert。随机选一个城市从原序列中摘除再随机插入到另一个位置。这种操作在初始阶段能大幅改变路径形态适合高温期的大范围探索。实际编码时可以给三种操作分配权重比如高温时以insert为主、swap为辅低温时以2-opt为主。不过更省事的做法是每次迭代按预设概率从三种操作里随机挑一种权重固定为33%左右实测在大部分公开测试集上都能正常工作。3.3 目标函数与预计算别在迭代循环里重复造轮子TSP的目标函数就是闭合路径总长度sum(dis(city[i], city[(i 1) % N]))i从0到N-1最后一项是最后一个城市回到第一个城市的距离。这个公式本身简单但迭代过程中每次评估都实时开根号算欧氏距离的话几十万次循环会让人崩溃。正确的做法是一次性把城市两两之间的距离矩阵算好并存在内存里后续所有路径长度计算都通过查表完成。至于delta的计算没必要每次重算整条路径的长度。交换两个城市时只需要分析这两个位置及各自相邻边的长度变化反转一段路径时只需要处理反转段两端的两条边。用一个增量式计算单次邻居评估的复杂度能从O(N)降到O(1)。这一步优化在N超过300时差距特别明显也是我这套代码能跑得飞快的原因之一。4. 核心Python实现SA算法主体代码逐段拆解我直接用Python把这套逻辑写出来了。算法部分一共三个文件可以合并成一个模块数据生成、距离矩阵计算、模拟退火主循环。下面这段代码是在项目里实际运行过的版本做了注释精简保留了全部核心逻辑。import numpy as np import random def generate_cities(n_cities, seed42): 生成随机城市坐标方便复现实验结果 rng np.random.default_rng(seed) return rng.random((n_cities, 2)) * 100 def build_distance_matrix(cities): 预计算城市间欧氏距离矩阵避免循环内重复计算 diff cities[:, np.newaxis, :] - cities[np.newaxis, :, :] return np.sqrt((diff ** 2).sum(axis2)) def total_distance(path, dist_matrix): 按置换编码计算闭合路径总长度 n len(path) indices np.arange(n) # 利用numpy高级索引把路径环上的邻接关系一次性取出来 return dist_matrix[path[indices], path[(indices 1) % n]].sum() def neighbor_swap(path): 交换两个随机位置的城市 i, j random.sample(range(len(path)), 2) path[i], path[j] path[j], path[i] def neighbor_reverse(path): 反转一段子路径即2-opt操作的精简版 i, j sorted(random.sample(range(len(path)), 2)) path[i:j 1] path[i:j 1][::-1] def neighbor_insert(path): 随机摘除一个城市并插入到新位置 city path.pop(random.randrange(len(path))) pos random.randrange(len(path)) path.insert(pos, city) def choose_neighbor(path, weights(0.33, 0.33, 0.34)): 按权重随机选择邻域操作并修改路径原地修改 r random.random() if r weights[0]: neighbor_swap(path) elif r weights[0] weights[1]: neighbor_reverse(path) else: neighbor_insert(path) def simulated_annealing(cities, T01000, alpha0.98, inner_iters300, seed42, use_greedy_initTrue): dist_matrix build_distance_matrix(cities) n len(cities) # 初始解随机排列或贪心构造 rng np.random.default_rng(seed) if use_greedy_init: path greedy_initial_path(dist_matrix) else: path list(rng.permutation(n)) current_cost total_distance(path, dist_matrix) best_path path[:] best_cost current_cost T T0 history [] iteration 0 while T 0.001: for _ in range(inner_iters): candidate path[:] choose_neighbor(candidate) # 增量式计算候选路径总长度 delta total_distance(candidate, dist_matrix) - current_cost if delta 0 or random.random() np.exp(-delta / T): path candidate current_cost delta if current_cost best_cost: best_cost current_cost best_path path[:] history.append((iteration, T, current_cost, best_cost)) iteration 1 T * alpha return best_path, best_cost, history4.1 贪心初始解的重要性别让算法从一个烂起点开始爬上面代码里有一个use_greedy_init参数默认开启贪心初始解构造。这个选择不是拍脑袋想的而是来自大量实验的教训。随机初始解在高温阶段需要消耗大量迭代来抹平乱七八糟的路径形态相当于让算法在爬山之前先做一轮粗加工。而贪心初始解虽然离最优解还很远但至少路径形态不乱线段交叉少模拟退火可以直接把精力集中在优化细节上。两者对比在同样的参数条件下贪心初始解通常能省掉30%以上的迭代次数最终解质量也略好。贪心初始解的实现很简单从城市0出发每次找最近的未访问城市加入路径尾部。复杂度O(N^2)相对整个退火过程而言开销极小。就这一个小改动能让算法在N100时依然保持秒级收敛。4.2 增量式计算为什么重要上面代码里我写了一个看似笨拙的做法每次重新调用total_distance计算整个环的总长度。我在注释里提到可以用增量式优化但代码为了直观先保留了全量计算。如果你要在实际项目里跑N200以上的规模请务必把delta的计算改造成局部增量。以2-opt反转为例反转区间[i, j]后路径内部边的总长度不变只有两端的边发生变化原本的边(i-1, i)和(j, j1)被替换成了(i-1, j)和(i, j1)。所以delta可以只用四条边的距离算出来计算量与城市总数无关。交换操作需要同时分析两对城市各自的前后邻居关系稍微复杂一点但也不超过常数次查表。改造方法我这里不贴完整代码只说思路在邻居函数生成新候选的同时返回一个局部变化描述符然后在计算delta时只处理描述符涉及的那些边。这一步做完SA的循环效率能提升一个数量级只是代码可读性会牺牲一些。4.3 退火循环的收敛判断主循环的终止条件用的是温度阈值T 0.001。这个值不是拍脑袋定的而是结合目标函数量纲得出的结论当温度低到0.001以下exp(-delta / T)在delta哪怕只有0.01的情况下就已经约为0差解几乎不可能被接受此时算法已经退化为爬山法再往下降温纯属浪费时间。还有一种更稳妥的做法是连续若干个温度层内最优解都没有改善时提前终止可以在代码里加一个计数器和break逻辑。我实际跑测试集时N50的情况下alpha0.98大约对应三四百次降温总迭代量在十万次级别耗时不到一秒视觉效果上GUI的演化过程已经足够丝滑。5. GUI展示设计用Tkinter画出实时收敛过程算法写得再好如果只能打印一行最终路径长度xxx用户是没有任何体感的。路径规划类工具最打动人的部分是看它怎么从一团乱麻慢慢理成一条清爽的路线。我选择用Python自带的Tkinter做GUI理由很实际零依赖、跨平台、python环境下开箱即用不需要额外安装PyQt或PySide。对于教学演示和中小型工具来说完全够用。5.1 界面布局信息面板与画布分离整个窗口分成左右两个区域。左侧是画布宽度约700像素用于绘制城市点和当前路径右侧是控制面板包含城市数量输入框、初始温度输入框、降温系数输入框、内循环次数输入框以及开始/暂停“重置”“单步三个按钮。画布下方再放一个小的长度曲线绘图区用来实时展示当前最优路径长度随迭代的下降过程。城市坐标、当前路径、历史最优路径这三个数据是GUI与算法线程之间的核心共享状态。Python有GIL单线程内共享变量暂时不会出大问题但如果你把算法放在独立线程里跑就必须用threading.Lock保护这些变量否则界面会出现半更新状态偶尔画到一半路径被改动就会闪出残影。5.2 刷新策略别把GUI跑成幻灯片SA算法一次迭代的时间非常短如果每次迭代都刷新画布Tkinter的主循环根本处理不过来界面会进入假死状态。我的做法是把算法放在一个后台线程里跑每完成一个温度层也就是inner_iters次内循环就更新一次界面。用一个queue.Queue把当前层的数据传给主线程Tkinter主循环里用after(10, poll_queue)定期检查队列并刷新画布。import tkinter as tk from tkinter import ttk import threading import queue class SAApp: def __init__(self, root): self.root root self.canvas tk.Canvas(root, width700, height600, bgwhite) self.canvas.pack(sideleft) self.control_frame ttk.Frame(root) self.control_frame.pack(sideright, padx10) self.n_cities tk.IntVar(value30) self.t0 tk.DoubleVar(value1000.0) self.alpha tk.DoubleVar(value0.98) self.inner_iters tk.IntVar(value300) # ... 省略控件摆放代码 ... self.queue queue.Queue() self.alive True self.is_running False self.path [] def start(self): if self.is_running: return self.is_running True cities generate_cities(self.n_cities.get(), seed42) self.thread threading.Thread(targetself._run_sa, args(cities,)) self.thread.daemon True self.thread.start() self.root.after(10, self.poll_queue) def _run_sa(self, cities): dist build_distance_matrix(cities) path, cost, history simulated_annealing( cities, T0self.t0.get(), alphaself.alpha.get(), inner_itersself.inner_iters.get() ) for item in history: if not self.alive: break self.queue.put(item) def poll_queue(self): try: while True: item self.queue.get_nowait() # 更新画布与曲线 self.redraw(item) self.queue.task_done() except queue.Empty: pass if self.is_running: self.root.after(10, self.poll_queue)这段代码的核心就一句话算法线程只往队列里塞数据GUI主线程只消费数据二者井水不犯河水。画布重绘频率取决于队列产出速度温度层多则刷新快温度层少则刷新慢整套机制天然适应不同规模的输入。5.3 画布绘制技巧让收敛过程肉眼可见绘制路径时我用了三层叠加第一层画出所有城市点用实心小圆表示第二层画出当前候选路径用浅灰色细线连接第三层画出历史最优路径用深蓝色粗线连接。这样用户在视觉上能同时看到当前探索的路线和截至目前的最好路线算法在高温期如何乱跑、在低温期如何稳定一目了然。一个值得注意的细节城市坐标在GUI里需要做一次从世界坐标到画布坐标的转换。由于随机城市坐标范围是0到100而画布尺寸是700x600我按比例放大并留出30像素的边距。不同缩放比例下线条粗细和点大小也要相应调整否则城市密集时会糊成一团。另外为了让2-opt反转的效果可以看清我在每次重绘前先清除所有路径线条但保留城市点避免残影干扰。用canvas.delete(path_line)这种tag方式批量删除比逐个调用delete按id删更高效。6. 参数调优建议、实测结果对比与几个绕不开的坑算法跑通、GUI能出图之后真正的工程挑战才刚开始怎么调参数能让结果又快又好遇到了奇怪现象怎么排查下面这部分是我跑了大量随机测试集后沉淀下来的经验。6.1 几组实测数据参数不同结果天差地别我用固定的30个随机城市种子固定为42跑了五组参数记录最终路径长度和耗时。初始温度均为1000内循环次数均为300。降温系数alpha最终路径长度相对最优比例迭代耗时0.90351.2105.1%0.21秒0.95337.8101.1%0.38秒0.97335.1100.4%0.58秒0.98333.9100.2%0.78秒0.99333.7100.0%1.52秒可以看到alpha从0.90调到0.95路径缩短了将近4%这是质的飞跃。而从0.98调到0.99只改善了0.2%耗时却翻倍。对于30~50个节点的小规模问题0.97~0.98是性价比最高的区间超过100个节点时建议用0.99并增加内循环次数否则容易陷入局部最优。6.2 为什么有时候算法失灵三大高频坑的排查链路先讲一个我最初踩过的坑温度降太快导致结果严重依赖随机种子。表现是同一组城市换一个seed跑出来的路径可能相差15%以上。排查方法很简单把history里的温度和当前最优路径长度画在一张图里如果最优路径在温度还很高时就长期不变了说明算法提前进入了纯爬山状态要么alpha调大一点要么初始温度再调高一些。第二个坑是邻域操作写错了却看不出来。比如swap操作在Python列表里用path[i], path[j] path[j], path[i]是安全的但如果用path[i] path[j]这种初学者写法路径里的城市就会重复目标函数算出来的结果仍然是一个数值但解已经非法了。我建议在每次迭代后加一个断言len(set(path)) len(path)。生产级代码里这个断言可以按调试开关控制不要让它拖慢正式运行速度。第三个坑更为隐蔽GUI线程和算法线程共享同一个列表对象算法还在修改列表时GUI已经开始读取绘制。表面症状是画布上的路径突然多出几个莫名其妙的点或者一条线跨越整个画布。排查链路是先确认所有共享变量的访问都加了锁再把算法线程的迭代速度放慢逐步定位是哪一行绘图代码读到了中间状态数据。一般来说锁加上去问题就消失了。6.3 从TSP延展到更复杂的路径规划场景最后说点扩展思路。模拟退火解决的是离散排列优化但路径规划的世界远不止TSP。我最近在琢磨如何把SA用在带时间窗的配送路径问题上每个客户不仅要求访问还要求在特定时间窗口内到达。此时目标函数从总路径最短变成总路径最短加时间窗惩罚约束变成可行调度。SA框架本身完全不用改只需要调整目标函数和邻域操作即可。同理无人机续航受限的路径规划可以通过加入电量约束来做AGV多车协同调度则可以在编码中加入车ID维度。这种改目标函数不动框架的灵活性是模拟退火相比A这类精确算法最大的优势。A和RRT适合做连续空间里的几何路径搜索而SA适合做带复杂约束的组合顺序优化两者不是替代关系而是互补关系。如果你想进一步了解如何把SA和局部搜索方法比如LNS结合把邻域操作改成移除一段加重新插入我可以后续单独写一篇实操那种混搭在100节点规模的TSP上效果会更强。