简介一份面向数学建模竞赛的专项学习资料以1998年全国大学生数学建模竞赛B题“灾情巡视最优路线问题”为例系统展示如何用模拟退火算法求解带约束的组合优化问题。内容从多组巡视转化为单组巡视的思路切入依次给出约束优化模型I至IV并说明Dijkstra算法求最短路径、道路距离与巡视时间换算、分组数与路线双重优化等关键处理方法覆盖问题1至问题4的建模与求解框架。资料以单个doc文档提供压缩包大小86KB适合正在备赛或学习启发式算法的本专科学生直接阅读。目前已有168人学习下载。读者可借此掌握约束最优路线模型的构建思路理解模拟退火中交换、反转、删除、插入、替换等路线调整操作以及如何兼顾总路程、分组均衡和时间限制对物流配送、交通规划等实际路径优选问题同样有迁移价值。 数学建模比赛里路线规划绝对是最经典的一类题。翻翻往年的题目从灾情巡视到无人机协同避障从快递配送再到各类资源调度本质上都在同一套框架里打转给一张网、一堆必须覆盖的点、几条约束让你设计出既满足条件又最省时间或路程的方案。而这类“最优路线”问题里模拟退火这种启发式算法几乎年年都会出现在优秀论文中。今天我想认真拆解一道很有代表性的题——灾情巡视最优路线把从建模、算法实现、结果分析到论文呈现的完整过程讲清楚。无论你是刚开始接触数学建模的新人还是正在准备国赛、研赛的选手应该都能从这套流程里拿到一套直接能用的解题思路。1. 灾情巡视问题的本质从现实场景到数学模型1.1 题目在说什么先抓住三个要素灾情巡视这类题目的背景很直白某个区域发生灾情后需要组织若干支巡视队伍从县政府驻地出发跑遍各乡镇、村等巡视点检查灾情并汇报。题目通常会给你一张道路网络图图中点代表县城和巡视点边代表道路边上标着路程或行驶时间巡视点本身还要停留检查停留时间也跟点的级别有关。现在要求设计巡视路线使得每组队伍从县城出发走完分给它的点后回到县城并且总耗时尽量短、各组工作量尽量均衡、还不能超过某个时间上限。我第一次在竞赛里拿到这题时第一反应是把它当成“走迷宫”。后来才发现把它翻译成图论语言就清爽多了这是一张无向带权图点是巡视点边是道路权值是通行时间。我们需要把这个图上的所有点分给若干支队伍每支队伍从起点O出发走一条闭合回路覆盖分到的点再回到O。用生活化的话说就是“几个快递员从仓库出发把所有客户都跑一遍最后回仓库既要让每个人别太累又要让总时间最短”。这一类问题在运筹学里的名字叫带约束的车辆路径问题如果你只考虑一支队伍那就是经典的旅行商问题TSP。概念一听好像不难但难就难在“所有点都要覆盖”“每个点只能被一支队伍访问”“各组时间要均衡”这几个约束叠在一起解法空间直接变成天文数字。1.2 数学模型怎么建变量、目标与约束建模的时候不需要一步到位先把要素写清楚。设巡视点集合为 V县城为 O组数为 k。两个点 i、j 之间的通行时间为 c_ij点 i 的停留时间为 s_i。一支巡视队伍从 O 出发经过一串点后回到 O总耗时就是路径上通行时间之和再加上沿途各点停留时间之和。这题的优化目标可以选两个方向一是最小化所有队伍的总路程或总耗时之和二是让耗时最长的那支队伍尽量短也就是最小化最大耗时。实际比赛中我更推荐把“最大耗时最小化”作为主目标因为“均衡”往往比“总路程最短”更能体现灾情巡视的现实意义——总不能让人家最倒霉的一组跑到半夜还在山路上。约束条件要列全每支队伍的路线首尾都是 O每个巡视点必须被某支队伍访问且只能访问一次每组耗时不得超过题目给出的时间上限。这里有个常见的坑很多人把“访问一次”理解成“经过一次”。但在网络图上队伍完全可能途经一个不属于本组巡视对象的点这时候该点不算被巡视也不需要停留只是在路径上“路过”。这一块如果不说明评委很容易挑出逻辑漏洞。至于为什么这题会让穷举法直接崩溃假设有 30 个点分成 3 组粗略估算所有可能分组的数量级是组合数乘以组内排列数远超任何一台比赛用笔记本在几分钟内能枚举的规模。所以我们必须放弃“找理论最优”转向“在可接受时间内找一个足够好的近似最优解”。1.3 为什么精确算法和简单贪心都不行很多人会先想到用动态规划求精确解像经典的 Held-Karp 算法能在 O(n²·2ⁿ) 时间内解决小规模 TSP。但 n30 时2³⁰ 约等于十亿动态规划状态数量照样爆炸更别提还要同时处理多组、均衡、时间上限三重约束。至于贪心算法比如每步都去最近的未访问点最近邻法速度确实快但结果往往惨不忍睹它只顾眼前很容易在最后被迫绕一个巨大的圈子回来陷入局部最优。模拟退火不一样。它允许在搜索过程中以一定概率接受“更差”的解这就相当于给了搜索过程一次“翻山越岭”的机会而不是一碰到下坡就死守在山谷里。我以前用贪心初始解加局部搜索经常在 20 个点的规模就卡死在一条明显绕远的路径上换用模拟退火之后哪怕初始解很烂跑完 20 秒的结果也往往比贪心优化一小时更好。这就是它在路线规划问题里受欢迎的根本原因。2. 模拟退火算法为什么它是“最优路线”的好解法2.1 从金属退火到寻找最优路线模拟退火的思想来自冶金学里的退火工艺金属被加热到高温后内部原子运动剧烈然后缓慢降温原子逐渐趋于低能态排列最终形成缺陷少、能量低的晶体结构。算法借用了这套物理图景把“解的好坏”类比为“系统能量”把“温度”作为控制搜索随机性的参数。算法的大框架并不复杂先随意生成一个初始解然后在一个很高的“温度”下开始迭代。每一步对当前解做一个小扰动得到一个新解计算新旧解之间的能量差。如果新解更优就接受如果新解更差也不直接扔掉而是以 exp(-Δ/T) 的概率接受它。随着温度 T 逐渐下降接受劣解的概率越来越小算法行为从“大范围乱跳”逐步过渡到“局部精细搜索”最终收敛到一个稳定解。这就像你在山里面找最低点刚出发时风很大经常一个踉跄把你吹到别的小山坡上去但好处是你有机会越过那个把你困住的山脊后来风变小了你只能在附近慢慢挪最终停在一个比较低的地方。只要降温足够慢最后找到的位置通常都不会差。2.2 针对灾情巡视的四个关键设计第一解的编码。对单支队伍来说一条路线可以编码成一串点的排列比如 [O, v3, v1, v8, v2, O]。对于多支队伍我习惯用一个“大环切段”的思路把 k 支队伍看成一条长序列序列里每隔一段插入一个 O 作为队伍起点比如 [O, v3, v1, O, v4, v8, O, v2, v5, O]。这样就用一个序列同时表达分组信息和组内顺序扰动时既可能交换点也可能调整断点位置实现起来很轻。第二目标函数。最常用的是把“最大巡视完成时间”作为主目标同时加一个罚函数处理硬约束。比如某组总耗时超过题目给出的工作上限就在目标函数里加一个很大的惩罚值如果题目要求各组用时尽量均衡还可以把“最长用时与最短用时的差值”作为附加项乘以一个权重。罚函数写起来简单但惩罚系数不能设得太大否则会破坏正常搜索我一般从 1000 起步做参数扫描。第三邻域操作。模拟退火能不能跳到好解很大程度上取决于“扰动”是否多样。我常用的三种操作是交换随机选两个点交换顺序、插入把一个点拿出来插到另一个位置、逆转把路径中间一段倒过来相当于 2-opt 操作。三种操作混合使用可以同时实现“调整分组”“优化组内顺序”“消除路线交叉”三种效果。第四参数设置。初始温度 T0 要足够高保证一开始有较高概率接受劣解我通常取 1000~5000降温系数 α 取 0.95~0.999越小降温越快、程序越短越大收敛越慢但结果更稳每个温度下迭代次数 L 取 500~2000。这些参数我都建议做成变量跑一组对比实验再定不要抄一个就冲到底。2.3 和遗传算法、蚁群算法的对比怎么选有人会问既然要找最优路线为什么不用遗传算法或者蚁群算法我做了一个对比算法实现难度跳出局部最优能力参数数量竞赛中最适合的场景模拟退火低强少好调中大规模组合优化尤其是 TSP/VRP 类遗传算法中强多调参费时解空间复杂、需要保留多种候选结构的场景蚁群算法中高依赖信息素参数多图上路径搜索类似 TSP 但收敛较慢模拟退火在竞赛中的优势非常现实代码量少、调试容易、对初值不敏感一个晚上就能跑出像样的结果。遗传算法要做选择、交叉、变异和种群管理写起来明显更重蚁群算法处理几十个点的规模也要花不少时间调信息素参数。所以如果你只想快速拿到一个稳定、可解释的好解模拟退火基本是性价比最高的选择。3. 实操过程一步步用模拟退火解灾情巡视问题3.1 数据处理与初始解构造开始写代码前先把数据变成程序认识的格式。第一步建立距离矩阵如果题目给的是坐标就计算欧氏距离如果给的是路网就需要先把路网转换成邻接矩阵再用 Floyd 算法或 Dijkstra 算法求出所有点之间的最短通行时间。这里有一个容易踩的坑直接在原图上走邻接关系容易绕远路一定要先做最短路预处理不然模拟退火再怎么搜结果都会被“绕路”拖垮。第二步把停留时间存成数组。题目一般会说明不同类型的巡视点停留时间不同比如县城附近村庄停 30 分钟、偏远乡镇停 1 小时照着表格映射过去就行。第三步构造初始解。最简单的办法是随机打乱所有点的顺序生成大序列但我更喜欢用“最近邻贪心”生成初始路线从 O 出发每次去最近的未访问点最后回到 O。这样生成的路径虽然也有很多问题但整体位置不至于太离谱能帮模拟退火省下不少迭代时间。3.2 核心代码框架代码结构并不复杂。下面是核心部分的 Python 示意用于单条 TSP 路线的模拟退火求解多组情况只要在目标函数里套一层“大环切段”的解析逻辑即可。import math import random def total_time(route, dist, stop_time): # route 形如 [O, v1, v2, ..., O]计算总耗时 t 0 for i in range(len(route) - 1): t dist[route[i]][route[i 1]] t stop_time[route[i 1]] return t def neighbor(route): # 三种扰动交换 / 插入 / 2-opt 逆转 new_route route[:] op random.randint(0, 2) if op 0: a, b random.sample(range(1, len(new_route) - 1), 2) new_route[a], new_route[b] new_route[b], new_route[a] elif op 1: a, b random.sample(range(1, len(new_route) - 1), 2) node new_route.pop(a) new_route.insert(b, node) else: a, b random.sample(range(1, len(new_route) - 1), 2) if a b: a, b b, a new_route[a:b 1] reversed(new_route[a:b 1]) return new_route def simulated_annealing(route, dist, stop_time, T03000, alpha0.998, L800, T_end1e-3): best route[:] best_e total_time(best, dist, stop_time) cur route[:] T T0 while T T_end: for _ in range(L): nxt neighbor(cur) cur_e total_time(cur, dist, stop_time) nxt_e total_time(nxt, dist, stop_time) delta nxt_e - cur_e if delta 0 or random.random() math.exp(-delta / T): cur nxt if nxt_e best_e: best nxt[:] best_e nxt_e T * alpha return best, best_e代码里最需要理解的是random.random() math.exp(-delta / T)这一行当新解更差时delta 为正数温度越高指数越接近 1劣解被接受的概率越大温度降低后指数变小几乎不再接受劣解。这就是“先探索、后收敛”的算法核心。3.3 多组巡视与均衡性调整多组情况我在编码方案里已经提过把一条大路线上嵌入断点 O代表每支队伍的起止位置。实际操作时可以先用模拟退火跑一条“包含所有点的大回路”然后按某个“均衡切割”策略把大环切成 k 段。切完后继续做局部调整找出耗时最长的一组和最短的一组从最长那组中抽出一个点插入到最短那组中的合适位置再重新用模拟退火做组内局部搜索。这个过程可以反复执行到两组用时差小于某个阈值。均衡性指标我常用两个一个是“最长耗时减最短耗时”另一个是各队耗时的标准差。写作的时候不要只报一个“最大值变小了”要报出调整前后两组对比数据才能体现模型的改进效果。3.4 结果分析与可视化模拟退火是随机算法单次结果有波动所以一定要“多次运行取最优”。我一般同一组参数独立跑 8 到 10 次记录每次的目标函数值做收敛曲线图。收敛曲线能直观展示算法从高温探索到低温收敛的全过程也是论文里最有力的“算法有效性”证据之一。可视化部分是整篇文章的门面。用 matplotlib 把巡视点、道路、分组路线画在一张图上不同组用不同颜色起点 O 用五角星标出来路线交叉情况一目了然。我记得自己第一次跑出结果时路线图里有一条组间交叉的弧线乍一看还以为有误排查之后发现是两组在各自的独立路线上确实需要路过同一个路口不算逻辑错误。这类小细节写进论文里反而能体现你认真做了结果检验。4. 常见问题与避坑技巧实录4.1 结果不稳定或者明显绕远这是模拟退火最常见的两个问题根源多半在参数上。结果不稳定说明降温太快或者迭代次数太少“搜索还没铺开就急着收敛了”。解决方法是把初始温度调高、把降温系数 α 从 0.99 改成 0.998 甚至 0.999同时把每个温度下的迭代次数从 500 提到 1500。程序跑得慢一点没关系竞赛时间通常够用。如果结果总是绕远先检查邻域操作是否太单一。只做交换而不做 2-opt 逆转路线交叉就很难消除。我的经验是三种邻域操作混合使用并且在主循环结束后再单独做一轮 2-opt 局部优化专门用来消除路径交叉。提示看到模拟退火结果差先别急着改参数。先检查目标函数是不是写对了尤其是停留时间有没有重复计算、起点 O 有没有被错误地当普通点参与交换。这类“低级 bug”比参数不合理更常见。4.2 时间上限约束总是不满足很多题会规定每支队伍必须在一个时间上限内完成巡视比如 24 小时。如果只靠罚函数去“惩罚”超时解结果经常在边界附近徘徊怎么都不肯干净地落进可行域。我的建议是双管齐下一是在初始解构造阶段就尽量让每组不超过上限比如用贪心切大环时优先保证每组时间接近上限二是在局部调整阶段每做一次扰动后检查一遍时间上限超时的新解直接加大惩罚强制搜索往可行方向走。如果始终找不到完全可行解就要回头检查约束是否真的与现实冲突。比如题目说“每组巡视完必须返回县城”但有些队伍如果去最远的点巡视一辈子都不可能按时回来那说明初始分组思路有问题不是算法的问题应该重新调整分组策略。4.3 论文里怎么把这个过程讲清楚论文呈现是竞赛中比代码更重要的部分。我的建议是分成四个模块模型假设哪些情况简化了比如“车队速度恒定”“不堵车”、数学模型符号表、目标函数、约束方程、算法设计模拟退火流程图参数表为什么这样设参数、结果分析收敛曲线、路线图、不同方案对比。另外一定要做参数敏感性分析。比如把降温系数从 0.95 改成 0.99 和 0.998跑 10 次记录最好值和平均值做一张小表格。这看起来只占几行但评委很看重“这个参数不是拍脑袋定的”这一点。5. 从这道题到竞赛实战玩法迁移与能力提升5.1 模拟退火还能解决哪些建模题把“灾情巡视最优路线”这套解法吃透你会发现它能解的题远不止这一道。无人机协同避障航迹规划本质是多点路径规划加碰撞约束应急救援设备调度本质是带时间窗的车辆路径问题甚至某些看似跟“路线”无关的题目比如空间利用率优化、排班问题也可以抽象成组合优化问题再用模拟退火处理。我见过一篇优秀论文把模拟退火用在电力抢修班组调度上核心思想跟这题一模一样只是把“道路通行时间”换成了“维修作业时间”。所以学习这类算法不要只背代码更要理解“解编码、目标函数、邻域操作、接受准则”这四个要素。换一道题你只需要改掉解的编码方式和目标函数算法骨架可以完全复用。5.2 备赛中的模型库、算法库、论文库从这道题的经验往外延伸我给准备竞赛的同学一个建议平时备赛不要只刷题要建三个自己的库。第一个是模型库把常见的预测、优化、评价类问题各整理几个典型案例第二个是算法库像模拟退火、遗传算法、蚁群算法、层次分析法这类高频算法各写一个模板脚本加好注释比赛时直接改第三个是论文库收集历年优秀论文重点看它们怎么画图、怎么排版、怎么描述算法流程。这三个库建好之后你做任何新题的速度都会快很多。5.3 关于时间安排的一点实战体会竞赛三天时间看着很长其实很紧。我的建议是第一天上午把所有队员拉到一起读题建立模型框架和确定算法方案第一天下午到第二天上午集中写代码、跑实验第二天下午开始写论文初稿边写边补实验结果第三天全力打磨图表和摘要。千万不要第一天就开始写论文因为模型很可能会改。模拟退火这种算法虽然调参比较花时间但胜在实现快、结果稳定能给后续写论文留出充足时间。我在实际做这题时还有一个心得每次改参数后都把当前收敛曲线和最优路线图存下来做好版本标记。答辩时老师问“你怎么确定这个参数组合最优”你直接把几组对比曲线和表格拍出来比任何花哨的解释都更有说服力。最后再分享一个小技巧。模拟退火跑完如果路线图里还有交叉别急着改代码先检查是不是可视化的连线顺序写错了画图时如果只按点的编号连线而没有按路线顺序连线就会出现“伪交叉”。这个错误我曾经犯过一次排查了整整一个小时才发现是绘图逻辑的问题。先排除低级错误再去怀疑算法这是经验之谈。本文还有配套的精品资源点击获取 模拟退火算法求解灾情巡视最优路线：数学建模实战全解析
简介一份面向数学建模竞赛的专项学习资料以1998年全国大学生数学建模竞赛B题“灾情巡视最优路线问题”为例系统展示如何用模拟退火算法求解带约束的组合优化问题。内容从多组巡视转化为单组巡视的思路切入依次给出约束优化模型I至IV并说明Dijkstra算法求最短路径、道路距离与巡视时间换算、分组数与路线双重优化等关键处理方法覆盖问题1至问题4的建模与求解框架。资料以单个doc文档提供压缩包大小86KB适合正在备赛或学习启发式算法的本专科学生直接阅读。目前已有168人学习下载。读者可借此掌握约束最优路线模型的构建思路理解模拟退火中交换、反转、删除、插入、替换等路线调整操作以及如何兼顾总路程、分组均衡和时间限制对物流配送、交通规划等实际路径优选问题同样有迁移价值。 数学建模比赛里路线规划绝对是最经典的一类题。翻翻往年的题目从灾情巡视到无人机协同避障从快递配送再到各类资源调度本质上都在同一套框架里打转给一张网、一堆必须覆盖的点、几条约束让你设计出既满足条件又最省时间或路程的方案。而这类“最优路线”问题里模拟退火这种启发式算法几乎年年都会出现在优秀论文中。今天我想认真拆解一道很有代表性的题——灾情巡视最优路线把从建模、算法实现、结果分析到论文呈现的完整过程讲清楚。无论你是刚开始接触数学建模的新人还是正在准备国赛、研赛的选手应该都能从这套流程里拿到一套直接能用的解题思路。1. 灾情巡视问题的本质从现实场景到数学模型1.1 题目在说什么先抓住三个要素灾情巡视这类题目的背景很直白某个区域发生灾情后需要组织若干支巡视队伍从县政府驻地出发跑遍各乡镇、村等巡视点检查灾情并汇报。题目通常会给你一张道路网络图图中点代表县城和巡视点边代表道路边上标着路程或行驶时间巡视点本身还要停留检查停留时间也跟点的级别有关。现在要求设计巡视路线使得每组队伍从县城出发走完分给它的点后回到县城并且总耗时尽量短、各组工作量尽量均衡、还不能超过某个时间上限。我第一次在竞赛里拿到这题时第一反应是把它当成“走迷宫”。后来才发现把它翻译成图论语言就清爽多了这是一张无向带权图点是巡视点边是道路权值是通行时间。我们需要把这个图上的所有点分给若干支队伍每支队伍从起点O出发走一条闭合回路覆盖分到的点再回到O。用生活化的话说就是“几个快递员从仓库出发把所有客户都跑一遍最后回仓库既要让每个人别太累又要让总时间最短”。这一类问题在运筹学里的名字叫带约束的车辆路径问题如果你只考虑一支队伍那就是经典的旅行商问题TSP。概念一听好像不难但难就难在“所有点都要覆盖”“每个点只能被一支队伍访问”“各组时间要均衡”这几个约束叠在一起解法空间直接变成天文数字。1.2 数学模型怎么建变量、目标与约束建模的时候不需要一步到位先把要素写清楚。设巡视点集合为 V县城为 O组数为 k。两个点 i、j 之间的通行时间为 c_ij点 i 的停留时间为 s_i。一支巡视队伍从 O 出发经过一串点后回到 O总耗时就是路径上通行时间之和再加上沿途各点停留时间之和。这题的优化目标可以选两个方向一是最小化所有队伍的总路程或总耗时之和二是让耗时最长的那支队伍尽量短也就是最小化最大耗时。实际比赛中我更推荐把“最大耗时最小化”作为主目标因为“均衡”往往比“总路程最短”更能体现灾情巡视的现实意义——总不能让人家最倒霉的一组跑到半夜还在山路上。约束条件要列全每支队伍的路线首尾都是 O每个巡视点必须被某支队伍访问且只能访问一次每组耗时不得超过题目给出的时间上限。这里有个常见的坑很多人把“访问一次”理解成“经过一次”。但在网络图上队伍完全可能途经一个不属于本组巡视对象的点这时候该点不算被巡视也不需要停留只是在路径上“路过”。这一块如果不说明评委很容易挑出逻辑漏洞。至于为什么这题会让穷举法直接崩溃假设有 30 个点分成 3 组粗略估算所有可能分组的数量级是组合数乘以组内排列数远超任何一台比赛用笔记本在几分钟内能枚举的规模。所以我们必须放弃“找理论最优”转向“在可接受时间内找一个足够好的近似最优解”。1.3 为什么精确算法和简单贪心都不行很多人会先想到用动态规划求精确解像经典的 Held-Karp 算法能在 O(n²·2ⁿ) 时间内解决小规模 TSP。但 n30 时2³⁰ 约等于十亿动态规划状态数量照样爆炸更别提还要同时处理多组、均衡、时间上限三重约束。至于贪心算法比如每步都去最近的未访问点最近邻法速度确实快但结果往往惨不忍睹它只顾眼前很容易在最后被迫绕一个巨大的圈子回来陷入局部最优。模拟退火不一样。它允许在搜索过程中以一定概率接受“更差”的解这就相当于给了搜索过程一次“翻山越岭”的机会而不是一碰到下坡就死守在山谷里。我以前用贪心初始解加局部搜索经常在 20 个点的规模就卡死在一条明显绕远的路径上换用模拟退火之后哪怕初始解很烂跑完 20 秒的结果也往往比贪心优化一小时更好。这就是它在路线规划问题里受欢迎的根本原因。2. 模拟退火算法为什么它是“最优路线”的好解法2.1 从金属退火到寻找最优路线模拟退火的思想来自冶金学里的退火工艺金属被加热到高温后内部原子运动剧烈然后缓慢降温原子逐渐趋于低能态排列最终形成缺陷少、能量低的晶体结构。算法借用了这套物理图景把“解的好坏”类比为“系统能量”把“温度”作为控制搜索随机性的参数。算法的大框架并不复杂先随意生成一个初始解然后在一个很高的“温度”下开始迭代。每一步对当前解做一个小扰动得到一个新解计算新旧解之间的能量差。如果新解更优就接受如果新解更差也不直接扔掉而是以 exp(-Δ/T) 的概率接受它。随着温度 T 逐渐下降接受劣解的概率越来越小算法行为从“大范围乱跳”逐步过渡到“局部精细搜索”最终收敛到一个稳定解。这就像你在山里面找最低点刚出发时风很大经常一个踉跄把你吹到别的小山坡上去但好处是你有机会越过那个把你困住的山脊后来风变小了你只能在附近慢慢挪最终停在一个比较低的地方。只要降温足够慢最后找到的位置通常都不会差。2.2 针对灾情巡视的四个关键设计第一解的编码。对单支队伍来说一条路线可以编码成一串点的排列比如 [O, v3, v1, v8, v2, O]。对于多支队伍我习惯用一个“大环切段”的思路把 k 支队伍看成一条长序列序列里每隔一段插入一个 O 作为队伍起点比如 [O, v3, v1, O, v4, v8, O, v2, v5, O]。这样就用一个序列同时表达分组信息和组内顺序扰动时既可能交换点也可能调整断点位置实现起来很轻。第二目标函数。最常用的是把“最大巡视完成时间”作为主目标同时加一个罚函数处理硬约束。比如某组总耗时超过题目给出的工作上限就在目标函数里加一个很大的惩罚值如果题目要求各组用时尽量均衡还可以把“最长用时与最短用时的差值”作为附加项乘以一个权重。罚函数写起来简单但惩罚系数不能设得太大否则会破坏正常搜索我一般从 1000 起步做参数扫描。第三邻域操作。模拟退火能不能跳到好解很大程度上取决于“扰动”是否多样。我常用的三种操作是交换随机选两个点交换顺序、插入把一个点拿出来插到另一个位置、逆转把路径中间一段倒过来相当于 2-opt 操作。三种操作混合使用可以同时实现“调整分组”“优化组内顺序”“消除路线交叉”三种效果。第四参数设置。初始温度 T0 要足够高保证一开始有较高概率接受劣解我通常取 1000~5000降温系数 α 取 0.95~0.999越小降温越快、程序越短越大收敛越慢但结果更稳每个温度下迭代次数 L 取 500~2000。这些参数我都建议做成变量跑一组对比实验再定不要抄一个就冲到底。2.3 和遗传算法、蚁群算法的对比怎么选有人会问既然要找最优路线为什么不用遗传算法或者蚁群算法我做了一个对比算法实现难度跳出局部最优能力参数数量竞赛中最适合的场景模拟退火低强少好调中大规模组合优化尤其是 TSP/VRP 类遗传算法中强多调参费时解空间复杂、需要保留多种候选结构的场景蚁群算法中高依赖信息素参数多图上路径搜索类似 TSP 但收敛较慢模拟退火在竞赛中的优势非常现实代码量少、调试容易、对初值不敏感一个晚上就能跑出像样的结果。遗传算法要做选择、交叉、变异和种群管理写起来明显更重蚁群算法处理几十个点的规模也要花不少时间调信息素参数。所以如果你只想快速拿到一个稳定、可解释的好解模拟退火基本是性价比最高的选择。3. 实操过程一步步用模拟退火解灾情巡视问题3.1 数据处理与初始解构造开始写代码前先把数据变成程序认识的格式。第一步建立距离矩阵如果题目给的是坐标就计算欧氏距离如果给的是路网就需要先把路网转换成邻接矩阵再用 Floyd 算法或 Dijkstra 算法求出所有点之间的最短通行时间。这里有一个容易踩的坑直接在原图上走邻接关系容易绕远路一定要先做最短路预处理不然模拟退火再怎么搜结果都会被“绕路”拖垮。第二步把停留时间存成数组。题目一般会说明不同类型的巡视点停留时间不同比如县城附近村庄停 30 分钟、偏远乡镇停 1 小时照着表格映射过去就行。第三步构造初始解。最简单的办法是随机打乱所有点的顺序生成大序列但我更喜欢用“最近邻贪心”生成初始路线从 O 出发每次去最近的未访问点最后回到 O。这样生成的路径虽然也有很多问题但整体位置不至于太离谱能帮模拟退火省下不少迭代时间。3.2 核心代码框架代码结构并不复杂。下面是核心部分的 Python 示意用于单条 TSP 路线的模拟退火求解多组情况只要在目标函数里套一层“大环切段”的解析逻辑即可。import math import random def total_time(route, dist, stop_time): # route 形如 [O, v1, v2, ..., O]计算总耗时 t 0 for i in range(len(route) - 1): t dist[route[i]][route[i 1]] t stop_time[route[i 1]] return t def neighbor(route): # 三种扰动交换 / 插入 / 2-opt 逆转 new_route route[:] op random.randint(0, 2) if op 0: a, b random.sample(range(1, len(new_route) - 1), 2) new_route[a], new_route[b] new_route[b], new_route[a] elif op 1: a, b random.sample(range(1, len(new_route) - 1), 2) node new_route.pop(a) new_route.insert(b, node) else: a, b random.sample(range(1, len(new_route) - 1), 2) if a b: a, b b, a new_route[a:b 1] reversed(new_route[a:b 1]) return new_route def simulated_annealing(route, dist, stop_time, T03000, alpha0.998, L800, T_end1e-3): best route[:] best_e total_time(best, dist, stop_time) cur route[:] T T0 while T T_end: for _ in range(L): nxt neighbor(cur) cur_e total_time(cur, dist, stop_time) nxt_e total_time(nxt, dist, stop_time) delta nxt_e - cur_e if delta 0 or random.random() math.exp(-delta / T): cur nxt if nxt_e best_e: best nxt[:] best_e nxt_e T * alpha return best, best_e代码里最需要理解的是random.random() math.exp(-delta / T)这一行当新解更差时delta 为正数温度越高指数越接近 1劣解被接受的概率越大温度降低后指数变小几乎不再接受劣解。这就是“先探索、后收敛”的算法核心。3.3 多组巡视与均衡性调整多组情况我在编码方案里已经提过把一条大路线上嵌入断点 O代表每支队伍的起止位置。实际操作时可以先用模拟退火跑一条“包含所有点的大回路”然后按某个“均衡切割”策略把大环切成 k 段。切完后继续做局部调整找出耗时最长的一组和最短的一组从最长那组中抽出一个点插入到最短那组中的合适位置再重新用模拟退火做组内局部搜索。这个过程可以反复执行到两组用时差小于某个阈值。均衡性指标我常用两个一个是“最长耗时减最短耗时”另一个是各队耗时的标准差。写作的时候不要只报一个“最大值变小了”要报出调整前后两组对比数据才能体现模型的改进效果。3.4 结果分析与可视化模拟退火是随机算法单次结果有波动所以一定要“多次运行取最优”。我一般同一组参数独立跑 8 到 10 次记录每次的目标函数值做收敛曲线图。收敛曲线能直观展示算法从高温探索到低温收敛的全过程也是论文里最有力的“算法有效性”证据之一。可视化部分是整篇文章的门面。用 matplotlib 把巡视点、道路、分组路线画在一张图上不同组用不同颜色起点 O 用五角星标出来路线交叉情况一目了然。我记得自己第一次跑出结果时路线图里有一条组间交叉的弧线乍一看还以为有误排查之后发现是两组在各自的独立路线上确实需要路过同一个路口不算逻辑错误。这类小细节写进论文里反而能体现你认真做了结果检验。4. 常见问题与避坑技巧实录4.1 结果不稳定或者明显绕远这是模拟退火最常见的两个问题根源多半在参数上。结果不稳定说明降温太快或者迭代次数太少“搜索还没铺开就急着收敛了”。解决方法是把初始温度调高、把降温系数 α 从 0.99 改成 0.998 甚至 0.999同时把每个温度下的迭代次数从 500 提到 1500。程序跑得慢一点没关系竞赛时间通常够用。如果结果总是绕远先检查邻域操作是否太单一。只做交换而不做 2-opt 逆转路线交叉就很难消除。我的经验是三种邻域操作混合使用并且在主循环结束后再单独做一轮 2-opt 局部优化专门用来消除路径交叉。提示看到模拟退火结果差先别急着改参数。先检查目标函数是不是写对了尤其是停留时间有没有重复计算、起点 O 有没有被错误地当普通点参与交换。这类“低级 bug”比参数不合理更常见。4.2 时间上限约束总是不满足很多题会规定每支队伍必须在一个时间上限内完成巡视比如 24 小时。如果只靠罚函数去“惩罚”超时解结果经常在边界附近徘徊怎么都不肯干净地落进可行域。我的建议是双管齐下一是在初始解构造阶段就尽量让每组不超过上限比如用贪心切大环时优先保证每组时间接近上限二是在局部调整阶段每做一次扰动后检查一遍时间上限超时的新解直接加大惩罚强制搜索往可行方向走。如果始终找不到完全可行解就要回头检查约束是否真的与现实冲突。比如题目说“每组巡视完必须返回县城”但有些队伍如果去最远的点巡视一辈子都不可能按时回来那说明初始分组思路有问题不是算法的问题应该重新调整分组策略。4.3 论文里怎么把这个过程讲清楚论文呈现是竞赛中比代码更重要的部分。我的建议是分成四个模块模型假设哪些情况简化了比如“车队速度恒定”“不堵车”、数学模型符号表、目标函数、约束方程、算法设计模拟退火流程图参数表为什么这样设参数、结果分析收敛曲线、路线图、不同方案对比。另外一定要做参数敏感性分析。比如把降温系数从 0.95 改成 0.99 和 0.998跑 10 次记录最好值和平均值做一张小表格。这看起来只占几行但评委很看重“这个参数不是拍脑袋定的”这一点。5. 从这道题到竞赛实战玩法迁移与能力提升5.1 模拟退火还能解决哪些建模题把“灾情巡视最优路线”这套解法吃透你会发现它能解的题远不止这一道。无人机协同避障航迹规划本质是多点路径规划加碰撞约束应急救援设备调度本质是带时间窗的车辆路径问题甚至某些看似跟“路线”无关的题目比如空间利用率优化、排班问题也可以抽象成组合优化问题再用模拟退火处理。我见过一篇优秀论文把模拟退火用在电力抢修班组调度上核心思想跟这题一模一样只是把“道路通行时间”换成了“维修作业时间”。所以学习这类算法不要只背代码更要理解“解编码、目标函数、邻域操作、接受准则”这四个要素。换一道题你只需要改掉解的编码方式和目标函数算法骨架可以完全复用。5.2 备赛中的模型库、算法库、论文库从这道题的经验往外延伸我给准备竞赛的同学一个建议平时备赛不要只刷题要建三个自己的库。第一个是模型库把常见的预测、优化、评价类问题各整理几个典型案例第二个是算法库像模拟退火、遗传算法、蚁群算法、层次分析法这类高频算法各写一个模板脚本加好注释比赛时直接改第三个是论文库收集历年优秀论文重点看它们怎么画图、怎么排版、怎么描述算法流程。这三个库建好之后你做任何新题的速度都会快很多。5.3 关于时间安排的一点实战体会竞赛三天时间看着很长其实很紧。我的建议是第一天上午把所有队员拉到一起读题建立模型框架和确定算法方案第一天下午到第二天上午集中写代码、跑实验第二天下午开始写论文初稿边写边补实验结果第三天全力打磨图表和摘要。千万不要第一天就开始写论文因为模型很可能会改。模拟退火这种算法虽然调参比较花时间但胜在实现快、结果稳定能给后续写论文留出充足时间。我在实际做这题时还有一个心得每次改参数后都把当前收敛曲线和最优路线图存下来做好版本标记。答辩时老师问“你怎么确定这个参数组合最优”你直接把几组对比曲线和表格拍出来比任何花哨的解释都更有说服力。最后再分享一个小技巧。模拟退火跑完如果路线图里还有交叉别急着改代码先检查是不是可视化的连线顺序写错了画图时如果只按点的编号连线而没有按路线顺序连线就会出现“伪交叉”。这个错误我曾经犯过一次排查了整整一个小时才发现是绘图逻辑的问题。先排除低级错误再去怀疑算法这是经验之谈。本文还有配套的精品资源点击获取