灾情巡视路线模型.doc

灾情巡视路线模型摘要本题所研究的分组巡视的最佳路线与多个旅行推销员的问题相似,但也有不同,因为此题还有均衡性要求。这是一类图上的点的遍历性问题,即用若干条闭链覆盖图上所有的顶点,并使某些指标达到最优。首先,将乡村公路示意图转化为赋权连通图,并通过最小生成树法将原权图划分为若干个子图,然后,利用 Hamilon 圈法分别求出各个子图的最佳巡视路线。最后,利用本文中自定义的均衡度公式: ???? max min( ) 100%, max A A AA ??? ?为各组巡视路程或时间组成的集合, 来衡量分组的均衡性,如果均衡度越小,那么分组的均衡性就越好,据此来判断分组是否满足题意。而题中,在基于最小生成树法将原权图划分为若干个子图的划分情况下,就必然使得总巡视路程相对较短,而均衡度不够令人满意,此时根据实际需要,若要使总巡视路程优先,达到相对较短,则采用原划分的子图分组; 若要使均衡度优先,达到满意要求,则我们可以对各分组部分边界点进行重划分调整。针对问题一,我们分别采用直观分析法和最小生成树法求解并得到不同的结果。若分三组巡视,最小生成树法求解各组的巡视路程分别为 、 、 ,总路程为 ,路程均衡度为 34% 。此结果下的总路程相对较短, 而均衡度偏高。如果要优先考虑均衡度,在最小生成树法求解发改进的基础上得到: 、 、 ,总路程为 ,路程均衡度为 % 。针对问题二,基于计算可以发现至少分 4组,并求出了各组的最佳巡视路线。各组巡视的路程和时间分别为 km/ h、 km/ h、 km/ h、 km/ h,时间均衡度为 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出发,走遍各乡(镇)、村最后油回到县镇府。我们可以把该题抽象为图论的赋权连通问题,即有一赋权无向连通图( , ) G V E ,且 O V ?。两村之间的公路长度即为无向图的边权( ) w e 。寻找最佳巡视路线,即在图( , ) G V E 中找到一条包含 O点的回路,它至少经过所有的顶点一次且使得总路程(总时间) 最短。如果将巡视人员分成若干组,每组考察部分区域且所有乡(镇)、村都考察到,实际上就是将图( , ) G V E 分为若干个连通的子图 iG ,然后在每个子图中寻找到一条含 O点的最佳回路。完成巡视的时间应是各组巡视中最长的时间,要想提高巡视的效率则应尽量使各组的巡视时间接近,反映在 G 图分块时应尽量均衡。三、模型假设 1、公路不考虑等级差别,