1、灾情巡视最佳路径选择摘要本文解决的是对全县各乡镇和村庄进行灾情巡视线路的设计问题，该问题属于点的遍历性的TSP问题。因此我们结合图论的相关知识并考虑到分组的均衡性，建立起了约束最优化线路模型来解决该问题。针对问题一，我们先建立起目标函数(见5.11中式)，随后根据各点的集中区域进行划分，引入均衡度进行分组方案的比较，最终采用方案二(见5.2中方案二)。再利用破圈法得到了最短回路。最后matlab编程求解（见附录一）得出三组的巡视路程分别为200.1公里,196.8公里,205.1公里,总路程为602公里，均衡度=0.0405。具体路线安排见表二。针对问题二，分析得到要在24小时完成巡视的任务最
2、少要四组巡视人员，将问题一中各条线路的权重由路程改为了时间，并在结点处增加了结点权重。Matlab求解（见附录二）得巡视的时间分别为21.73小时22.51小时，23.60小时，21.18小时。所以至少分四组，具体路线安排见表三。针对问题三，通过图论软件得出巡视到距离O最远的点H要的时间为6.43小时，要在这个时间上限内完成巡视，分析得到最优分配为24组。最后借助图论软件求出最终方案(见表四)。针对问题四，在不影响分组的均衡条件下, 采用控制变量法对T,t,V分别为变量时的各自允许变化范围进行了研究。得出了这三个变量的关系式，再根据式子进行了讨论，得到最终结果见表五。关键词：Hamilton
3、圈 破圈法 TSP问题 路径最优化1问题重述1.1问题背景今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。1.2需要解决的问题若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 在上述关于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表示回路路程总和表示路程均衡
5、度Li表示每一条子回路T表示在每个乡(镇)停留的时间I表示在每个村停留的时间Ti表示第i组的巡视时间V表示汽车行驶速度Z表示划分的区域数N表示乡(镇)的数目n表示村的数目Ni表示第i组巡视乡(镇)的数目ni表示第i组巡视村的数目m表示所分的组数表示时间均衡度3问题分析本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡(镇)村后，在回到O点，此问题可以转化为旅行商问题，再设计相应的算法求解针对问题一：问题一要求设计3组巡视，巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问
6、题转化为单旅行商问题求解针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。针对问题三：问题三T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间，并设计最佳路线。首先，我们分析可知巡视H使用的时间是最长的。那么，设计分组时，其它组巡视的时间不能超过这一最长时间。在计算过程中我们先从距O点远的点开始考虑，因为若巡视时间与最小时间相差较远可以考虑顺便访问途径的乡、村。运用图论软件可以很好解决这一问题。针对问题四：巡视组数已定
7、，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。我们分别考虑当其中两个变量不变时对最佳路线的影响。分为3种情况讨论。4.数据分析及处理4.1理论知识1定义 一个图G是指一个二元组(V(G),E(G)，其中：其中元素称为图G的顶点。 2) E(G)是顶点集V(G)中的无序或有序的元素偶对组成的集合，即称为边集,其中元素称为边.定义 图G的阶是指图的顶点数|V(G)|, 用来表示；图的边的数目|E(G)|用来表示. 用表示图，简记也用来表示边 设G=是加权的连通图，对任意边e，其权C(e)0。令T=是G的一棵加权生成树，其所有枝上的权的总和称为树T的权，记为C(T)。一般说来，对于G的
8、不同生成树T，C(T)也是不同的。可以知道，其中必有一个最小者，而这正是人们最为感兴趣的。因此，给定连通加权图G=，T0=是G的加权生成树，C(T0)为T0的权。若对G的任意加权生成树T均有C(T0)C(T)，则称T0是G的最小生成树。下面给出一种求最小生成树的方法(破圈法)：设G是有n个结点的连通图，下面算法产生的是最小生成树。算法的基本思想先将图G 的边按权的递减顺序排列后, 依次检验每条边, 在保持连通的情况下, 每次删除最大权边, 直到余下n- 1 条边为止。4.2数据分析处理我们把53个乡(镇)村看作53个顶点，它们之间的距离为权重，建立邻接矩阵，运用图论软件，可视化如下图所示运用图
9、论软件，自动选择最短路径，可以求得O点到53个顶点的最短距离及路径。 图一5问题一的解答5.1模型一的建立5.1.1确定目标函数公路网图中，每个乡(镇)或村，看作图中的一个节点，公路看作边，节点之间的距离看作对应边上的权，公路网问题就转化为加权网络图，问题一就转化为在加权网络图中，从给定点O出发，寻遍所有顶点再回到O，所得总权最小，即为多旅行商路线问题。分三组巡视，则需要把图G分为3个子图，在每个子图Gi(i=1,2,3)中寻找最佳回路Li(i=1,2,3)。巡视路线要尽可能均衡，因而每组巡视顶点数要尽量接近。综上建立的模型为：目标函数：(0.1)约束条件：是对均衡度的度量，越小表示均衡度越好
10、；S表示总的巡视路线，S越小表示巡回路线越短。这两个目标函数不可能同时达到最小值，求解时要两者兼顾。5.2模型的求解因为最小生成树包含G中所有定点E，相邻两点之间的权重为这两点之间的距离，它描述了顶点之间的相近程度，故考虑最小生成树初步分块。对于巡视组的划分，我们可以利用原图的最小生成树（所选择的都是权最小边）从县城出发的最短路生成树，或者原图的单旅行商路线等等子图作为依据，对边界进行合理划分后向内扩展等直观方法作近似处理分组巡视路线的最优解，应当采用增广完全图上的单旅行商路线分段的方法求得但是根据原题图的规模以及边的稀疏性，用这种方法处理反而将使问题变得更为复杂，而且考虑到均衡性要求需做的调
11、整工作也将是大量的，因此，可以采用先适当进行点的分组，分别求出各组的单旅行商路线，然后在组问进行适当调整的方法求得近似解。问题一求解流程图(图二)均衡度测试建立数学模型根据分区原则划3个分区寻找最小生成树，求最短回路分析问题调整分区接受模型满足不满足算法实现：求出G中任意两个顶点见的最短路，构造出完备图输入图G的一个初始H圈。用对角线完全算法产生一个初始H圈。随机搜索出G中若干个H圈。对2,3,4步所得每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈。在第5步求出的所有H圈中，找出权重最小的一个，即为要找的最佳H圈的近似解。根据以下4条原则将原图划分为3组：1从O点开始分解。2分解的三个子
12、图顶点数尽可能接近17个。3尽量实每一个子图为连通图。4尽量使每一个子图中与点O的最短路上的点在该子图内，尽量使每个子图的点在子图内形成回路。运用破圈法得到图形如下，红色线条为最小生成树方案一 H划在第二组图三方案二 H划在第3组图四I方案一的求解结果（具体程序见附录一）表一分组路线每组路程均衡度总路程组O-1-B-34-35-3230-Q-28-27-2423-N-26-P-29-R-3133-A-1-O200.100.147601.4组O-M-25-20-L19-J-18J13-14-H1415I-16-17-22-K-2125-M-O216.6组O-2-5-67-E-11-G-12F10
13、-F9E-8-4-D-3C-O184.70均衡度均衡度不够好，于是我们对路线进行了一些调整，把H划在第III组，这种方法更加合理。II方案二的求解结果表二分组路线每组路程均衡度总路程组O-1-B-34-35-32-30-Q-28-27-24-23N-26-P-29-R-31-33-A-1-O200.100.04056020组O-M-25-20-L19-J-18-J131415-I-16-17-22-K2125M-O196.8组O-2-5-6-7-E-11-G-12-H-12-F-10-F9-E-8-4-D-3-C-O205.10均衡度均衡度很好，路程S增加不大，故调整后的方案更优。5.3结果分
14、析问题一中，我们建立双目标最优化模型，但是二者不能同时达到最小值，对于两者我们都要兼顾，方案二在路程增加不大情况下，均衡度较好，因而我们选择方案二。6问题二的解答6.1模型的建立6.1.1确定目标函数在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时（不考虑O点），在不考虑在路上时间情况下满足（Z为组数）Z的最小取值为3，若分为3组，每组在路上的时间为小时每组只能行走35公里，显然不可能实现。考虑Z值取4，分为4组每组，在路上时间为小时，4组总共能行走的路程为公里大于问题一中求解的总路程，故Z=4是可能实现的。据此，我们将原图分为4个子图。综上模型为：目标函数：约束条件：6.2模型的求解
15、分组时要考虑到在乡和村中停留的时间和在路程上消耗的时间，使在近处寻访的组多访问几个村和乡，远处的组则尽量少访问些村庄和乡，从而使各组的总的消耗时间比较均衡。划分原则：从O点开始分解分解的三个子图顶点数尽可能接近13个尽量实每一个子图为连通图尽量使每一个子图中与点O的最短路上的点在该子图内，尽量使每个子图的点在子图内形成回路。据此，划分如下图所示 图五运用问题一中同样的算法，可以得到结果如下(具体程序见附录二)表三组数每组路线每组路程每组时间巡视村镇数O-C-B-343532-30-Q29R3133A1-O130.50021.735个乡镇，8 个村O-P-28-27-26-N2324232217
16、1617-K2125M-O157.90022.514 个乡镇10 个村O-25-6-L20L-19J-18-I1514-H1413-J19-L-6-5-2-0196.00023.604个乡镇，9个村O-2-3-D-7-E-11-G-12-F10F-9-E-8-4-D-3-2-0181.20021.184个乡镇，8 个村6.3结果分析问题二在问题一基础上加了停留时间及巡视时间限制，但算法一样。至少分为4组，才能在24小内完成巡视7问题三的解答7.1模型的建立7.1.1确定目标函数问题3中假设巡视人员足够多，即分组数不限，甚至每个村镇都能安排一个巡视人员。那么，最短时间取决于最远那个村或镇。分析发
17、现H是所有点中距离O最远的点，则有：即在T=2，t=1,v=35的情况下，完成巡视最短时间为6.43小时设应分i组巡视，第i组巡视的乡(镇)数目，巡视村的数目，巡视路程综上建立的模型为目标函数：约束条件：每一组的巡视时间不能大于每一个顶点都要访问到，不能遗漏分组数要尽可能少均衡度不能大于我们规定上限7.2模型的求解寻找最优路径算法实现。利用图论软件求出每一点到O点最短路径，进而得到任意点返回O点的所需的最短时间，将此时间作为各点的权值；由于每一点都要访问到，所以每一点都要走到。任取一点，该点权值的两倍加上沿途访问的地点停留时间之和记为T，在tH-T的时间内，看与该点相连的各点中有没有可以访问的
18、点，若有，则继续；没有，则返回。基于以上算法，借助图论软件编程得出结果如下表表四组号访问路线访问地点所耗时间 (小时)1O-1-B-C-01 B C5.9820-1-A-34-35-OA 34 356.033O-R-31-33-A-1-OR 31 335.524O-31-32-30-Q-29-O32 30 Q6.175O-R-29-Q-28-27-26-P-O29 28 275.076O-P-26-N-24-N-26-P-OP 245.547O-P-26-N-23-N-26-P-O26 N 236.228O-P-26-N-23-22-17-K-21-25-M-O22 17 216.129O-M
19、-25-20-25-M-OM 25 206.1810O-2-5-6-7-6-5-2-O2 5 6 75.9611O-2-3-D-4-D-3-2-O3 D 4612O-2-5-6-7-E-8-E-7-6-5-2-OE 85.8413O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-OF 105.7614O-2-5-6-L-19-L-6-5-2-OL 195.6415O-M-25-21-K-18-K-21-25-M-OK 186.0216O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O9 125.8417O-2-5-6-7-E-11-G-13-G-11-E-7-
20、6-5-2-O11 136.0818O-2-5-6-7-E-11-G-13-14-13-G-11-E-7-6-5-2-O145.5619O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-OH6.4220O-2-5-6-L-19-J-19-L-6-5-2-OJ6.121O-M-25-21-K-18-I-18-K-21-25-M-OI5.522O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.5823O-M-25-21-K-18-I-15-I-18-K-21-25-M-O15524O-M-25-21-K-17-16-17-K-21-25-M-O164.4
21、48问题四的解答8.1模型的建立问题四巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。在问题三的基础上，即所分组数m为定值，要尽快完成巡视，即Ti尽可能小要求m组中最大巡视时间最小综上建立的模型为：目标函数时间均衡度2约束条件8.2模型的求解规定当时间均衡度时最佳路线不变最大巡视时间第e组Tg，最小巡视时间第f组Tf，I.当T，t为定值时，巡视路线不变V满足.当T，V定值时，巡视路线不变t满足.当t，V定值时，巡视路线不变T满足取m=4,考虑问题二中分四组情况，取则结果为：表五不变量T和t不变T和V不变t和V不变变量范围当T和t为定值时，若，则最佳巡视路线不变
22、；当T和V伟定值时，若，则最佳路线巡视路线不变；当t和V不变时，若，则最佳巡视路线不变。9模型的评价、改进及推广9.1模型的评价3优点：(1)本文所建立的模型是可以解决TSP问题，具有普遍性。(2)提出的分组方法简便易行，可操作性强，且可逐步调整使分组达到均衡。 (3)在模型的结果表达和分析时与具体图相结合，使结果简单明了。缺点：(1)由于分组的存在，求出的只是一个近似最优解，并不能保证绝对最优。(2)在划分区域的时候借助了划分经验，缺少严格的数学证明和推导。(3)在第四问中只是定性理论分析缺乏数学证明，结果的严密性不强。9.2模型的改进(1)可以结合计算机进行多次仿真模拟使结果更加准确。(2
23、)在划分区域时可以增加方案，多种方案进行比较结果说服性会更强。9.3模型的推广4我们建立的模型不仅仅可以用于灾情的巡视，还可以解决旅行线路的设定等一系列由邮递员问题引申出来的子问题。同时也可以解决图论的系列问题，如求最短路径，最优生成树等等。参考文献1E.米捏卡美，网络和图的最优化算法中国铁道出版社，北京，19842卢开澄 图论及应用，清华大学出版社，北京，19813 韩中庚 数学建模方法及其应用 高等教育出版社 20054谢兆鸿数学建模技术中国水利水电出版社2003.95张红梅 杨铁军 matlab基础及其应用教程附录一问题一的程序5%分区I的求解程序N=20; %输入地点个数Result0
24、=0.0;%用于记录最小的权值和C=eye(N);for i=1:N for j=1:NC(i,j)=inf;endendfor i=1:NC(i,i)=0;end%输入相关信息C(1,2)=10.1; C(1,3)=6.0;C(1,4)=9.9;C(1,7)=12.9;C(2,6)=10.5; C(2,11)=12.1;C(2,12)=15.2;C(3,4)=5.9;C(3,8)=10.3;C(4,8)=12.2;C(4,15)=17.6;C(5,6)=10.5;C(5,9)=7.9;C(5,16)=13.2;C(6,10)=7.8;C(7,8)=8.6;C(7,12)=1.9;C(7,13
25、)=9.2;C(8,14)=7.4;C(8,15)=11.5;C(9,16)=8.9; C(10,11)=7.9;C(10,16)=18.2;C(11,17)=8.3;C(12,17)=7.2;C(13,14)=7.3;C(13,19)=8.1;C(14,19)=19;C(14,20)=20.3;C(15,20)=8.2;C(17,18)=7.7;C(18,19)=10.3;C(19,20)=14.9;for i=1:N-1for j=i+1:NC(j,i)=C(i,j);endendfor i=1:NC(i,i)=0;endR=1 4 15 20 19 18 17 11 10 16 9 5
26、6 2 12 7 13 14 8 3;%随便输入一个环路%下面求哈密顿圈for i=1:N-1for j=i+2:Nif C(R(i),R(j)=0 & C(R(i),R(j)inf for m=i+1:jfor n=m+2:N if C(R(m),R(n)=0 & C(R(m),R(n)inf & C(R(i),(m)inf & C(R(j),(n)inf & C(R(i),(n)inf & C(R(j),(m)inf &(C(R(i),R(j)+C(R(m),R(n)C(R(i),(m)+C(R(j),(n)|(C(R(i),R(j)+C(R(m),R(n)C(R(i),R(n)+C(R(
27、j),R(m) k=R(m); R(m)=R(j); R(j)=k; %交换得到总权值更小的哈密顿圈 end end end else continue; end endendR=1 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3;for i=1:N-1 j=i+1;Result0=Result0+C(R(i),R(j);endResult0=Result0+C(R(j),R(1)+C(1,3)+C(3,4)-9.9;fprintf(路径为：);for i=1:N if i=2 fprintf(3 4 );elsefprintf(%d ,R(i);endendfprintf(n最小的路径和为:%3.2fn,Result0);路径为：1 3 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3 最小的路径和为:200.10对应路径为：O-1-B-34-35-32-30-Q-28-27-24-23-N-26-P-29-R-31-3
