搜索
灾难最佳巡视路线摘要本文解决的是对全县的乡镇和村庄进行灾情巡视最佳线路的求解问题，多旅行售货问题。问题一是三个旅行售货问题，问题二是四个旅行售货问题。我们可以运用图论的知识并且考虑气均衡性，建立起约束最优化线路模型来解决这个问题。关键词：Hamilton圈多旅行售货问题最小生成树问题今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。2.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。1.问题重述问题1：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线图问题2：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题3：在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题4：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。2.模型的假设及符号说明2.1模型假设假设1：假设汽车在路上以V匀速行驶，且不停留，不考虑故障，忽略外部因素影响假设2：巡视过程中除了正常停留外，没有因其它因素造成时间延误假设3：巡视路线可以重复假设4：对于要多次经过的乡(镇)或村只停留一次假设5：每个巡视人员只能走自己划分区域内的路线2.2符号说明G：表示加权图Gi：表示子图V：表示顶点，每一个乡(镇)或村看成一个点E：表示边，乡(镇)或村之间的路线w(x，y)：表示权重，乡(镇)或村之间的距离S：表示回路路程总和ə：表示路程均衡度Li：表示每一条子回路T：表示在每个乡(镇)停留的时间I：表示在每个村停留的时间Ti：表示第i组的巡视时间V：表示汽车行驶速度Z：表示划分的区域数N：表示乡(镇)的数目N：表示村的数目Ni：表示第i组巡视乡(镇)的数目Ni：表示第i组巡视村的数目M：表示所分的组数：表示时间均衡度3.问题分析本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡(镇)村后，在回到O点，此问题可以转化为旅行商问题，再设计相应的算法求解针对问题一：问题一要求设计3组巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。针对问题三：问题三T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间，并设计最佳路线。首先，我们分析可知巡视H使用的时间是最长的。那么，设计分组时，其它组巡视的时间不能超过这一最长时间。在计算过程中我们先从距O点远的点开始考虑，因为若巡视时间与最小时间相差较远可以考虑顺便访问途径的乡、村。运用图论软件可以很好解决这一问题。针对问题四：巡视组数已定，要求尽快完成巡视，讨论T，t和V改变对最v佳巡视路线的影响。我们分别考虑当其中两个变量不变时对最佳路线的影响。分为3种情况讨论。4.数据分析处理4.1理论知识定义一个图G是指一个二元组(V(G),E(G))，其中：其中元素称为图G的顶点。2)E(G)是顶点集V(G)中的无序或有序的元素偶对(,)ijvv组成的集合，即称为边集,其中元素称为边.定义图G的阶是指图的顶点数|V(G)|,用v来表示；图的边的数目|E(G)|用来表示.用((),())GVGEG表示图，简记(,).GVE也用ijvv来表示边(,).ijvv设G=V，E，W是加权的连通图，对任意边e，其权C(e)≥0。令T=VT,ET,WT是G的一棵加权生成树，其所有枝上的权的总和称为树T的权，记为C(T)。一般说来，对于G的不同生成树T，C(T)也是不同的。可以知道，其中必有一个最小者，而这正是人们最为感兴趣的。因此，给定连通加权图G=V，E，W，T0=V，ET0，WT0是G的加权生成树，C(T0)为T0的权。若对G的任意加权生成树T均有C(T0)≤C(T)，则称T0是G的最小生成树。下面给出一种求最小生成树的方法(破圈法)：设G是有n个结点的连通图，下面算法产生的是最小生成树。算法的基本思想先将图G的边按权的递减顺序排列后,依次检验每条边,在保持连通的情况下,每次删除最大权边,直到余下n-1条边为止。4.2数据分析处理我们把53个乡(镇)村看作53个顶点，它们之间的距离为权重，建立邻接矩阵，运用图论软件，可视化如下图所示运用图论软件，自动选择最短路径，可以求得O点到53个顶点的最短距离及路径。v5问题一的解答5.1模型一的建立5.1.1确定目标函数公路网图中，每个乡(镇)或村，看作图中的一个节点，公路看作边，节点之间的距离看作对应边上的权，公路网问题就转化为加权网络图，问题一就转化为在加权网络图中，从给定点O出发，寻遍所有顶点再回到O，所得总权最小，即为多旅行商路线问题。分三组巡视，则需要把图G分为3个子图，在每个子图Gi(i=1,2,3)中寻找最佳回路Li(i=1,2,3)。巡视路线要尽可能均衡，因而每组巡视顶点数要尽量接近。目标函数：1231313min()(maxmin)minmaxiiiiiSLLLLLL(0.1)是对均衡度的度量，越小表示均衡度越好；S表示总的巡视路线，S越小表示巡回路线越短。这两个目标函数不可能同时达到最小值，求解时要两者兼顾。5.2模型的求解因为最小生成树包含G中所有定点E，相邻两点之间的权重为这两点之间的距离，它描述了顶点之间的相近程度，故考虑最小生成树初步分块。对于巡视组的划分，我们可以利用原图的最小生成树（所选择的都是权最小边）．从县城出发的最短路生成树，或者原图的单旅行商路线等等子图作为依据，对边界进行合理划分后向内扩展等直观方法作近似处理．分组巡视路线的最优解，应当采用增广完全图上的单旅行商路线分段的方法求得．但是根据原题图的规模以及边的稀疏性，用这种方法处理反而将使问题变得更为复杂，而且考虑到均衡性要求需做的调整工作也将是大量的，因此，可以采用先适当进行点的分组，分别求出各组的单旅行商路线，然后在组问进行适当调整的方法求得近似解.问题一求解流程图1.分析问题2.建立数学模型3.根据分区原则划3个分区4.寻找最小生成树，求最短回路5.均衡度测试6.调整分区7.接受模型算法实现：求出G中任意两个顶点见的最短路，构造出完备图''(,)GVE'(,,(,)min(,),GxyEwxydxy）输入图G的一个初始H圈。用对角线完全算法产生一个初始H圈。随机搜索出G中若干个H圈。对2,3,4步所得每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈。在第5步求出的所有H圈中，找出权重最小的一个，即为要找的最佳H圈的近似解。根据以下4条原则将原图划分为3组：1从O点开始分解。2分解的三个子图顶点数尽可能接近17个。3尽量实每一个子图为连通图。4尽量使每一个子图中与点O的最短路上的点在该子图内，尽量使每个子图的点在子图内形成回路。运用破圈法得到图形如下，红色线条为最小生成树方案一H划在第二组图二方案二H划在第3组图三I方案一的求解结果（具体程序见附录一）表一分组路线每组路程均衡度总路程I组O--1--B--34--35--32—30--Q--28--27--24—23--N--26--P--29--R--31—33--A--1--O200.100.147601.4II组O--M--25--20--L—19--J--18—J—13--14--H—14—15—I--16--17--22--K--21—25--M-O216.6III组O--2--5--6—7--E--11--G--12—F—10--F—9—E--8--4--D--3—C--O184.70均衡度=0.1470.1均衡度不够好，于是我们对路线进行了一些调整，把H划在第III组，这种方法更加合理。II方案二的求解结果表二分组路线每组路程均衡度总路程I组O--1--B--34--35--32--30--Q--28--27--24--23—N--26--P--29--R--31--33--A--1--O200.100.0405602．0II组O--M--25--20--L—19--J--18--J—13—14—15--I--16--17--22--K—21—25—M--O196.8III组O--2--5--6--7--E--11--G--12--H--12--F--10--F—9--E--8--4--D--3--C--O205.10均衡度0.04050.1均衡度很好，路程S增加不大，故调整后的方案更优。5.3结果分析问题一中，我们建立双目标最优化模型，但是二者不能同时达到最小值，对于两者我们都要兼顾，方案二在路程增加不大情况下，均衡度较好，因而我们选择方案二。6.问题二的解答6.1模型的建立6.1.1确定目标函数在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时（不考虑O点），在不考虑在路上时间情况下满足24TNtnZ（Z为组数）Z的最小取值为3，若分为3组，每组在路上的时间为243-172-35=13小时每组只能行走35公里，显然不可能实现。考虑Z值取4，分为4组每组，在路上时间为244172356.754小时，4组总共能行走的路程为6.75435945公里大于问题一中求解的总路程，故Z=4是可能实现的。据此，我们将原图分为4个子图。目标函数：12341414min()(maxmax)minmaxiiiiiSLLLLLLL约束条件：241,2,3,4iiiLTNtniV6.2模型的求解分组时要考虑到在乡和村中停留的时间和在路程上消耗的时间，使在近处寻访的组多访问几个村和乡，远处的组则尽量少访问些村庄和乡，从而使各组的总的消耗时间比较均衡。划分原则：○1从O点开始分解○2分解的三个子图顶点数尽可能接近13个尽○3量实每一个子图为连通图○4尽量使每一个子图中与点O的最短路上的点在该子图内，尽量使每个子图的点在子图内形成回路。据此，划分如下图所示运用问题一中同样的算法，可以得到结果如下(具体程序见附录二)表三组数每组路线每组路程每组时间巡视村镇数IO--C--B--34—35—32--30--Q—29—R—31—33—A—1--O130.50021.735个乡镇，8个村IIO--P--28--27--26-N—23—24—23—22—17—16—17--K—21—25—M--O157.90022.514个乡镇10个村IIIO--2—5--6-L—20—L--19—J--18--I—15—14--H—14—13--J—19--L--6--5--2--0196.00023.604个乡镇，9个村IVO-2--3--D--7--E--11--G--12--F—10—F--9--E--8--4--D--3--2--0181.20021.184个乡镇，8个村6.3结果分析问题二在问题一基础上加了停留时间及巡视时间限制，但算法一样。至少分为4组，才能在24小内完成巡视7.问题三的解答7.1模型的建立7.1.1确定目标函数问题3中假设巡视人员足够多，即分组数不限，甚至每个村镇都能安排一个巡视人员。那么，最短时间取决于最远那个村或镇。分析发现H是所有点中距离O最远的点，则有：77.522