44组 罗霄 伏龙 秦琪
灾情巡视路线的最优解决方案
摘要
本文依据某县的公路网络图，求解不同条件下的灾情巡视路线：一为定组巡视，二为限时巡视，并总结出该问题属于分组旅行员推销(TSP)问题。文中首先将公路网络图转化为赋权连通图，经Kruskal算法画出最小生成树并将原权图分为若干子图，最后画出哈密尔顿圈，通过比较选出最优路径。
对于问题一:首先利用Kruskal算法画出最小生成树，再以树干为基础分为三组，分组后依据分组情况画出哈密尔顿圈并在Lingo中编程求出每组最小权值，选出最优路径。最优路径见图6，均衡度a=12.3%，三组走的路程和为616.5km
对于问题二：经分析计算，巡视人员至少分为4组。然后按照分类准则把最小生成树分成4组，利用第一问的算法思想依次求出每组的最优哈密尔顿回路。根据均衡度的大小对所求得的结果进行调整，最后我们得到最优解为：时间均衡度a1=18.67%,路径均衡度a2=33.06%,最优巡视路线见表10。
对于问题三:我们利用Dijkstra算法求出O点距离其它各点的距离，根据O点到最远点的距离确定时间上界，该点为H最短巡视时间为6.43。然后根据时间上界和到O点的距离由远及近确定最优巡视路线，见图14。
对于问题四：我们以第二问为基础分四组来考虑，运用控制变量法分三种情况进行讨论。讨论两个变量约束不变另外一个变量如何变化时，最佳巡视路线都不会改变。假定均衡度a<10%,T,V和t变化不上上述范围时最佳巡视路线会发生改变,结果见图15
关键词：TSP问题 Kruskal算法 最小生成树 哈密尔顿圈
1
1.问题重述
1.1问题背景
今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。
图1
1.2本文需要解决的问题
(1)若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 (2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
(3)在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 (4)若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。
2
2.问题假设与符号说明
2.1问题的假设
假设一：在巡视过程中不会出现汽车故障或道路堵塞等现象。 假设二：各组路面状况一致，汽车行驶速度相等。 假设三：村镇巡视一次后，再次经过不会停留。 假设四：巡视过程中可以重复巡视某一条路。 2.2符号说明 符号 符号说明 w(Ck) 分组后第k组的TSP回路路程 a 均衡度 max(Ck) 各组路径长度中最大值 min(Ck) 各组路径长度中最小值 T 巡视人员在各乡(镇)停留时间 t 巡视人员在各村停留时间 V 汽车行驶速度 Gi 第i个加权网络图 Vi 第i个顶点集 cij 城镇i与城镇j之间的权值 ai 第i组巡视人员巡视乡镇数目 bi 第i组巡视人员巡视村数目 Soi(n) 从o点到城镇i的第n种路径的权值 ki 访问某镇或村一次所用的时间 Ki 从O点径直访问第i点往返所用的时间 Ki’ 从O点径直访问第i点附加访问其它城镇所用的时间 maxKi 从O点径直访问第i点往返所用的最大时间
3.问题分析
本文给出了某县的公路网络图，要求在不同条件下设计出最优的灾情巡视路线。将每个乡(镇)或村看作一个图的顶点，各乡镇、村之间的公路看作对应顶点的边，各条公路的长度(或行驶时间)看作对应边上的权，使得公路网络图转化为加权网络图，问题转化为图论中的分组旅行员推销问题(TSP)，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次后又回到点O，使得总
3
权(路程或时间)最小。
对于问题一：要求分三组巡视设计出总路程最短且尽可能均衡的巡视路线，我们首先利用Kruskal算法画出最小生成树。但因为图中节点数较多，有53个，我们只能去寻求一种较合理的划分准则，对图1进行粗步划分后,求出各部分类似最佳旅行员推销回路的权,再进一步调整，使得各部分满足给定的均衡性条件从O点出发到其它点并使得路程最短。故用Matlab求出O点到其它顶点的最短路程后再以树干为基础将图分为三组。由于分组有不同情况,我们先选择一种途径然后再优化处理从而确定分组情况,最后建立模型求得各组的最短路径。 对于问题二：从题中已知数据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组是合理的。
对于问题三：在上述关于T,t,V 的假定情况下，巡视人员足够多，要求出完成最短的巡视时间，并设计出最佳巡视方案。依据此条件，我们可以考虑每镇(镇)、村各分派一名巡视员，每个巡视员所经过的路线都是每段路线对应于权值的最小值。求出从O出发径直驶向所需访问的点然后再返回，比较所有巡视员巡视时间，最大值即为所要求的最小巡视时间。当巡视其它点时，巡视时间与最大巡视时间之差大于1，则可考虑顺路访问其它村或镇，但总时间仍必须小于最大巡视时间。
对于问题四：在第二问分为4组的前提下，要求尽快完成巡视讨论T，t和V
改变对最佳巡视路线的影响。我们采用控制变量法，把T,t,V分成三组，假设均衡度为
10%。对两个变量先固定不变，讨论另外一个变量的变化对结果的影响。若讨论的变量在一
定范围内变动，均衡度a?10%则认为对巡视路线没有影响，并求出此时a的变化范围，
超出此范围则认为对巡视路线有影响。
4
4.数据分析
因为图中节点较多，为53个，要使得巡视过程中总路程最短并且路线尽可能的均衡。我们把公路网转化为图论中的加权网络图，问题就转化为一个图论问题。根据53组数据我们得到它的邻接矩阵，利用Kruskal算法用Matlab（详见附录1）编程处理后得到加权网络图的最小生成树，得到以表2： 顶点 1 1 2 2 2 3 3 4 5 6 6 ↓ 38 37 3 5 36 39 40 40 6 7 49 顶点 9 9 10 11 12 13 13 13 14 15 16 ↓ 41 42 42 43 43 14 43 46 44 45 17 顶点 18 18 19 19 20 20 21 21 23 23 25 ↓ 45 46 48 46 25 47 25 50 24 50 27 顶点 27 28 29 29 30 31 31 33 34 34 36 ↓ 28 52 52 53 52 33 32 37 35 37 1 替7 41 17 22 26 50 36 51 8 41 17 47 26 28 37 53 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 A B C D E F G H I J K L M N P Q R 换 O 图2
然后根据以上数据，将两点之间连接起来，如1与B、A相连，画出的最小生成树结果如下：
图3
5