灾情巡视路线的最优解决方案

144组罗霄伏龙秦琪灾情巡视路线的最优解决方案摘要本文依据某县的公路网络图，求解不同条件下的灾情巡视路线：一为定组巡视，二为限时巡视，并总结出该问题属于分组旅行员推销(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。对于问题四：我们以第二问为基础分四组来考虑，运用控制变量法分三种情况进行讨论。讨论两个变量约束不变另外一个变量如何变化时，最佳巡视路线都不会改变。假定均衡度a10%,T,V和t变化不上上述范围时最佳巡视路线会发生改变,结果见图15关键词：TSP问题Kruskal算法最小生成树哈密尔顿圈21.问题重述1.1问题背景今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。图11.2本文需要解决的问题(1)若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。(3)在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(4)若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。32.问题假设与符号说明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，使得总4权(路程或时间)最小。对于问题一：要求分三组巡视设计出总路程最短且尽可能均衡的巡视路线，我们首先利用Kruskal算法画出最小生成树。但因为图中节点数较多，有53个，我们只能去寻求一种较合理的划分准则，对图1进行粗步划分后,求出各部分类似最佳旅行员推销回路的权,再进一步调整，使得各部分满足给定的均衡性条件从O点出发到其它点并使得路程最短。故用Matlab求出O点到其它顶点的最短路程后再以树干为基础将图分为三组。由于分组有不同情况,我们先选择一种途径然后再优化处理从而确定分组情况,最后建立模型求得各组的最短路径。对于问题二：从题中已知数据T=2小时,t=1小时,V=35公里/小时,需访问的乡镇共有17个，村镇有35个计算出在乡(镇)及村的总停留时间为17×2+35=69小时，要在24小时内完成巡回，若不考虑汽车行驶时间，由69/i24(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%。对两个变量先固定不变，讨论另外一个变量的变化对结果的影响。若讨论的变量在一定范围内变动，均衡度10%a则认为对巡视路线没有影响，并求出此时a的变化范围，超出此范围则认为对巡视路线有影响。54.数据分析因为图中节点较多，为53个，要使得巡视过程中总路程最短并且路线尽可能的均衡。我们把公路网转化为图论中的加权网络图，问题就转化为一个图论问题。根据53组数据我们得到它的邻接矩阵，利用Kruskal算法用Matlab（详见附录1）编程处理后得到加权网络图的最小生成树，得到以表2：顶点↓11222334566783837353639404067494141顶点↓99101112131313141516171741424243431443464445172247顶点↓1818191920202121232325262645464846254725502450275028顶点↓272829293031313334343636372852525352333237353715153图2然后根据以上数据，将两点之间连接起来，如1与B、A相连，画出的最小生成树结果如下：图3替换363738394041424344454647484950515253OABCDEFGHIJKLMNPQR65.问题一的解答5.1模型的准备因为最小生成树包含G中所有顶点E，而且最小树的边权是相邻顶点之间的距离，它描述相邻顶点之间的相似程度，故可考虑用最小生成树进行分块。现在对已经得到的最小生成树G进行分解，以获得三个子图Gi使得分解结果尽量均衡。由于最小生成树上，边权接近，可略认为均衡度即各子图包含的顶点数接近，各子图包含的顶点尽量接近[(35+17)/3]=17个。最小生成树分组原则：(1)分解点为O点或尽可能接近O点；(2)尽量使分解所得的三个子图Gi为连通图，且所包含的顶点树尽可能接近17；(3)尽量使子图Gi与点O最短路上的点在该子图内，并且子图内的点形成回路。根据以上原则，将最小生成树以O点为原点，树干为基础分为三组，图形如下：图4：最小生成树G组别顶点编号数量1A,N,P,Q,R,22,23,24,26,27,28,29,30,31,32,33,34,35182I,J,K,L,M,2,5,6,15,16,17,18,19,20,21,25163B,C,D,E,F,G,H,1,3,4,7,8,9,10,11,12,13,1418图5：问题1的分组情况75.2模型的建立5.2.1确定目标函数该模型是为解决最佳灾情巡视路线问题，本问中巡视人员分成三组进行巡视，为使总巡视路线尽可能短且每组巡视路线尽可能均匀，我们确立了两个目标函数1：分成的三组回路中每组回路对应的权值w(Ck)最小令1,0,ijijxij城镇与城镇之间联通城镇与城镇之间不联通，则11()NNkijijijwcwc所以31()miniwc2：均衡度a最小:我们定义max()()max()ijiwcwcawc为该分组的实际均衡度，显然01a。a越小说明分组的均匀性越好。因此max()()minmax()ijiwcwcawc所以我们建立了一下目标函数：31()minmax()()minmax()iijiwcwcwcawc5.2.2确定约束条件在加权网络图G中，将顶点集V划分为V1,V2,V3,则G的三个子图为G[V1],G[V2],G[V3],需满足一下几个条件1:顶点O包含在每个顶点集Vi中，即OVi，i=1,2,32：顶点集Vi的为V（G）的子集，即31()iVVG3：在加权图G中，G的三个子图G[V1],G[V2],G[V3],必须形成一条回路，即111,;1,pijipijjxjNxiN85.2.3综上所述得到问题一的最优化模型为31()minmax()()minmax()iijiwcwcwcawc3111OV1,2,3().1,1,iipijipijjVVGstxjNxiN，i5.3模型的解答首先我们对数据进行处理，表示为邻接矩阵的形式。利用Kruskal算法，在Matlab中求出它的最小生成树。根据我们确定的分组原则把最小生成树大致分成三组，在Lingo中依次求出每组的最优哈密尔顿回路（详见附录2）。再依据均衡度的大小进行调整，最后得到的结果为近似最优解。通过对最小生成树分三组后，得到以下最优路径：编号巡视路线长度1O-2-5-6-L-19-J-13-J-18-I-16-17-K-21-20-25-M-O169.02O-2-5-6-7-E-9-F-10-F-12-H-14-13-G-11-E-8-4-D-3-C-B-1-O227.33O-P-26-N-23-22-23-24-27-28-Q-29-Q-30-32-35-34-A-33-31-R-O206.7max()min()227.3169100%100%25.6%max()227.3kkkCCaC均衡度考虑到均衡性比较大,分析结果可知编号1较小，编号2偏大所以可以把编号2中的一些点划分到编号1中，则通过对最小生成树重新分三组后，得到以下最优路径：编号巡视路线长度1O-2-5-6-L-19-18J-13-14-15I-16-17-K-21-20-25-M-O191.62O-1-B-C-3-D-4-8-9-10-F-G-11-E-7-11-E-7O218.23O-P-26-N-23-22-23-24-27-28-Q-29-Q-30-32-35-34-A-33-31-