灾情巡视路线模型.doc

灾情巡视路线模型摘要本题所研究的分组巡视的最佳路线与多个旅行推销员的问题相似,但也有不同,因为此题还有均衡性要求。这是一类图上的点的遍历性问题,即用若干条闭链覆盖图上所有的顶点,并使某些指标达到最优。首先,将乡村公路示意图转化为赋权连通图,并通过最小生成树法将原权图划分为若干个子图,然后,利用Hamilon圈法分别求出各个子图的最佳巡视路线。最后,利用本文中自定义的均衡度公式:,来衡量分组的均衡性,如果均衡度越小,那么分组的均衡性就越好,据此来判断分组是否满足题意。而题中,在基于最小生成树法将原权图划分为若干个子图的划分情况下,就必然使得总巡视路程相对较短,而均衡度不够令人满意,此时根据实际需要,若要使总巡视路程优先,达到相对较短,则采用原划分的子图分组;若要使均衡度优先,达到满意要求,则我们可以对各分组部分边界点进行重划分调整。针对问题一,我们分别采用直观分析法和最小生成树法求解并得到不同的结果。若分三组巡视,、、,,路程均衡度为34%。此结果下的总路程相对较短,而均衡度偏高。如果要优先考虑均衡度,在最小生成树法求解发改进的基础上得到:、、,,%。针对问题二,基于计算可以发现至少分4组,并求出了各组的最佳巡视路线。、、、,时间均衡度为18%。针对问题三,我们选取了巡视离县城最远的乡镇(点H),当巡视比较偏僻的乡村时,汽车从县镇府出发直至到达终点,中途不会停留,仅在终点站停留T(或t)小时,然后按原路返回,到达沿途各站接回巡视人员。基于最短巡视时间和制定的分组原则得到巡视人员至少需分成7组。针对问题四,实际上是一个变量讨论问题。在分析乡(镇)停留时间T,村庄停留时间t和汽车行驶速度v的改变对最佳巡视路线的影响时,我们通过控制不同变量的变化,初步的得出了当T与t变化时和v变化时对最佳巡视路线的影响。最后,我们对模型进行了评价和推广,使其更具有实用价值。【关键词】:均衡度最小生成树Hamilon圈最佳巡视路线一、问题重述下图为某县的乡(镇)、村公路网示意图,公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。问题一:若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线。问题二:假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度v=35公里/小时。要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。问题三:在上述关于T,t和v的假定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。问题四:若巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和v改变对最佳巡视路线的影响。二、问题分析本题给出了某县的道路交通网络图,要求的是在不同条件下,灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题,也就是要用若干条闭链覆盖图上所有的顶点,并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。如果巡视人员只分一组,巡视路线是指巡视人员从县政府O出发,走遍各乡(镇)、村最后油回到县镇府。我们可以把该题抽象为图论的赋权连通问题,即有一赋权无向连通图,且。两村之间的公路长度即为无向图的边权。寻找最佳巡视路线,即在图中找到一条包含O点的回路,它至少经过所有的顶点一次且使得总路程(总时间)最短。如果将巡视人员分成若干组,每组考察部分区域且所有乡(镇)、村都考察到,实际上就是将图分为若干个连通的子图,然后在每个子图中寻找到一条含O点的最佳回路。完成巡视的时间应是各组巡视中最长的时间,要想提高巡视的效率则应尽量使各组的巡视时间接近,反映在图分块时应尽量均衡。三、模型假设1、公路不考虑等级差别,也不受灾情或交通情况的影响;2、各条公路段上汽车行驶的速度可以认为是均匀的;3、巡视人员在各乡(镇)、村停留的时间一定,不会出现特殊情况而延误时间;4、各巡视组巡视的乡(镇)、村不受行政区划的影响,即某乡(镇)与隶属于它的村不一定要分在同一组内5、忽略不计巡视人员上、下车所用的时间;6、当巡视比较偏僻的乡村时,汽车从县镇府出发直至到达终点,中途不会停留,仅在终点站停留T(或t)小时,然后按原路返回,到达沿途各站接回巡视人员。四