简介本资源围绕多旅行商问题MTSP展开分别用遗传算法与模拟退火算法实现求解面向计算机、人工智能、自动化等专业学生及需要课程设计、毕设或算法进阶的学习者。项目包含两个实验场景工厂巡检路线安排与运输机航线规划数据分别存放于对应文本文件中最终可视化结果在Jupyter Notebook中呈现。压缩包共15个文件约3.26MB涵盖Python源码、数据文本、Notebook、HTML结果页、PNG与GIF动图及说明文档结构清晰便于对照算法实现与实验效果。目前已有78人学习下载。读者可获取两套完整算法代码、实验数据与可视化结果理解GA与SA在MTSP中的建模差异、参数设置与收敛表现也可在此基础上修改扩展用于课程作业、毕业设计或项目初期演示。1. 从两份真实数据说起这个 MTSP 资源包到底能跑出什么多旅行商问题MTSP不是课本里那种只存在于论文里的抽象模型它对应的是很具体的调度场景多个执行体从同一个或不同的起点出发各自走一条路线把所有目标点覆盖完最后让总路程或最大单程尽量小。这个资源包直接给了两个能跑的实验——工厂巡检路线和运输机航线数据分别是data/routine_nodes.txt和data/provincial_capital.txt算法侧同时实现了遗传算法和模拟退火算法可视化结果落在mtsp_ga_and_sa.ipynb里。它适合正在做课程设计、毕设或者需要快速验证 MTSP 求解效果的人。你拿到手不是一堆散代码而是一套能对照实验、能改参数、能换数据的完整流程。2. 遗传算法解 MTSP编码、适应度与交叉变异的落地细节2.1 为什么 MTSP 不能直接套用单旅行商的排列编码单旅行商问题TSP最自然的编码是一个城市排列比如[0, 3, 1, 4, 2]解码就是按顺序走一圈。但 MTSP 有多个旅行商如果还是只用一个排列就必须额外决定“在哪里切分给不同的人”。这个资源包里的genetic_algorithm.py采用的是分段式染色体一条染色体仍然是一个完整排列但额外维护一组断点把排列切成若干段每段对应一个旅行商的路线。这样做的好处是交叉和变异算子可以复用 TSP 的成熟逻辑代价是断点位置也需要参与进化。常见做法是固定断点数量等于旅行商数量然后让断点在排列长度范围内随机生成并参与变异。这个项目里两个实验的旅行商数量不同实验一工厂巡检通常是多组人员分区域实验二运输机航线则对应多架飞机从不同省会出发。你在改数据时第一件要确认的事就是旅行商数量这个参数在哪里设置否则跑出来的路线数对不上你的实际业务。2.2 适应度函数怎么写才不翻车适应度函数直接决定算法往哪个方向收敛。MTSP 的优化目标通常有两种最小化总路程或者最小化最大单条路线长度。前者适合总成本敏感的场景后者适合负载均衡敏感的场景。这个资源包的 GA 实现里适应度是总路程的倒数加上一个惩罚项惩罚那些路线长度严重不均衡的个体。# genetic_algorithm.py 中适应度计算的核心逻辑示意 def fitness(self, individual): routes self.decode(individual) # 把染色体解码成多条路线 total_dist sum(self.route_distance(r) for r in routes) max_dist max(self.route_distance(r) for r in routes) # 惩罚不均衡最大路线越长惩罚越重 balance_penalty self.alpha * max_dist return 1.0 / (total_dist balance_penalty 1e-6)这里的alpha是均衡权重调大它会让算法更倾向于把路程摊平调小则更看重总路程最短。很多新手跑出来一条路线特别长、其他路线很短就是因为alpha设得太小或者根本没设。我一般会先把alpha设成 0.1 左右跑一轮看路线分布再决定往哪个方向调。2.3 交叉与变异算子的参数怎么设GA 的核心参数是种群大小、交叉概率、变异概率和迭代次数。这个资源包里的默认值在genetic_algorithm.py的入口部分可以找到通常是种群 100、交叉 0.8、变异 0.05、迭代 500。但默认值不一定适合你的数据规模。城市数量从 20 涨到 100 时种群太小会导致早熟收敛太大则单轮迭代变慢。# 运行 GA 的典型调用方式 from genetic_algorithm import GeneticAlgorithm ga GeneticAlgorithm( data_filedata/routine_nodes.txt, num_salesmen3, # 旅行商数量 pop_size120, # 种群规模 crossover_rate0.85, # 交叉概率 mutation_rate0.08, # 变异概率 generations800, # 迭代代数 alpha0.1 # 均衡惩罚权重 ) best_route, best_dist ga.run() print(最优总路程:, best_dist)参数说明num_salesmen必须和你的业务场景一致pop_size建议取城市数量的 2 到 5 倍crossover_rate一般不低于 0.7否则进化太慢mutation_rate在 0.01 到 0.1 之间太高会退化成随机搜索。迭代次数看收敛曲线如果 300 代之后适应度基本不动了加代数意义不大不如调种群或算子。2.4 用routine_nodes.txt跑通第一个实验实验一的数据是工厂巡检节点文件里每行是一个节点的坐标。运行前先确认文件路径和格式然后直接调用 GA 入口。跑完之后GA 会输出最优路线和总距离同时把结果写进ga_best_all_air_line.html这样的可视化文件里。如果你在 notebook 里跑mtsp_ga_and_sa.ipynb已经帮你把绘图逻辑串好了直接执行对应 cell 就能看到路线图。注意routine_nodes.txt和provincial_capital.txt的坐标量纲可能不同前者可能是平面坐标后者是经纬度。如果你把两个数据混用距离计算会失真。换数据时先检查utils.py里的距离函数用的是欧氏距离还是球面距离。3. 模拟退火解 MTSP邻域构造与降温策略的实操要点3.1 SA 在 MTSP 里的状态表示和邻域动作模拟退火算法解 MTSP 的思路和 GA 不同。SA 不维护种群而是从一个初始解出发通过邻域动作不断产生新解按 Metropolis 准则决定是否接受。这个资源包的simulated_annealing.py里状态表示同样是一条完整排列加断点邻域动作主要有三类交换两个城市、反转一段路线、移动断点位置。这三类动作对应不同的搜索能力。交换城市适合微调局部顺序反转路线适合打散长路径移动断点则直接改变旅行商之间的任务分配。实际跑的时候如果只做交换解容易卡在局部最优如果只做断点移动路线内部顺序又优化不动。常见做法是给三类动作分配不同权重比如交换 0.5、反转 0.3、断点移动 0.2。3.2 降温系数和初始温度怎么定SA 最玄学的两个参数就是初始温度和降温系数。初始温度太高前期接受大量劣解收敛慢太低则一开始就陷入局部最优。这个资源包里初始温度是根据初始解的目标函数值估算的降温系数默认在 0.95 到 0.99 之间。# simulated_annealing.py 中的降温循环示意 def anneal(self): current self.initial_solution() best current T self.initial_temp while T self.min_temp: for _ in range(self.iter_per_temp): neighbor self.random_neighbor(current) delta self.cost(neighbor) - self.cost(current) if delta 0 or random.random() math.exp(-delta / T): current neighbor if self.cost(current) self.cost(best): best current T * self.cooling_rate # 降温 return bestcooling_rate越接近 1降温越慢搜索越充分但耗时越长。iter_per_temp是每个温度下的迭代次数太小会导致每个温度还没搜够就降下去了。我一般会把cooling_rate设在 0.97 左右iter_per_temp取城市数量的 5 到 10 倍先跑一轮看收敛曲线再微调。3.3 用provincial_capital.txt跑通第二个实验实验二的数据是省会城市坐标对应运输机航线规划。这个数据的规模比实验一大城市之间距离也更远所以 SA 的初始温度和迭代次数都要相应调大。运行方式和 GA 类似调用simulated_annealing.py的入口指定数据文件和旅行商数量跑完后结果会写入sa_best_all_air_line.html。from simulated_annealing import SimulatedAnnealing sa SimulatedAnnealing( data_filedata/provincial_capital.txt, num_salesmen4, initial_temp1000, cooling_rate0.97, iter_per_temp200, min_temp1e-3 ) best_route, best_dist sa.run() print(SA 最优总路程:, best_dist)参数说明initial_temp可以先用 1000 试如果前期接受率低于 0.5 就调高cooling_rate不要低于 0.9否则退火太快min_temp是终止温度设到 1e-3 量级就够了。跑完 SA 之后建议和 GA 的结果对比一下两个算法在同一数据上的表现差异能帮你判断参数是否合理。3.4 GA 和 SA 在同一数据上的对比方法这个资源包的价值之一就是让你能直接对比两种算法。mtsp_ga_and_sa.ipynb里已经把两个实验的 GA 和 SA 结果放在一起可视化。你可以在 notebook 里分别跑两个算法记录总路程、最大单条路线长度和运行时间然后画成对比图。对比时要注意GA 是种群搜索单次运行结果波动较大最好跑 5 次取平均SA 是单点搜索结果受初始解影响明显可以换几个随机种子各跑一次。如果 GA 的平均结果明显优于 SA可能是 SA 的降温策略太激进如果 SA 反超 GA检查 GA 的种群大小和变异率是不是设得太保守。4. 避坑与排查跑 MTSP 代码时最容易翻车的五个地方4.1 现象路线数量对不上旅行商数量原因num_salesmen参数没有正确传入或者断点生成逻辑在数据量变化时越界了。解决先打印解码后的路线列表长度确认等于num_salesmen如果不等检查断点生成函数是否用了硬编码的索引范围。4.2 现象GA 跑了很久适应度不涨原因种群多样性过早丢失或者变异率太低导致新解产生不足。解决把mutation_rate从 0.01 提到 0.05 以上同时检查交叉算子是否真的在交换有效片段。如果还是不动把种群大小翻倍再试。4.3 现象SA 结果每次差异特别大原因初始温度或降温系数设置不合理导致搜索过程不稳定。解决固定随机种子跑几次看结果方差如果方差过大把cooling_rate调高到 0.98 以上并增加iter_per_temp。4.4 现象可视化 HTML 打开是空白原因绘图数据没有正确写入或者浏览器拦截了本地文件。解决先检查 notebook 里绘图 cell 是否执行成功再看 HTML 文件大小是否正常。如果文件很小说明数据没写进去回到代码里检查结果保存路径。4.5 现象换了自己的数据后距离计算明显不对原因坐标量纲和距离函数不匹配比如经纬度用了欧氏距离。解决打开utils.py确认距离函数是euclidean还是haversine根据你的数据格式切换。如果是经纬度必须用球面距离否则结果没有参考价值。5. 进阶用法把 MTSP 求解器接进你自己的调度流程这个资源包最实用的进阶方向是把 GA 或 SA 的求解结果导出成结构化数据再接进你自己的排班或路径规划流程。mtsp_ga_and_sa.ipynb里已经有把路线写成 HTML 的逻辑但 HTML 不方便程序消费。我一般会加一个导出 JSON 的函数把每条路线的节点顺序、总距离、单条距离都存下来。import json def export_routes(routes, distances, filenameroutes.json): result [] for i, (route, dist) in enumerate(zip(routes, distances)): result.append({ salesman_id: i, nodes: route, distance: dist }) with open(filename, w, encodingutf-8) as f: json.dump(result, f, ensure_asciiFalse, indent2) print(f已导出 {len(result)} 条路线到 {filename})导出之后你可以用这个 JSON 去驱动地图 API 画线或者喂给排班系统做进一步约束校验。另一个进阶方向是给 GA 加精英保留策略每代把最好的几个个体直接复制到下一代防止最优解在交叉变异中被破坏。这个改动很小但在 MTSP 上通常能明显提升收敛稳定性。验证方法上我习惯用两个指标交叉检查一是总路程二是最大单条路线长度。如果总路程降了但最大单条路线反而涨了说明算法在牺牲均衡性换总距离这时候要回头调alpha或 SA 的邻域权重。从那以后我每次换数据或改参数都强制走一遍“先跑小规模看路线分布再跑全量看收敛曲线”的流程避免直接上全量数据跑半天才发现参数不对。希望帮到你。本文还有配套的精品资源点击获取
