关于灾情巡视路线的模型

.关于灾情巡视路线的模型摘要本文将求最正确巡视路线间题转化为图论中求最正确推销员回路哈米尔顿回路的问题,并用近似算法去寻求近似最优解。对赋权图中的路径分组问题定义了均衡度用以衡量分组的均衡性。对问题1和问题2先定出几个分的准则进展初步分组,并用近似算法求每一组的近似最正确推销员回路,再根据均衡度进展微调,得到较优的均衡分组和每组的近似最正确推销员回路。对问题1，运用求任意两点间最短路的Floyd算法,得出总路程较短且各组尽可能均衡的路线,各组的巡视路程分别为216.4公里,191.1公里,192.3公里,总路程599.8公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线,各组的巡视时间分别为22.74小时,22.59小时,21.69小时,22.54小时。对问题3,求出完成巡视的最短时间为6.43小时,并用较为合理的分组的准则,分成22个组对问题4，研究了在不影响分组的均衡条件下, T,t,V的允许变化围,并得出了这三个变量的关系式,并由此对分三个组的情况进展了具体讨论。关键词：最正确推销员回路问题哈米尔顿回路赋权图近似算法均衡度一、问题重述1998年夏天*县遭受水灾。为考察灾情、组织自救，县领导决定，带着有关部门负责人到全县各17个乡镇、35个村巡视。巡视路线指从县政府所在地出发，走遍各乡镇、村，又回到县政府所在地的路线。(1) 假设分三组路巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(2) 假定巡视人员在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时完成巡视，至少应分几组；给出这种分组下你认为最正确的巡视路线。(3) 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最正确的巡视路线。(4) 假设巡视组数已定(如三组，要求尽快完成巡视，讨论T，t和V改变对最正确巡视路线的影响。二、问题分析此题给出了*县的公路网络图，要求的是在不同的条件下，灾情巡视的最分组方案和路线.将每个乡镇或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度或行驶时间看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权路程或时间最小.此题是旅行售货员问题的延伸多旅行售货员问题.此题所求的分组巡视的最正确路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和到达最小的闭链闭迹.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.三、问题假设1. 汽车在路上的速度总是一定，不会出现抛锚等现象；忽略天气、故障等因素的影响。2. 巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3. 每个小组的汽车行驶速度完全一样；4. 分组后，各小组只能走自己区的路，不能走其他小组的路，除公共路外。5. 情况不受灾情影响，即车辆在所有公路上所有公路上都可以顺利通过。四、符号说明符号符号说明任意两点，间的间距各点的停留时间，即点权汽车行驶速度从任意点至点的时间，则五、模型建立与求解公路网图中，每个乡镇或村看作图中的一个节点，各乡镇、村之间的公路看作图中对应节点间的边，各条公路的长度或行驶时间看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权路程或时间最小，此即最正确推销员回路问题。在加权图G中求最正确推销员回路问题是NP完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一求加权图GV，E的最正确推销员回路的近似算法：1 用图论软件包求出G中任意两个顶点间的最短路，构造出完备图，；2 输入图的一个初始H圈；3 用对角线完全算法见23产生一个初始H圈；4 随机搜索出中假设干个H圈，例如2000个；5 对第2、3、4步所得的每个H圈，用二边逐次修正法进展优化，得到近似最正确H圈；6 在第5步求出的所有H圈中，找出权最小的一个，此即要找的最正确H圈的近似解.由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较优的计算结果。问题一：此问题是多个推销员的最正确推销员回路问题.即在加权图G中求顶点集V的划分，将G分成n个生成子图，使得1顶点 i=1，2，3n23，其中为的导出子图中的最正确推销员回路，为的权，i，j=1，2，3n4定义称为该分组的实际均衡度。为最大容许均衡度。显然，越小，说明分组的均衡性越好.取定一个后，与满足条件3的分组是一个均衡分组.条件4表示总巡视路线最短。此问题包含两方面：第一、对顶点分组；第二、在每组中求最正确推销员回路，即为单个推销员的最正确推销员问题。由于单个推销员的最正确推销员回路问题不存在多项式时间的准确算法，故多个推销员的问题也不存在多项式时间的准确算法.而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图19进展粗步划分后，求出各局部的近似最正确推销员回路的权，再进一步进展调整，使得各局部满足均衡性条件3。图11-10 O点到任意点的最短路图单位：公里从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从O点出发的树枝称为干枝，见图0，从图中可以看出，从O点出发到其它点共有6条干枝，它们的名称分别为，。根据实际工作的经历及上述分析，在分组时应遵从以下准则：准则一：尽量使同一干枝上及其分枝上的点分在同一组；准则二：应将相邻的干枝上的点分在同一组；准则三：尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组一：，分组二：，显然分组一的方法极不均衡，故考虑分组二。对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图11-10中树上的边的H圈作为其第2步输入的初始圈。分组二的近似解见表1。表1单位：公里小组名称路线总路线长度路线的总长度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-C241.9IIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5因为该分组的均衡度=54.2%所以此分法的均衡性很差。为改善均衡性，将第组中的顶点C，2，3，D，4分给第组顶点2为这两组的公共点，重新分组后的近似最优解见表2。表2单位：公里路线路线长度路线总长度IOP282726N2423221716I15I18K212025MO191.1599.8IIO2567E8E9F10F12H1413G11J19L652O216.4IIIOR29Q303231333534A1BC3D4D32O192.3因该分组的均衡度11.69%所以这种分法的均衡性较好。问题二由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有35个.计算出在乡镇及村的总停留时间为172+35=69小时，要在24小时完成巡回，假设不考虑行走时间，有: (i为分的组数).得i最小为4，故至少要分4组。由于该网络的乡镇、村分布较为均匀，故有可能找出停留时间尽量均衡的分组，当分4组时各组停留时间大约为小时，则每组分配在路途上的时间大约为24-17.25=6.75小时.而前面讨论过，分三组时有个总路程599.8公里的巡视路线，分4组时的总路程不会比599.8公里大太多，不妨以599.8公里来计算.路上时间约为小时，假设平均分配给4个组，每个组约需=4.25小时6.75小时，故分成4组是可能办到的。现在尝试将顶点分为4组.分组的原则：除遵从前面准则一、二、三外，还应遵从以下准则：准则四：尽量使各组的停留时间相等。用上述原则在图11-10上将图分为4组，同时计算各组的停留时间,然后用算法一算出各组的近似最正确推销员巡回，得出路线长度及行走时间，从而得出完成巡视的近似最正确时间.用算法一计算时，初始圈的输入与分三组时同样处理。这4组的近似最优解见表3：表3路程单位：公里；时间单位：小时组名路线路线总长度停留时间行走时间完成巡视的总时间IO2567E8E11G12H12F10F9E7652O 195.8175.5922.59IIOR29Q30Q282726N242322171617K2223N26PO199.2165.6921.69IIIOM252021K18I151413J19L6MO159.1184.5422.54IVORA3331323534B1C3D4D32O166184.7422.74上表中符号说明：加有底纹的表示前面经过并停留过，此次只经过不需停留；加框的表示此点只经过不停留。该分组实际均衡度=4.62%可以看出，表3分组的均衡度很好，且完全满足24小时完成巡视的要求。问题三我们发现从O点巡视H点的最短时间是所有最短时间中最长的，其距离为77.5公里。其时间为因此，T=2小时，t=1小时，V=35公里/小时。假设巡视人员足够多，完成巡视的最短时间为6.43小时。在最短时间限定一下，完成巡视的最优路线应满足如下条件：（1） 每个组巡视的总时间不能超过最短时间；（2） 所有点都必须访问到，不能漏点；（3） 所需巡视组数要尽量少；在寻求最优路线时，从距离O点较远的一些点如点12、10、15、22开场搜索比拟容易，因为到这些点的路线比拟少。具体方法如下：第一步：依据图1算出从O点到每一个点的最短距离;第二步：找出其中最大的一个，算出从O点沿最短的路巡视的时间，并求出;第三步：假设则这一组只能访问这一点；假设则在余下的点找到距离O点最远的点，根据条件看这一组能否巡视这一点；第四步：假设能巡视，则算出，转到第三步；第五步：假设不能则依次判断次远点、第三远点,满足总巡视时间不超过，就让这组巡视到这一点，直到然后再从第二步开场。通过以上方法，最后我们找到的最优解是22个组，如下表所示：巡视路径停留地点所需时间时间差1O-H-OH6.4302O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-013,146.150.283O-M-25-21-K-18-I-15-I-16-17-K-21-25-M-O15,166.310.124O-2-5-6-7-E-9-F-12-G-11-E-7-6-5-2-O12,115.940.495O-2-5-6-7-E-8-E-9-F-10-F-9-E-7-6-5-2-O8,106.220.216O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.580.857O-2-5-6-7-E-9-F-9-E-7-6-5-2-O9,F6.140.298O-2-5-6-L-19-J-18-K-21-25-M-OJ,186.290.149O-M-25-21-K-18-I-18-K-21-25-M-OI5.490.9410O-M-25-21-K-17-22-23-N-26-P-O17,22,236.120.3111O-2-5-G-L-19-L-6-5-2-OL,195.640.7912O-M-25-20-21-23-24-N-26-P-O20,21,246.100.3313O-M-25-21-K-21-25-M-O25,K5.500.9314O-2-5-6-7-E-7-6-5-2-O6,7,E6.380.0515O-R-31-32-35-34-A-1-O31,32,35,346.320.1116O-R-29-Q-30-Q-28-P-OQ,30,286.110.3217O-P-26-27-26-N-26-P-O26,27,N6.230.2018O-2-3-D-4-D-3-2-O3,D,45.990.4419O-1-A-33-31-R-29-R-OA,33,295.970.4620O-2-5-M-O2,5,M5.401.0321O-1-B-C-O1,B,C5.980.4522O-P-O-R-OP,R5.321.11问题四巡视组数已定, 要求尽快完成巡视, 讨论T，t和V的改变对最正确巡视路线的影响。要尽快完成巡视, 就得要求每组完成巡视时间尽量均衡, 因为总的完成巡视时间按最长的完成巡视时间计算。现在讨论在均衡度允许的围已分成n组后，改变T，t和V对最正确巡视路线的影响。显然在分组不变的情况下, 无论了T,t 、V如何改变, 对每组的最正确巡视路线是没有影响的，但可能会影响各组间的均衡性。因此该问题实际上讨论T，t和V对于分组的影响，即在不破坏原来分组均衡的条件下，T，t和V允许的最大变化围。在分n组的情况下，设：表示第i组的最正确推销员回路路线总长度；：表示第i组所要停留的乡镇的数目；：表示第i组所要停留的村的数目；i=1,2,3,n显然，当时，即每组的乡镇数、村数、最正确巡回的长度均相等，因而分组绝对均衡时，即=0时，无论T，t和V如何改变都不会改变原来分组的均衡。（一） 不影响分组的均衡时，T，t和V的最大允许变化围的讨论：对任意一个组i，其完成巡视的时间设均衡分组的最大允许时间均衡度为，即则有记则表示均衡分组所允许的最大时间误差，则 (1)由1式我们得到2由式2可得1. 当0时，要保持原均衡分组不变，T必须满足的条件为32.当时，要保持原均衡分组不变，t必须满足的条件为 (4)3.当0时，由2式得 当有当时，有6由36式，当T,t,V三个变量中任意两个变量无论如何变化，都可计算出为保持均衡性分组不变，三个变量所允许的最大变化围。二分三组的实例讨论现对分三组的情况进布寸论对问题一中所得的三个分组假设考虑停留时间和行驶时间且取小时，小时，公里/小时，结果如表5：表5 路程单位：公里；时间单位：小时行驶时间总时间I513191.15.4628.46II611192.35.4928.49III611216.46.1829.18实际均衡度为。实际时间误差为小时。现分别规定均衡分组的最大允许均衡度和，即最大容许的时间误差分别为小时和小时，计算出T,t,V三个参量中固定任意两个时，要不破坏原均衡分组，另一个参量所容许的变化围，结果如下表：表6V,t不变T,V不变T,t不变上表可以看出：1当实际均衡度刚好等于最大容许均衡度时，要保持原均衡分组，当t，V不变时，T只能减小，且下界为1.25小时；T的上界为小时； T，V不变时，t只能增大，且上界为1.38小时；t的下界为小时； t，T不变时，V只能增大，且下界为35；无上界；2当实际均衡度小于最大容许均衡度时，即时要保持原均衡分组，当t，V不变时，T变化的下界为0.51小时；T的上界为2.74小时； T，V不变时，t的上界为1.75小时；t的下界为0.63小时； t，T不变时，V增大但无上界，且下界为17.3公里/小时；三对实例结果的分析上述实例的均衡分组有一个特点，各组的停留时间相等,即取小时，小时，公里/小时，在表5的分组中定义4各组的停留时间相等的均衡分组称为停留时间相等的均衡分组，由7式得现讨论对停留时间相等的均衡分组,T,t,V的变化规律，对停留时间相等的均衡分组，分组的实际时间误差：其中，为使最大的组的标号；为使最小的组的标号。*当T,t不变时,即,时，因由6式知道，要保持平衡分组,V的下界应为取时，由9式得时，由9式得故有以下定理定理当时,对图进展停留时间相等的均衡分组后,设该分组的实际时间误差为。1假设取最大允许时间误差,当T,t不变时,要使该均衡分组保持不变,V的下界为即V只能增加不能减少；2假设取最大允许时间误差,当T,t不变时,要使该均衡分组保持不变,V的变化围的下界小于。五、优缺点分析优点1、 本文提出的分组准则简便易行,可操作性强,且可逐步调整使分组到达均衡；2、用均衡度的概念定量的刻画了分组的均衡性；3、在用近似算法求近似最正确推销员回路时,采取了三种不同的方法产生初始圈,使得算法比拟完善,得到了误差很小的近似最优解；4、从理论上定量地讨论了T,V,t的变化又中均衡分组灵敏度的影响,得到了很好的结果。缺点略六、参考文献1 静，数学建模与数学实验第三版，：高等教育，2008；2 胡运权，运筹学根底及应用第三版，：工业大学，1998；3 惠泉，图论及其应用，：科学，2004。附录用Floyd 算法求赋权图中任意两点间最短路径及路长, MATLAB程序代码如下：n=53;A=*lsread(D:file1.*ls); D=A; %赋初值for(i=1:n) for(j=1:n) R(i,j)=j; end;end %赋路径初值for(k=1:n) for(i=1:n) for(j=1:n) if(D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j); %更新dij R(i,j)=k; end; end; end;end %更新rij k %显示迭代步数 D %显示每步迭代后的路长 R %显示每步迭代后的路径 pd=0;for i=1:n %含有负权时 if(D(i,i)