简介：这份资源收录了2017年全国大学生数学建模竞赛高教杯奖D题的完整论文，主题为化工厂巡检路径规划与建模，适合数学建模参赛者、毕业设计学生及相关方向研究者参考。论文系统解决了巡检线路设计与排班优化问题，构建了以最少巡检人员和均衡工作量为目标的多目标规划模型，借助LINGO与Excel进行求解，详细给出固时上班、休息进餐、错时上班等多种情形下的巡检路线与人员配置方案，并引入均衡度指标进行优化对比。资源包共含1个PDF文件，大小约1.09MB，内容为完整论文正文、模型假设、符号说明及附录中的巡检时间表，可直接作为竞赛复盘、课程设计或项目入门的参考资料。已有118人学习下载，适合希望掌握路径规划建模思路的中高级学习者。
1. 赛题回顾：化工厂巡检到底在优化什么
2017年国赛D题“化工厂巡检路径规划与建模”拿到手的时候，很多队伍第一反应是“这不就是个TSP吗”——把每个巡检点走一遍，找最短回路就行。这个判断方向没错，但真正动手才发现，题目远没有这么简单。它表面上是一条路径问题，实际上混杂了图论建模、多目标权衡、时间窗约束和多人协作分配，每一个环节都藏着失分点。
这道题有一个很特别的工程背景：化工厂的巡检不是“逛一圈”就结束，而是有明确的周期要求——比如每两小时要完成一轮全部点位的检查，每次到点需要停留固定时长做设备状态确认。也就是说，路径上消耗的时间由两部分构成：点位之间的行走时间，加上每个点位的停留时间。后者是固定的，前者才是优化的空间。真正要回答的问题是：在满足巡检频次和单轮时长限制的前提下，怎么安排人员路线，让总行走时间最短、人员利用率最均衡。
从建模角度看，这道题考察的其实不是某个高深算法，而是三件事：能不能把一个真实的厂区场景抽象成正确的图模型；能不能在模型基础上选对求解策略；能不能把抽象出来的结果翻译回生产语言，让评委觉得“这个方案真的能落地”。我复盘这道题时最大的体会是，获奖论文和普通论文的分水岭不在算法复杂度，而在建模环节的严谨度和结果分析的说服力。
所以这篇复盘文章，我打算按当时做题的完整流程来讲：从数据清洗和图构建，到最短路计算，再到路径优化和多人分配，最后落到论文图表和避坑经验。不绕弯子，全是实操层面能直接拿去用的东西。
2. 建模第一步：把厂区地图变成计算机能算的图
2.1 巡检点的坐标与耗时数据
题目通常会给出巡检点的编号、平面坐标和单点停留时间。以当年数据为例，大约30个巡检点分布在厂区不同装置附近，停留时间从5分钟到15分钟不等，有些重点设备需要更细致的检查。拿到这些数据第一件事不是急着写算法，而是先画散点图，把所有点位在坐标系里标出来，同时把起点（通常是值班室或调度室）也标上去。
这一步很重要。画完图你会直观看到几件事：点位分布是否有明显的区域聚集；哪些点离主路网很远、通行成本很高；经纬度坐标是否可以直接当平面坐标用（如果跨度很大就需要做投影换算）。这些信息直接决定后面的分区和路径策略，跳过这一步直接上算法，很容易在后续解释结果时变得很被动——评委问“为什么这个点要绕这么大一圈”时，如果连地图长什么样都没看过，是答不上来的。
停留时间需要单独列一个数组存好，它不参与路径计算，但会参与总耗时的最终累加。我当时做了一个表，格式类似下面这样：
| 巡检点编号 | X坐标(m) | Y坐标(m) | 停留时间(min) |
|---|---|---|---|
| P01 | 120.5 | 86.3 | 8 |
| P02 | 89.2 | 210.7 | 12 |
| ... | ... | ... | ... |
| P30 | 310.4 | 55.8 | 6 |
数据整理成这种结构化表格之后，后面所有建模和编程都不用再翻原始题目，效率会高很多。
2.2 为什么不能直接用欧氏距离
很多新手队伍到这里会犯一个经典错误：直接用两个点的直线距离当路径权重。这在数学上很干净，在工程上却站不住脚。化工厂区内有装置区、管廊、围栏、道路系统，巡检人员只能沿着厂区道路走，不能穿越设备区域。两个点位之间直线距离500米，实际绕行可能超过800米，偏差率达到60%左右。
正确的做法是先把厂区道路系统也抽象成图。题目给的数据里虽然没有直接给出道路坐标，但常见处理方法是：根据厂区平面示意图，把主干道和支路的交叉口作为中间节点，把巡检点映射到距离最近的道路节点上，然后在这个“道路网络图”上计算任意两点之间的最短路径。这样一来，边的权重就变成真实的道路长度，点位之间的实际通行距离也有了依据。
这种处理方式会多花一些时间，但非常值得。一方面它让模型更贴近真实场景，论文里可以有理有据地说明“本模型采用道路网络距离而非欧氏距离”；另一方面，后续Floyd算法算出的最短路矩阵，本身就是从这张道路图上推出来的，每一步都有迹可循。评委最怕看到凭空出现的距离矩阵，而这个设计方案正好堵住了这个质疑。
2.3 邻接矩阵的构建原理
道路网络图确定之后，下一步是构建邻接矩阵。构建规则很简单：两个节点之间有道路直接相连，矩阵值就是道路长度；没有直接相连，设为无穷大；对角线为0。这里的“无穷大”在代码里通常用一个大数表示，比如99999，千万不要直接用Python的float('inf')，否则后面Floyd算法的加法运算可能溢出或者变得很慢。
构建完道路网络的邻接矩阵后，把巡检点映射到邻近道路节点上，得到一个“包含了巡检点的扩展图”。这个扩展图才是真正用于路径搜索的图。我建议把这张图的节点分为两类：一类是纯道路交叉口，它们是可经过的中间节点；另一类是巡检点，它们必须被访问。这样分类在后续解释优化结果时非常方便，也方便在图上做可视化区分。
3. 核心算法：用Floyd一次性算出所有点位间的最短路径
3.1 为什么选择Floyd而不是Dijkstra
单源最短路径用Dijkstra很顺，但这道题需要的是任意两个巡检点之间的最短距离——因为路径规划时，你并不知道下一条要接哪个点。与其每次调用Dijkstra，不如直接用Floyd算法，一次性把全源最短路算出来，时间O(n³)在50个节点以内完全够用。当年数据也就三四十个节点，跑一遍Floyd，眨眼的功夫就出结果了。
Floyd的核心思想是动态规划：从i到j的最短路径，要么直接到达，要么经过某个中间节点k中转更短。三层循环不断松弛，直到所有组合都被检查过。代码如下，几乎可以直接抄：
import numpy as np def floyd(graph): num_nodes = len(graph) dist = np.array(graph, dtype=float) # path矩阵用于追踪路径，方便后续回溯具体路线 path = np.zeros((num_nodes, num_nodes), dtype=int) for i in range(num_nodes): for j in range(num_nodes): path[i][j] = j for k in range(num_nodes): for i in range(num_nodes): for j in range(num_nodes): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] path[i][j] = path[i][k] return dist, path计算完成后，dist矩阵里存的就是任意两个节点之间的最短道路距离。后续无论是做单人的TSP优化，还是做多人的分区规划，都直接查这张表，不用再重复计算最短路。这也是建模效率的关键：把复杂问题拆成“先算距离，再排路径”两个阶段，让主优化过程专注于路径顺序本身。
3.2 巡检路径耗时如何精确计算
有了任意两点间的最短道路距离，一条完整巡检路径的总耗时计算就清晰了。假设一条路径从起点S出发，依次经过P12、P08、P05，最后回到S，那么总时间就是：
T_total = d(S,P12)/v + t_P12 + d(P12,P08)/v + t_P08 + d(P08,P05)/v + t_P05 + d(P05,S)/v其中d表示Floyd算出的最短距离，v是巡检人员步行速度（题目一般会给出，没给的话取1.2m/s左右比较合理），t是每个点的停留时间。这个公式看起来简单，却是所有优化算法的“评估函数”。路径顺序一变，总耗时就会变，优化就是不断找总耗时更小的排序。
一个容易被忽视的地方是：返回起点的最后一段路程也要算进去。很多队伍在前期测试时把路径算成开环，结果得出一个非常漂亮的总时间，却忘了一家一圈必须回到值班室登记液位记录、交班归档，最终实测时间会多出一截。开环闭环的差别在论文里必须交代清楚，否则评委只要拿着路线图一量就能发现漏洞。
4. 路径规划优化：从单旅行商到多人协作
4.1 单人巡检的TSP框架与初始解生成
单人巡检场景下，问题退化成标准TSP：从起点出发，给定所有巡检点坐标和停留时间，求一条经过所有点并返回起点的最短路径。这里不需要用太复杂的算法起步，先把一个可靠的基础框架搭起来，后面再迭代优化。
推荐做法是：先用最近邻算法生成一个初始解。最近邻的思路很直白：从起点开始，每次都去当前距离最近的未访问巡检点，直到所有点都访问完，最后回到起点。这个算法虽然不能保证全局最优，但通常能在很短时间内给出一条合理路径，而且代码只要十几行：
def nearest_neighbor(start_idx, points_idx, dist_matrix): unvisited = set(points_idx) route = [start_idx] current = start_idx while unvisited: nearest = min(unvisited, key=lambda p: dist_matrix[current][p]) route.append(nearest) unvisited.remove(nearest) current = nearest route.append(start_idx) return route初始解的作用是给后续优化提供一个不错的起点。直接在这个解上做局部搜索，比在随机解上搜索收敛快得多。这也是为什么我一直强调“先贪心，再改进”——TSP类问题里，一个可靠的初始解比什么都重要。
4.2 2-opt局部搜索：简单但极其有效的改进策略
有了初始解，下一步用2-opt做改进。2-opt的思路同样很朴素：在路径中选两条边，断开，然后反向连接，看新路径是否更短。如果更短就保留，否则继续尝试下一组边。反复迭代直到找不到改进为止。
def two_opt(route, dist_matrix): improved = True best_route = route best_cost = route_cost(route, dist_matrix) while improved: improved = False for i in range(1, len(route) - 2): for j in range(i + 1, len(route) - 1): new_route = best_route[:i] + best_route[i:j+1][::-1] + best_route[j+1:] new_cost = route_cost(new_route, dist_matrix) if new_cost < best_cost: best_route = new_route best_cost = new_cost improved = True route = best_route return best_route, best_cost2-opt是我做路径规划题时最推荐的算法，没有之一。它实现简单、运行快速，而且对TSP类问题的改善效果非常明显。实测下来，最近邻加2-opt的组合通常能把初始解优化10%到20%，这个幅度在论文里完全拿得出手。如果想再进一步，可以换到3-opt或者在2-opt基础上叠加一个模拟退火框架，但那属于锦上添花，题目基础分已经不缺了。
4.3 多人巡检的分区与协作策略
接下来是2017年D题真正拉开差距的地方：巡检不是一个人完成的，而是多人分组完成。这意味着要把“一条回路”变成“多条回路”，同时还要保证各条回路的工作量尽量均衡。
一种经典做法是先把巡检点按空间位置聚类，再对每个聚类的子集单独做TSP优化。聚类方法可以用K-means，也可以用更省事的按角度分区——以起点为中心，把巡检点按方位角分成几组。K-means的问题是聚类结果受初始中心影响很大，有时候会把两个相隔很远但有桥梁连接的点分到同一组，导致区域内路径绕行很大。我当时的做法是：先按空间距离做一个K-means预分区，再用“总耗时均衡”作为二次修正——哪一组总耗时长，就划出几个点位给其他组。
分区完成后，每组内部用前面讲的最近邻加2-opt做TSP优化。这样问题就转化成“区域划分 + 子路径优化”两个子问题，模型模块化程度很高，论文里也容易画图展示。
多人巡检还有一个隐含约束是“巡检工具和记录设备的数量”。比如厂里只有3台气体检测仪，那么最多只能3人同时巡检。这个约束必须在分区一开始就确定组数，不能最后才想起这个限制。当年题目我记得是3组巡检人员，所以直接按3区来做。如果题目没有明确，那论文里也要给出分组数量的合理性论证，而不是拍脑袋定。
5. 模型落地：时间窗校验与排班策略
5.1 巡检频次背后的硬约束
化工厂巡检和高德导航的路径规划有一个根本区别：导航只要最短路，而巡检必须满足周期。比如规定每2小时完成一轮巡检，所有点位都要覆盖到，那么路径总耗时就不能超过这个窗口。如果优化完发现最优路径总耗时150分钟，那就不满足120分钟的要求，必须拆分成两轮或者增派人手。
这个约束在模型里要转化成不等式约束去检验。我当时是写了一段校验函数：输入一条路径的完整巡检序列，自动累加行走时间和停留时间，然后和给定的巡检周期上限做比较。如果超时，就提示“该方案不可行”。这看起来是个很小的事情，但它把“优化”和“可行性判断”两个环节彻底分开了，调试时清晰很多。
5.2 把路径方案排成实际可执行的班次表
路径规划算出来之后，还要排成具体时间表：几点几分从值班室出发，几点几分到哪个巡检点，停留多久，几点几分回值班室。这个排程要精确到分钟，而且出发时间要错开，避免两组人在同一巡检点“撞车”。
我用一个很简单的贪心法排班：第一组最早出发，第二组比第一组晚出发几分钟以错开共用路段，第三组再错开。错开时间怎么定？观察各组路径的重叠程度，重叠越多，错开时间越长。这个方法不保证数学上最优，但用起来非常顺手，在论文里也很好解释——方案的可行性比微小的理论最优重要得多。
时间窗还有一层含义是“每个巡检点允许被检查的时间范围”。比如加热炉的温度记录需要在刚切换工况后的30分钟内读一次，那就要求巡检员在特定时间窗内到达。这种约束加入后，路径规划就变成带时间窗的路径问题（VRPTW），复杂度上了一个台阶。我当时的策略是：先不强行优化带时间窗的版本，而是把巡检顺序按距离优化完之后，逐点检查每个点是否落在时间窗内，如果有冲突，再局部调整顺序或微调出发时间。这个方法虽然保守，但对拿奖来说足够了。
6. 论文呈现：评委真正想看的几张图表
6.1 巡检路线图的可视化技巧
论文里最核心的展示是一张分区巡检路线图。这张图做得好不好，直接影响评委对方案的第一印象。我当时用Matplotlib把所有巡检点、起点、道路网和最终路径画在同一张图里，每个小组用不同颜色标出，巡检点用编号标注，停留时间用点的大小反映。整张图一目了然，评委一看就知道每个组负责哪片区域、路径是怎么走的。
画图时有几个细节要注意：一是巡检点的坐标比例尺必须一致，否则图会变形；二是要标注起点名字，比如“值班室”；三是路径的线条粗细要适中，太细看不清，太粗盖住底图信息。网上常见的高级做法是叠一张厂区卫星底图，但这需要额外处理坐标对齐，比赛时间紧，直接把道路网络画出来就够了。
6.2 灵敏度分析与模型评价怎么做
一篇优秀论文的另一个标志是有灵敏度分析。这道题里最简单的灵敏度分析是看“步行速度”对最优路径的影响：速度提高10%，总耗时下降多少；速度降低10%，会不会导致方案超出巡检周期。另一个分析维度是“巡检点停留时间波动”的鲁棒性：某个关键设备停留时间增加20%，其他组的负载怎么变化。
做完灵敏度分析之后，论文的评价部分要回答一个核心问题：我这个方案到底比普通方案好多少？最简单的对比基线是“按编号顺序巡检”，也就是不优化、直接按巡检点编号从头走到尾。把这条路径的总耗时算出来，和优化后的方案对比，算出优化比例。我记得当时和编号顺序巡检相比，优化后的总路径长度缩减了大约18%，耗时缩减更多，因为还考虑到了停留时间在总耗时中的占比。这种对比非常直观，评委一看就明白优化的价值在哪里。
7. 实战避坑指南与复盘心得
7.1 我们踩过的四个坑
第一个坑是直接用欧氏距离。我们第一次跑出来的最优路径拿到厂区示意图上一比，有几段路线直接穿越了装置区，现实中根本走不了。这个教训直接导致我们推倒重来，花了大半天把道路网络补齐。
第二个坑是忘记计算返回路程。初版优化结果漂亮得吓人，总耗时连90分钟都不到，后来逐点核算才发现少加了最后一段回程。加上之后又多了15分钟，方案勉强压线达标。从那之后我养成了一个习惯：任何路径方案都必须回到“实际巡检流程表”里验算一遍，而不是只盯着优化曲线看。
第三个坑是分区不均衡。第一次用K-means聚类时，算法把点位聚集密集的区域全划给了一组，导致那一组总耗时超过其他两组将近40分钟。后来加入“耗时均衡修正”之后，三组耗时差距缩小到10分钟以内。
第四个坑是代码里的“无穷大”处理。用Python的float('inf')填邻接矩阵，Floyd更新时出现inf加inf的情况，输出dist矩阵后查了半天才发现是这个问题。后来统一用99999代替，一次通过。
7.2 这个题还能怎么延伸
做完这道题之后我发现，化工厂巡检路径规划本质上是一个“覆盖所有必须访问节点、满足时效要求、分配有限人力”的通用问题。这套方法换个壳就能用在很多领域：小区的快递员派件路线、图书馆闭馆后的巡馆检查、电力线路的巡查排班、园区的安保巡逻路线——场景不同，模型结构一模一样。
如果想在这个方向上继续深入，有几个明确的进阶方向：引入时间窗约束的VRPTW模型、用遗传算法或蚁群算法做全局优化、探索动态环境中突发任务点的再调度问题。这些方向在研究生阶段的优化类课题里很常见，也是比赛论文往外延伸的加分点。
回看这道题，它最难的地方不在算法本身，而在“把实际场景抽象成模型”和“把模型结果翻译回实际方案”这两层功夫。这两层功夫练好了，以后遇到再复杂的规划类问题都能举一反三。
本文还有配套的精品资源，点击获取
