183.2
99.25
max Ck min Ck ， 规定 0.2 分组均衡.计算得分组二 max Ck
的均衡度为
C1 C3 228.8 99.25 0.5662 ，所以此分法的均衡性很差. C1 228.8
为改善均衡性， 将第一组中的顶点 C,2,3,D,4 分给第三组（顶点 2 为这两组 的公共点） ，重新分分组后的近似最优解如下： 小组名称 路线 总路线长度 分组 2 总长度 176.7 552.9
5.1 问题一的模型 第一问中，要在返回 O 点的条件下，找到三组路径，使得总路径最短且三组 划分均衡.因此我们考虑先以三组尽可能均衡为目标，划分出各组，把问题转化 为三个旅行商问题.之后求出各分组的最短路径.具体实施过程如下： 首先我们对数据进行了处理， 从图中人工提取出各邻接点之间的权及较近两 点之间的最短路的权，得到图 1 的残缺权矩阵（见附录）.之后利用 Floyd 算法 求出缺省值，得到图一的完备权矩阵（部分如下表）.
第 一 组 O-2-5-6-7-E-8-E-9-F-10-F-12-H（①，②） 14-13-G-11-J-19-L-6-5-2-O
6
第 二 组 O-P-28-27-26-N-24-23-22-17-16（③，④） I-15-I-18-K-21-20-25-M-O 第 三 组 0-R-29-Q-30-32-31-33-35-34-A-1（⑤，⑥） B-C-3-D-4-D-3-2-O
183.2
193
表三分组二修正最短路线表 算得该分组的均衡度为 很好.巡视路线图如下：
C3 C1 193 176.7 0.0845 ，故该方法均衡度 C3 193
图 4 问题一路线图 5.2 问题二的模型 问题二是在问题一的基础上加了时间考量.故首先由时间限制对图二进行分 组，这就将问题二转化成了问题一的单旅行商问题.具体分组过程如下： 由于 T 2h ，t 1h ，V 35km / h ，需访问的乡镇共有 17 个，村共有 35 个. 计算出在乡（镇）及村的总停留时间为 17 * 2h 35* h 69h ，要在 24h 内完成巡 回， 加上行走时间得不等式: 69h
M ij
四、 模型假设
所有模型基于以下假设：
3
1)汽车在路上的速度总是一定，不会出现抛锚等现象； 2)巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时 间； 3)每个小组的汽车行驶速度完全一样； 4)分组后， 各小组只能走自己区内的路， 不能走其他小组的路 （除公共路外） .
五、 模型建立与求解
I
II
199.2
16
5.69
21.69
III
159.1
18
4.54
22.54
IV
16 该分组实际均衡度
22.74 21.69 0.0462 . 22.74
可以看出，表 3 分组的均衡度很好，且完全满足 24h 完成巡视的要求，不需 要再进行修正.巡视路线图如下：
表 1 完备权矩阵局部表 在用 Flody 算法求缺省值时，我们能得到 O 点到其他点的最短路，在原图中 进行标注，去掉没有标注的路，得到如下图：
4
图 2 O 点到各点公路图 易见，从 O 点出发到其它点共有 6 条干枝，我们对其进行标注：
图 3 公路主干图 然后我们对图三中的公路进行分类，将其分为三组，分组依据如下： 1）尽量使同一干枝上及其分枝上的点分在同一组. 2）应将相邻的干枝上的点分在同一组. 3）尽量将长的干枝与短的干枝分在同一组. 由上述分组准则，我们找到两种分组形式如下： 分组 1:（⑥，①） ， （②，③） ， （⑤，④）
用模拟退火算法求解得分组 2 的路线如下： 小组名称 路线 总路线长度 分组 2 总长度 228.8 511.25
第 一 组 O-2-5-6-L-19-J-11-G-13-14-H-12（①，②） F-10-9-E-7-E-8-4-D-3-C-O 第 二 组 O-P-28-27-26-N-24-23-22-17-16（③，④） I-15-I-18-K-21-20-25-M-O 第 三 组 0-R-29-Q-30-32-31-33-35-34-A-B（⑤，⑥） 1-O 表 2 分组二最短路线表 引入均衡度指标：
基于多旅行商的最优灾情巡视路线设计
摘要
本文将求最佳灾情巡视路线问题转化为图论中求最佳旅行商回路的问题， 并 用近似算法去寻求近似最优解. 针对第一问， 首先从题目给出图中人工提取出部分点间残缺的最短路权矩阵， 利用 Floyd 算法将权矩阵完备化，在原图中标记各点间的最短路径，得到有六条 主干的公路图.其次依据三项分类原则将公路主干图分成三组， 得到两种分类.再 比较两种分类的均衡性，将公路分为（①，②） ， （③，④） ， （⑤，⑥）.再用模 拟退火算法求出各组中的最短路径.计算得出最短路径的均衡度为 56.62%，大于 标准 0.2.于是对分类结果进行修正，将第一组的几个点分到第三组.修正后得到 最短路径的均衡度为 8.45%，得到近似最优巡视路线. 针对第二问，首先将第一问中的权矩阵处理得到最少花费时间矩阵，由题目 要求建立不等式，求解出需将公路分为四组.故在第一问的分类方法中增加时间 考量，将公路分为四组.再用模拟退火算法求出各组最少花费时间路径，得到此 时的均衡度为 4.62%.得到近似最优巡视路线. 针对第三问，有题设条件建立不等式，得各组最短花费时间不超过 6.43h. 故采用一种最短路线调整算法求出在最短时间 6.43 小时内, 用 22 组就可以完 成巡视. 针对第四问，研究了在不影响分组的均衡条件下， T , t ,V 的允许变化范围 , 并得出了这三个变量的关系式，并由此对分三个组的情况进行了具体讨论.
关键词：旅行商问题 Floyd 模拟退火 均衡度
1
一、 问题重述
已知某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负 责人到全县各乡（镇） 、村巡视.下图为此县的乡（镇） 、村公路网示意图，公路 边的数字为该路段的公里数 . 要求巡视路线指从县政府所在地出发，走遍各乡 （镇） 、村，又回到县政府所在地的路线. 1. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线. 2. 假定巡视人员在各乡 （镇） 停留时间 T=2 小时， 在各村停留时间 t=1 小时， 汽车行驶速度 V=35 公里/小时.要在 24 小时内完成巡视，至少应分几组；给出 这种分组下你认为最佳的巡视路线. 3. 在上述关于 T , t 和 V 的假定下，如果巡视人员足够多，完成巡视的最短 时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线. 4. 若巡视组数已定（比如三组） ，要求尽快完成巡视，讨论 T，t 和 V 改变对最 佳巡视路线的影响.
C 故至少要分 4 组. 24h m .得 m 最小为 4， V
现在尝试将顶点分为 4 组.分组的原则：除遵从前面依据 1)、2)、3)外，还 应遵从以下准则： 4)尽量使各组的停留时间相等.
7
用上述原则在图 2 上将图分为 4 组，得到四组分别为： （⑥，①） ， （②） ， （③） ， （⑤，④）. 这样就将多旅行商问题转化为单旅行商问题，要求总花费时间最少，即要各 组花费时间最少，由此我们建立了如下模型，对各组分别进行求解.
通过以上的力法 , 最后我们找到的最优解是 22 个组.如下表： 编号 巡视路径 1 2 O-H-O O-2-5-6-L-19-J-13-14-13-J-19-L6-5-2-O 3 O-M-25-21-K-18-I-15-I-16-17-K21-25-M-O 4 O-2-5-6-7-E-9-F-12-G-11-E-7-65-2-O 5 O-2-5-6-7-E-8-E-9-F-10-F-9-E-76-5-2-O 6 7 8 9 10 11 12 13 14 15 O-2-5-6-7-E-11-G-11-E-7-6-5-2-O O-2-5-6-7-E-9-F-9-E-7-6-5-2-O O-2-5-6-L-19-J-18-K-21-25-M-O O-M-25-21-K-18-I-18-K-21-25-M-O O-M-25-21-K-17-22-23-N-26-P-O O-2-5-6-L-19-L-6-5-2-O O-M-25-20-21-23-24-N-26-P-O O-M-25-21-K-21-25-M-O O-2-5-6-7-E-7-6-5-2-O O-R-31-32-35-34-A-1-O G 9、F J、18 I 5.58 6.14 6.29 5.49 0.85 0.29 0.14 0.94 0.31 0.79 0.33 0.93 0.05 0.11 8、10 6.22 0.21 12、11 5.94 0.49 15、16 6.31 0.12 停留地点 H 13、14 所需时间 6.43 6.15 时间差 0 0.28
三、 符号说明
所有用到符号如下：
wij xij
公路图的权矩阵 公路图的邻接矩阵 某分组下的第 k 组路径长度 总路程 在各个乡镇的停留时间 在各个村的停留时间 汽车行驶的平均速度 第 k 组巡视乡镇个数 第 k 组巡视村个数 第 k 组花费时间 第 i 点到第 j 点花费时间
Ck
C
T
t
V
mk nk
hK
8
图 5 问题二路线图 5.3 问题三的求解 问题三没有人员限制，要求出耗时最短路线.从 O 点巡视 H 点的最短时间是 所有最短时间中最长的 , 其距离为 77.5 公里,算出时间为：
tH
77.5 2 2 6.43 35
因此，T 2h , t 1h ，V 35km / h 时，若巡视人员足够多，完成巡视的最短 时间为 6.43 小时. 在最短时问的限定下 , 完成巡视的最优路线应满足如下条件 1)每个组巡视的总时间不能超过最短时问小时 tH 6.43 ； 2)所有的点都必须访问到，不能漏点； 3)所需巡视组数要尽量少； 在寻求最优路线时， 从距离 O 点较远的一些点开始搜索比较容易, 因为到这 些点的路线比较少. 具体方法如下: 第一步 依据图 2 算出从 O 点到每一个点的最短距离； 第二步 找出其中最大的一个， 算出从 O 点沿最短路巡视所需的时间 ti ， 并求