哈密顿灾情巡视模型分析.pdf
《哈密顿灾情巡视模型分析.pdf》由会员分享,可在线阅读,更多相关《哈密顿灾情巡视模型分析.pdf(22页珍藏版)》请在三一文库上搜索。
1、灾情巡视路线模型 摘要 本题所研究的分组巡视的最佳路线与多个旅行推销员的问题相似,但也有不 同,因为此题还有均衡性要求。 这是一类图上的点的遍历性问题,即用若干条闭 链覆盖图上所有的顶点, 并使某些指标达到最优。 首先,将乡村公路示意图转化 为赋权连通图,并通过最小生成树法将原权图划分为若干个子图,然后,利用 Hamilon 圈法分别求出各个子图的最佳巡视路线。最后,利用本文中自定义的均 衡度公式: maxmin() 100%, max AA A A 为各组巡视路程或时间组成的集合, 来衡量分组的均衡性, 如果均衡度越小, 那么分组的均衡性就越好, 据此来判断 分组是否满足题意。 而题中,在基
2、于最小生成树法将原权图划分为若干个子图的 划分情况下, 就必然使得总巡视路程相对较短,而均衡度不够令人满意, 此时根 据实际需要,若要使总巡视路程优先, 达到相对较短,则采用原划分的子图分组; 若要使均衡度优先, 达到满意要求, 则我们可以对各分组部分边界点进行重划分 调整。 针对问题一,我们分别采用直观分析法和最小生成树法求解并得到不同的结 果。 若分三组巡视,最小生成树法求解各组的巡视路程分别为159.3km、 242.2km、 186.4km,总路程为 587.9km,路程均衡度为 34%。此结果下的总路程相对较短, 而均衡度偏高。 如果要优先考虑均衡度, 在最小生成树法求解发改进的基础
3、上得 到:194.0km、205.3km、206.8km,总路程为 606.1km,路程均衡度为 6.2%。 针对问题二,基于计算可以发现至少分4 组, 并求出了各组的最佳巡视路线。 各组巡视的路程和时间分别为125.5km 19.6h、 154.3km 22.4h、 203.9km 23.8h、 158.8km 21.5h,时间均衡度为 18%。 针对问题三,我们选取了巡视离县城最远的乡镇(点H)所需的时间 6.4 小 时作为最短巡视时间, 当巡视比较偏僻的乡村时, 汽车从县镇府出发直至到达终 点,中途不会停留,仅在终点站停留T(或 t)小时,然后按原路返回,到达沿 途各站接回巡视人员。 基
4、于最短巡视时间和制定的分组原则得到巡视人员至少需 分成 7 组。 针对问题四,实际上是一个变量讨论问题。在分析乡(镇)停留时间T,村 庄停留时间 t 和汽车行驶速度 v 的改变对最佳巡视路线的影响时,我们通过控制 不同变量的变化, 初步的得出了当T 与 t 变化时和 v 变化时对最佳巡视路线的影 响。 最后,我们对模型进行了评价和推广,使其更具有实用价值。 【关键词】: 均衡度最小生成树Hamilon 圈最佳巡视路线 一、问题重述 下图为某县的乡 (镇)、村公路网示意图, 公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负 责人到全县各乡(镇
5、) 、 村巡视。巡视路线指从县政府所在地出发, 走遍各乡(镇) 、 村,又回到县政府所在地的路线。 问题一:若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视 路线。 问题二:假定巡视人员在各乡(镇)停留时间T=2 小时,在各村停留时间 t=1 小时,汽车行驶速度v=35 公里/小时。要在 24 小时内完成巡视,至少应分几 组;给出这种分组下你认为最佳的巡视路线。 问题三:在上述关于T , t 和 v 的假定下,如果巡视人员足够多,完成巡视 的最短时间是多少; 给出在这种最短时间完成巡视的要求下,你认为最佳的巡视 路线。 问题四:若巡视组数已定 (如三组) ,要求尽快完成巡视,讨论T,
6、t 和 v 改 变对最佳巡视路线的影响。 二、问题分析 本题给出了某县的道路交通网络图,要求的是在不同条件下, 灾情巡视的最 佳分组方案和路线。 这是一类图上的点的遍历性问题,也就是要用若干条闭链覆 盖图上所有的顶点, 并使某些指标达到最优。 点的遍历性问题在图论中属于哈密 顿问题和旅行推销员问题类似。 如果巡视人员只分一组, 巡视路线是指巡视人员 从县政府 O 出发,走遍各乡(镇)、村最后油回到县镇府。我们可以把该题抽象 为图论的赋权连通问题,即有一赋权无向连通图( ,)G V E,且OV。两村之 间的公路长度即为无向图的边权( )w e。 寻找最佳巡视路线, 即在图( ,)G V E中 找
7、到一条包含 O 点的回路,它至少经过所有的顶点一次且使得总路程(总时间) 最短。如果将巡视人员分成若干组,每组考察部分区域且所有乡(镇)、村都考 察到,实际上就是将图( ,)G V E分为若干个连通的子图 i G,然后在每个子图中 寻找到一条含 O 点的最佳回路。 完成巡视的时间应是各组巡视中最长的时间,要想提高巡视的效率则应尽量 使各组的巡视时间接近,反映在G图分块时应尽量均衡。 三、模型假设 1、公路不考虑等级差别,也不受灾情或交通情况的影响; 2、各条公路段上汽车行驶的速度可以认为是均匀的; 3、巡视人员在各乡(镇)、村停留的时间一定,不会出现特殊情况而延误 时间; 4、各巡视组巡视的乡
8、(镇)、村不受行政区划的影响,即某乡(镇)与隶 属于它的村不一定要分在同一组内 5、忽略不计巡视人员上、下车所用的时间; 6、当巡视比较偏僻的乡村时, 汽车从县镇府出发直至到达终点,中途不会 停留,仅在终点站停留T(或 t)小时,然后按原路返回,到达沿途各站接回巡 视人员。 四、符号约定 k: 巡视人员的分组数 ; ( ,)G V E:赋权连通图; i G:赋权连通图的第i个子图(1,2,)i,k; i L:子图 i G中的最佳回路; i c:最佳回路 i L的各边权之和; i h:最佳回路 i L的巡视时间 ; ij w:第i个乡、村到第j个乡、村的距离(j1,2,53)i,; T:巡视员在
9、各乡(镇)的停留时间; t:巡视人员在各村停留的时间; v:汽车行驶的速度,单位公里小时。 五、模型建立及模型求解 5.1问题一模型的建立及求解: 5.1.1 模型一的建立与求解(直观分析法) : 根据题中所给的乡(镇) 、村示意图对地理位置进行粗略的划组分析。很显 然,由于县政府位置偏向东面, 则若分成三组巡视, 县城远离的一边分为两块的 可能性比邻近县城的一边大得多, 这样就可以得到手工给出的三组巡视路线图见 表 1: 表 1 编号路线路线长度 / 公里路线总长度 / 公里 O-1-B-34-35-32-30-Q-28- 27-26-P-29-R-31-33-A-1-O 168.4 O-M
10、-25-N-24-23-21-K-22-17-1 6 -I-15-I-18-J-19-20-L-6-5-2-O 207.2 594.3 O-2-3-D-7-E-11-G-13-14-H -12-F-10-F-9-E-8-4-D-3-C-O 218.7 为了衡量分组的合理性,于是我们定义分组的路程均衡度公式: 123123 123 max,min, max, c ccc cc c cc ; 显然01,值越小,说明分组的均衡性越好。 由此我们可以得到采 用直观分析法时的均衡度 1 23%。 5.1.2 模型二的建立与求解(基于最小生成树法) 现要分三组巡视, 则需要把图G分成三个子图(1,2,3)
11、 i G i,在每个子图 i G中寻找最佳回路(1,2,3) i L i。因为最小生成树中能包含图G中所有的顶 点E,而且最小树的边权是相邻两顶点间的距离,它描述了顶点之间的相近程 度,故可以采用最小生成树进行分组。 本模型的主要思想是:首先采用Prim 算法得到G图的最小生成树,然后基 于最小生成树生成一个可行的巡视路线,求得路线的最优总路程为。 采用 Prim 算法求解最小生成树步骤如下: (1)输入加权连通图G的带权邻接矩阵( ( , ) n n Aa i j; (2)建立初始候选边表, B T; (3)在候选边表中选出最短边( , ),( , )u v TTu v; (4)调整候选边表
12、B; (5)重复( 2) , (3) ,直到T含有1n条边。 根据 Prim 算法进行编程求解 (具体程序见附录1) ,于是我们得到G图的最 小生成树如图 1。 图 1 现对已得到的最小生成树进行分解,以获得三个子图 i G并使得分解结果尽 量均衡。由于在最小生成树上, 边权接近可以近似认为均衡即各子图包含的顶点 数应接近。因此,各个子图的顶点数应尽量接近17 个,且遵循以下分解原则。 最小生成树分解原则: ( i ) 分解点为 O 点或尽可能地接近O 点; (ii )分解所得的三个子图 i G的顶 点数尽可能地接近17 个; (iii)尽量是分解所得的子图是连通图; (iv )尽量使 子图
13、i G与点 O 的最短路上的点在该子图内,且尽量使各子图的点在子图内部形 成环路。 依据以上分解原则得到的分解结果如图2。 图 2 然后,采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路 线实际上就是在赋权图中寻找最优的哈密顿圈,包含图G的每个顶点的圈陈为 哈密顿圈。于是问题就可以转化为:现已知三个子图内乡、村与乡、村之间的距 离,从县镇府 O 出发,经过子图内的所有乡、村,最后又回到点O。 现在讨论如何将寻找最佳巡视路线问题表述成整数规划问题。但是,对于规 模较大的寻找最佳巡视路线问题,这里的表述会显得笨拙且效率低下。决策变量 定义为 : 1 0 ij x ,选择从城市 i 到城
14、市 j ,否则 ; 其线性(整数)规划模型目标函数为: 11 min nn ijij ij fw x 。 目标函数给出了哈密顿圈的总长度,并使其最小。约束式 1 1 n ij i x 保证只 能到达每个城市一次,约束式 1 1 n ij j x 保证只能离开一个城市一次,约束式 1 ijij nxn( , ij 为自定义变量 )是表述问题的关键,它确保: (1)由解得到的任何圈一定包含城市1(即县镇府点 O) ; (2)包含全部城市的 圈是可行的。于是,约束条件概括为: 1 1 1 j=1,2,n 1 i=1,2,n . 1 ij, i,j=2,3,n 01 ij, i,j=1,2,n 0 j
15、=1,2,n 53 n ij i n ij j ijij ij j x x st nxn x n , , , 或 , , 按照上述思想写出相应的Lingo 程序(程序见附录2)求解得到三组巡视路 线图见表 2: 表 2 编号路线路线长度 / 公里路线总长度 / 公里 O-P-26-27-28-30-Q-29-R- A-33-31-32-35-34-B-1-O 159.3 O-25-20-L-19-18-J-13-14-H-1 5- I-16-17-22-K-21-23-24-N-M-O 242.2 587.9 O-2-5-6-7-E-11-G-12-10- F-9-8-4-D-3-C-O 18
16、6.4 由此我们可以得到采用最小生成树法时的路程均衡度 2 34%。 从上述图表中不难看出, 第二组走的路程过长而第一组走的路程过短,两者 之间的差值较大, 也就是说这样分组的均衡性较差。因此,我们需在基于最小生 成树的原则之上对原来的分组进行适当的调整。为了缩小第一、二组间的路程差, 首先,我们将第二组的28点和 N 点分到第一组; 然后,再采用 Hamilton 圈法分 别求解三个子图内的最佳回路;最后,采用 Lingo 编程求解得到初步改进后三组 巡视路线图见表 3。 表 3 编号路线路线长度 / 公里路线总长度 / 公里 O-P -26-N -24-27-28-Q-30-29- R-A
17、-33-31-32-35-34-B-1-O 194.0 O-23-21-K-22-17-16-18-I-15- H-14-13-J-19-L- 20-25-M-O 225.1 605.5 O-2-5-6-7-E-11-G-12- 10-F-9-8-4-D-3-C-O 186.4 由此,可以计算出对模型二初步改进后的分组的均衡度为: 2 17.2%。 分析表 3 可知,第二组与第三组走的路程间的差值还是比较大,也就是说这 样分组的均衡性还有待改善。 于是,我们在基于最小生成树的原则之上对初步改 进后的分组进行适当的调整。为了缩小第二、三组间的路程差,首先,我们将第 二组的 H 点分到第三组;然后
18、采用上述中同样的方法求解得到最终改进后各组 的巡视路线图见表4。 表 4 编 号 路线 路线长度 / 公 里 路线总长度 / 公 里 O-P -26-N -24-27-28-Q-30-29- 194.0 R-A-33-31-32-35-34-B-1-O O-M-N-23-21-K-22-17-16-18-I-15- 14-13-J-19-L- 20-25-M-O 205.3 606.1 O-C-3-D-4-8-E-9-F-10- F-12-H-12-G-11-E-7-6-5-2-O 206.8 注:加有底纹的表示只经过此点但不停留。 由此,可以计算出对模型二最终改进后的分组的均衡度为: 2 6
19、.2%。 综上所述,对比模型一和改进后模型二的结果可知,若分成三组巡视, 虽然 改进后模型二的巡视总路程比模型一的长,但是,改进后模型二分组的均衡性比 模型一要好很多。 此外,模型二的结果是经过严谨科学的计算得到的,具有较高 的可信度, 相比之下, 模型一的结果是人根据地理位置粗略划分得到地,具有随 机性,可信度较低。经上述分析可知,若分成三组巡视,则应该采用改进后模型 二的巡视路线 , 见图 3。 图 3 5.2 问题二的模型建立及求解: 此问添加了巡视组在各乡 (镇)停留的时间2T小时,在各村停留的时间 1t小时以及汽车的行驶速度35v公里小时的条件后,要求在24小时内 完成巡视的最少分组
20、数以及相应的最佳巡视路线。此时需访问的乡(镇)共有 17 个,村共有 35个,于是可以计算出巡视人员在乡(镇)及村停留的总时间为 1723569小时。此外,从问题一的结果中可知,巡视的总路程至少为 500 公里,则汽车行驶所需的时间和将超过14 小时。由此可知,各组巡视所需 的总时间之和超过83 小时,要想在 24 小时内完成巡视则应满足: 83 24 i (i 为分的组数 ) 。得 i 最小为 4,故至少要分 4 组。 现在尝试将顶点分成4 组。分组的原则应建立在最小生成树的分解原则之 上,则分组应遵循以下原则:( i )分解点为 O 点或尽可能地接近O 点; (ii )分 解所得的 4 个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈密 灾情 巡视 模型 分析
链接地址:https://www.31doc.com/p-4736011.html