各组所走的路程分别为（单位：km） ：212.2、125.5、215.9， 各组所走的路程总和为（单位：km） ：553.6， 并求出其均衡度为：0.49。 4.2 问题二 4.2.1 问题分析 与第一题相同， 将巡视人员分为几组便将区域划分为几个部分。因此我们首 先确定在 24 小时内至少需要将巡视人员分为几组。在划分区域的过程中，经过 观察与计算发现，图中乡、村的分布十分的均匀，不存在某个区域集中出现乡或 者镇， 因此可以忽略停留时间对最小生成树与深度搜索的影响。所以我们套用第 一问的模型。 先进行粗略的分割得到大致所需的路程，然后根据最小生成树进行 深度优先算法，得到精确的路径，根据路径算出各组所需时间以及总时间。 4.2.2 模型的求解 首先计算需要把巡视人员分为几组： 乡镇停留时间:T=2 小时,村镇停留时间:t=1 小时,车速:V=35 公里/小时,乡 镇共有 17 个，村镇有 35 个, 总停留时间为 17×2+35=69 小时，要在 24 小时内 完成巡回，若不考虑汽车行驶时间，由 69/i<24(i 为分的组数)得到 i 最小为 4， 故至少要分 4 组。 由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的 分组,当分 4 组时各组停停留时间大约为 69/4=17.25 小时， 则每组分配在路途上 的时间大约为 24-17.25=6.75 小时。 根据第一问, 分三组时有个总巡视路程 602 公里，分 4 组时的总路程不会 比 603 公里大太多 , 不妨以 603 公里作为第二问的巡视总路程。路上约花 603/35=17 小时,若平均分配给 4 个组,每个组约需 17/4=4.25 小时小于 6.75 小 时,故巡视路线分成 4 组是合理的。 接下来套用第一题的最小生成树的 DFS 模型，得出了以下四个分组的路径：
表一 每两节点间距离表（部分）
4
将表格带入代码中（matlab 代码见附件一） ，得到了最小生成树中相邻的两 点的矩阵，表格如下：
27 50 46 14 1 2 7 49 50 24 14 15 2 38 1 51 50 26 14 43 1 3 2 37 26 21 43 12 3 4 37 34 21 48 43 13 4 39 34 32 48 20 47 18 4 40 32 33 26 22 18 23 3 6 37 53 22 47 18 17 6 7 53 30 20 46 15 44 7 8 30 52 46 19 42 11 8 41 52 31 19 45 37 35 41 10 52 29 45 16 35 36 10 42 29 28 24 25 40 5 41 9 28 27
tmax tmin 作为时间均衡度用具体实例分析在 ti 3
不同的 下，T、t、V 的改变对最佳巡视路线的影响，最终得到结果。
关键词：最小生成树 MTSP 深度优先搜索 贪心算法
1
一、 问题重述
今年夏天某县遭受水灾。为考察灾情、组织自救，该县领导决定带领有关 部门负责人到全县各乡（镇） 、村巡视。规定巡视路线为从县政府所在地出发， 走遍各乡（镇） 、村，又回到县政府所在地的路线。 题目给出一份已将该路段的公里数标注在公路边上的该县的乡（镇） 、村公 路网示意图。 1.给定巡查组数为三组，设计一组巡视路线使总路程最短且尽可能均衡。 2.给定巡视人员在各乡（镇）停留时间 T=2 小时，在各村停留时间 t=1 小 时，汽车行驶速度 V=35 公里/小时。求解应当分几组要在 24 小时内完成巡 视，并且给出这种分组下的最佳的巡视路线。 3.给定与问题二相同的 T , t 和 V 的假设，求解在巡视人员足够多的情况 下，完成巡视的最短时间是多少？并且给出最佳巡视路线。 4.若巡视组数已定（比如三组） ，要求尽快完成巡视，讨论 T，t 和 V 改变 对最佳巡视路线的影响。
灾情巡视路线
摘要
本题给出了某县的公路网示意图， 要求出在不同条件下灾情巡视的最佳分组 方案和路线。 这是一类图上点的遍历问题，也就是要用若干条闭合的曲线覆盖图 上的所有顶点， 并使某些指标达到最优。本文建模的主要思想即为利用逐步加入 法先生成一个可行路线，再利用最小生成树、启发式算法对路线进行优化调整， 并且使用均衡度概念来衡量各组路线的均衡性。 对于问题一，首先将图划分为三个区域，使每组巡视一个区域。在建立模型 的过程中， 首先使用了逐步加入法，粗略的得到三个区域的划分以及总共需要的 时间。接下来使用最小生成树算法，得到权值最小的路径。根据最小生成树，最 后运用深度优先搜索法，得到所求的精确路线。各组所走的路程分别为（单位： km） ：212.2、125.5、215.9，路程总和为 553.6，均衡度为：0.49。 对于问题二，与第一题相同，将巡视人员分为几组便将区域划分为几个部 分。在划分区域的过程中，忽略停留时间对最小生成树与深度搜索的影响。所 以套用第一问的模型。先粗略的分割得到大致所需的路程，然后根据最小生成 树的深度优先算法计算，得到精确的路径，根据路径算出各组所需时间以及总 时间。各组所需走的路程分别为（单位/km） ：142.5、152.1、194.6、189.2，各 组所需时间分别为（单位/h） ：21.07、 21.34、 22.56、23.40，均衡度为：0.3。 对于问题三，最短距离即为从原点到到最远点的距离，从而求出最短时间， 在其他组的路径中，要保证时间小于最短时间。以此原则寻找其他路径，并使最 后的路径包括所有的村、镇、乡。在寻找路径的过程中，使用贪心算法，在每点 周围寻找路径最短的相邻点， 以此保证路径最优， 最后得到的所需组数为 22 组。 对于问题四， 使用理论分析对问题四进行讨论。 先将巡视时间用路程、 速度、 停留时间等变量表示。其次定义
G 11 J 19 L 7 6 5 2 O 各组所走的路程分别为（单位：km） ：136.5、191.1、232.1 各组所走的路程总和为（单位：km） ：559.7 并求出其均衡度为：0.54.
接下来求取该图的最小生成树：在一个给定的无向图 G =（V，E） 中，(u,v) 代表连接顶点
表二 最小生成树相邻两节点标号矩阵 根据表格画出最小生成树图：
图二 最小生成树路径图 最后根据最小生成树进行深度优先搜索，得到最终精确路径。 深度优先遍历图的方法是，从图中某顶点 v 出发： （1）访问顶点 v ； （2）依次从 v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图 中和 v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新
5
进行深度优先遍历，直到图中所有顶点均被访问过为止。 基于最小生成树的深度优先搜索过程流程图如下：
图三 基于最小生成树的深度优先搜索过程流程图
6
根据这种方法（Matlab 源代码见附件二） ，可得到以下路线：
: O P 28 27 26 N 24 23 21 K 22 17 16 I 15 I 18 J 19 L 20 25 M O : O 1 B A 34 35 33 31 32 30 Q 29 R O : O 2 5 6 7 E 11 G 13 14 H 12 F 10 F 9 E 84 D 3C O
：O C B 34 35 32 30 Q 29 R 31 33 A 1 O ：O P 28 27 26 N 24 23 22 17 16 I 15 I 18 K 21 20 M O ：O 2 3 D 4 8 E 9 F 10 F 12 H 14 13
2
三、 符号说明
四、 模型的建立与求解
4.1 问题一 4.1.1 问题分析 题目给定巡查组数为三组，要求设计一组巡视路线使总路程最短且尽可能 均衡。因此考虑将图划分为三个区域，使每组巡视一个区域。划分过程中既要 总路程最短，又应尽量使各组均衡，即各组通过的路程数接近，经过的乡、村 数目接近。在建立模型的过程中，首先使用了逐步加入法，粗略的得到三个区 域的划分以及总共需要的时间。接下来使用最小生成树算法，得到权值最小的 路径。根据最小生成树，最后运用深度优先搜索法，得到所求的精确路线。 4.1.2 树的深度优先搜索模型的建立与求解 通过对问题一进行分析， 锁定问题一的关键为如何对该公路网络图进行区域 划分。 本文首先使用逐步加入法得到一个使得总路程较短的初始化路线，再根据 逐步加入法的结果使用最小生成树算法， 对生成的最小生成树进行深度优先搜索 法， 进一步得到最终的精确路线。我们首先将题目中的图转化为一个节点间的简 易图（图一） ，在进行模型的建立与求解。
u 与顶点 v 的边（即） ，而 w(u,v)代表此边的权重，(T) 最小，则此 T 为 G 的最小生成树。
(t)
(u,v) t
(u,v)
1 ○
即最小生成树是将图中所有边按权值从大到小排列， 依次选所剩最小的边加 入边集 T，只要不和前面加入的边构成回路，直到 T 中有 n-1 条边，则 T 是最小 生成树。该题中，我们首先做出每两点之间的距离矩阵，表格如下：
二、 问题假设
1. 2. 3. 4. 5. 6. 假设图上标注的公路均未受水灾影响，仍可正常通过行，不影响巡查路线。 假设在各乡（镇） 、村均能准时到达、准时离开。 假设巡视人员的用食、休息等均在规定停留时间内，不会影响正常巡视。 假设汽车行驶速度不受外界因素影响，始终保持 35km/h 匀速行驶。 假设巡视过程中汽车、巡视人员等均无任何突发情况影响巡视进度。 假设各巡视内成员巡视行动一致，各成员巡视进度统一
图一 简化公路网络图
3
首先是逐步加入法：任取最外围一点，以逆时针为搜索方向，假定搜索尽量 走方向变化最小的路线即先加入本区域最外围的点， 然后在内部逐步加入新的点。 最后得到本区域的所有店。 该方法首先必须确定巡视要分为几组，并且规定各组必须经过 O 点，然后 用上述方法确定各区域的范围。 以这种方法可以进行调整得到一种总路程较短的 初始化路线 1 如下：