1、44组罗霄伏龙秦琪灾情巡视路线的最优解决方案摘要本文依据某县的公路网络图，求解不同条件下的灾情巡视路线：一为定组巡视，二为限时巡视，并总结出该问题属于分组旅行员推销(TSP)问题。文中首先将公路网络图转化为赋权连通图，经KrUSkaI算法画出最小生成树并将原权图分为假设干子图，最后画出哈密尔顿圈，通过比拟选出最优路径。对于问题一:首先利用KrUSkaI算法画出最小生成树，再以树干为根底分为三组，分组后依据分组情况画出哈密尔顿圈并在Lingo中编程求出每组最小权值，选出最优路径。最优路径见图6,均衡度或，三组走的路程和为km对于问题二：经分析计算，巡视人员至少分为4组。然后按照分类准那么把最小生
2、成树分成4组，利用第一问的算法思想依次求出每组的最优哈密尔顿回路。根据均衡度的大小对所求得的结果进行调整，最后我们得到最优解为：时间均衡度防=18.67%,路径均衡度42=33.06%,最优巡视路线见表IOo对于问题三:我们利用Dijkstra算法求出0点距离其它各点的距离，根据0点到最远点的距离确定时间上界，该点为H最短巡视时间为6.43。然后根据时间上界和到0点的距离由远及近确定最优巡视路线，见图14。对于问题四：我们以第二问为根底分四组来考虑，运用控制变量法分三种情况进行讨论。讨论两个变量约束不变另外一个变量如何变化时，最正确巡视路线都不会改变。假定均衡度2-5-6-L-19-J-13-
3、J-18-I-16-17-K-21-20-25-M-O2O-2-5-6-7-E-9-F-10-F-12-H-14-13-G-11-E-8-4-D-3-C-B-1-O3O-P-26-N-23-22-23-24-27-28-Q-29-Q-30-32-35-34-A-33-31-R-O考虑到均衡性比拟大,分析结果可知编号1较小，编号2偏大所以可以把编号2中的一些点划分到编号1中，那么通过对最小生成树重新分三组后，得到以下最优路径：编号巡视路线长度1O-2-5-6-L-19-18J-13-14-15I-16-17-K-21-20-25-M-O2O-l-B-C-3-D-4-8-9-10-F-G-ll-E
4、7-l1-E-7O3O-P-26-N-23-22-23-24-27-28-Q-29-Q-30-32-35-34-A-33-31-R-O均衡度a=max(q)-min(q)=218.2191.6=2.3%max(cjt)218.2综合考虑以上两种情况我们发现这两种情况的总巡视路线长度比拟接近但均衡度变化很大故我们选择第二种情况为最优巡视路线。巡视路线图如图6所示编号巡视路线长度1O-2-5-6-L-19-18J-13-I4-I5I-16-17-K-21-20-25-M-O2O-l-B-C-3-D-4-8-9-10-F-G-ll-E-7-l1-E-7O3O-P-26-N-23-22-23-24-
5、27-28-Q-29-Q-30-32-35-34-A-33-31-R-O由第二问的分析得知，我们至少要分4组进行分解，使4个子图G分解结果尽量均衡。可略认为均衡度即各子图包含的顶点数接近，(35+17)4=13个。生成最小树划分为4组原那么：1：使各图中点权和尽量接近13.2：分解后的各子图尽量为连通图。O现在对已经得到的最小生成树T由于最小生成树上，边权接近，各子图包含的顶点尽量接近3：分解点为O或尽量接近0。4：生成的子图容易形成圈或接近圈。依据以上原那么对最小生成树分解为4组如图8所示图8组别顶点编号数量1A,B,C,R,Q,1,29,30,31,32,33,34,35132K,M,N,
6、P,16,17,21,22,23,24,25,26,27,28143G,H,I,J,L,5,6,11,12,13,14,15,18,19,20154D,E,F,2,3,4,7,8,9,1010图9此文在第一问的根底上分成了4组，且多了访问时间的限制。为使总巡视路线尽可能短且每组巡视路线尽可能均匀且访问时间在24小时以内，我们确立了三个目标函数1：分成的四组回路中每组回路对应的权值w(CU最小1,城镇当城镇/之间联通wy令马0,城镇i与城镇;之间不联通wQ=H所以Zw(q)=minI2：均衡度4最小：maxvv(c)-vr(c.)、我们定义=1-上为该分组的实际均衡度，显然Ol越maxH.)小说
7、明分组的均匀性越好。因此min=maxuC-B-34-35-32-30-Q-29-R-3l-33-A-1-O182O-P-28-27-26-N-24-23-22-17-16-17-K-21-25-M-O183O-M-25-21-K-18-I-15-14-H-12-G-l1-G-13-J-19-L-20-25-M184O-2-3-P-4-8-E-9-F-10-F-9-E-7-6-5-2-O15图10最正确巡视路线图为:图12在问题三中，T,t和V同二没有改变，在巡视人员足够多的情况下要求求出巡视的最短时间。分析的，在人员足够的情况下，我们给每个镇（乡）或村都分派一名巡视员。每个巡视员所走的路线该
8、点与0点之间的最短路径，巡视时间为往返时间加上访问点权时间。对他们巡视时间进行比拟，当巡视时间最长的巡视员返回时，其他巡视员都已近返回。所以巡视时间最长的即为要求的最短时间，因此我们确定的目标函数为：巡视人员从O点出发径直走向，点，在这个过程中船为两点之间权值最小值：假设巡视员访问某点权的时间K,与3x%之差大于一小时，那么可考虑访问一个村。假设大于两小时以上那么可考虑访问多个村或镇，但附加访问的村或镇所用的时间用仍小于maxK那i么综上所述得到问题三的最优化模型为首先我们通过Dijkstra算法算出O点距离其它52各点的权值最小值，通过比拟发现点H距离O点最小权值最大，H又恰好为一个镇，综上
9、二者可知从O点久吉IVnII占诉田的1问甚k2S“一一.2x77.5“二心I-LJ=LJIlAyNMJHjl.JMHOHJ1，J八CW-V/V-4一1234567891061411121314151617181920212223242526272829304939313233343536ABCD360Efghijklmn39PQR28图13：Dijkstra算法算出0点距离其它52各点的权值最小值通过MatIab编程求解（详见附录3,4）在上述条件下求得共需要29组巡视人员最优的巡视方案如下:编号巡视路径停留地点所需时间10,2,5,6,7,E,9,F,10,F,9,E,7,6,5,2,012
10、20.2,5,6,L,19,J,13,14,13,J,19,L,6,5,2,01430,c,0C40,2,5,6,7,E,9,F,9,E,7,6,5,2,0F50,2,5,6,7,E,11,G,11,E,7,6,5,2,0G60,2,5,6,7,E,9,F,12,H,12,F,9,E,7,6,5,2,0H70.M,25,21,K,18,I,18,K,21,25,M,0I80,2,5,6,L,19,J,19,L,6,5,2,0J90,2,5,6,L,19,J,19,L,6,5,2,0K100,2,3,2,02,3110,2,3,D,4,D,3,2,0D,4120,2,5,6,5,2,05,613
11、0,2,5,6,7,E,8,E,7,6,5,2,07,8140,2,5,6,7,E,9,E,7,6,5,2,0E,915O,M,25,21,K,17,K,21,25,M,0M,17160,M,25,21,K,18,K,21,25,M,025,21,18170,2,5,6,L,19,L,6,5,2,0L,19180,P,26,N,23,22,23,N,26,P,0P,22190,P,26,N,23,N,26,P,026,N,23200,53,29,53,0R,29210,53,29,Q,30,Q,29,53,0Q,30220,53,31,32,31,53,031,32230,1,A,33,A,1
12、01,A,33240,1,A,34,35,34,A34,35250,2,5,6,7,E,11J,19,20,25,M,011,20260,2,5,6,7,E,9,F,12,G,13,J,19L,6,5,2,012,13270,M,25,21,K,18,I,15,I,16,17,K,21,25,M015,16280,P,26,N,24,27,26,P,024,27290,1,B,1,0,P,28,P,0图148.1模型的建立在第二问的根底上，我们讨论四个组的情况，运用控制变量法对所要讨论的变量进行讨论。并令时间复杂度为10%,假设变量变化时而时间复杂度小于等于10%,那么认为对巡视路线没有影响
13、以此来确定变量的变化范围。所以建立的目标函数为：.vC.)v(cj.)令maxK-=aT+bit+-,minKi=aT+bit+-，所以,Vjjjy假设时间均衡度水10%时，最正确巡视路线不会改变，假设第i组巡视时间最长，第j组巡视时间最短，分三种情况进行讨论：1：T,t不变，由a10%,可以得出2：T,V不变，由a10版可以得出3：V,t不变，由a10%,可以得出88 .2模型的求解在问题四中分四组情况时求得时间均衡度为，我们假定时间5=10%,运用控制变量法，分三组进行讨论，每次控制两个变量不变，一个变量变动，最后求得求得结果如图15T和t不变时T和V不变时t和V不变时8.82V350.
14、69tl图15由上表可知:当T和t不变时，V只能变小，可以减小到/小时，此时的最正确巡视路径不变。当T和V不变时，t只能减小，可以减小到0.69小时，此时的最正确巡视路线不变。当t和V不变时,T只能增大，可以增大到2.67小时，此时的最正确巡视路线不变。9 .模型的评价、改良及推广91.1模型的优点：(1)把灾情巡视问题看作旅行员推销问题，便于快速解决问题。(2)运用Kruskal算法画出最小生成树，再根据近似算法使得问题简化。912模型的缺点：(1)模型中的计算都只是近似计算，不能够保证所求的解为最优解。(2)缺乏严格的理论根底。(3)模型求解过程中存在经过一个点屡次的情况。(4)在分组时凭
15、借经验划分可能存在不合理现象。(1)先利用计算机仿真巡视过程后再进行求解可使结果更准确。(2)所建立的模型没有考虑到意外情况，我们可以先调查统计对意外情况发生的概率及所产生的影响进行综合考虑后再优化模型。该图论模型可以广泛应用于物理学控制论、信息论、工程技术。交通运输、经济管理、电子计算机等各领域。对于科学研究、市场和社会中的许多问题，可以用该模型来解决。例如各种通信线路的架设、输油管道的铺设、铁路或者公路交通图的合理布局等问题都可应用该图论模型的方法，简便，快速地加以解决。1王朝瑞.图论M,北京：北京工业学院出版社.1987年。2李当志.数学建模竞赛教程M.南京：江苏教育出版社.1996年。
16、3姜启源.数学模型M.北京：高等教育出版社.1987年。4卢开澄.图论及其应用.北京：清华大学出版社.1981年。11.附录附录1：最小生成树源程序：b=l,1,1,1,2,2,2,3,3,3,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,9,9,10,11,11,11,12,12,12,13,13,13,13,14,14,14,15,15,16,16,17,17,17,18,18,18,19,19,19,20,20,20,20,21,21,21,21,22,22,22,23,23,23,23,24,24,24,25,25,25,25,26,26,26,27,27,27,28
17、28,28,29,29,29,30,30,31,31,31,32,32,32,32,33,33,33,33,34,34,34,35,35,35,36,36,36,36,36,36,37,37,37,37,37,38,38,38,38,39,39,39,39,40,40,40,40,41,41,41,41,42,42,42,43,43,43,44,44,45,45,45,45,45,46,46,46,46,46,47,47,47,47,48,48,48,48,49,49,49,49,49,50,50,50,50,50,51,51,51,51,52,52,52,53,53,53,53;36,37
18、38,39,3,5,36,2,39,40,8,40,2,6,40,49,5,7,48,49,6,40,41,48,4,41,41,42,42,41,43,46,42,43,44,14,43,45,46,13,15,44,14,45,17,45,16,22,47,45,46,47,20,46,48,19,21,25,48,20,23,25,47,17,23,47,21,22,24,50,23,27,50,20,21,49,50,27,50,51,24,26,28,27,51,52,51,52,53,32,52,32,33,53,30,31,33,35,31,32,35,37,35,37,38,
19、32,33,34,1,2,39,49,51,53,1,33,34,38,53,1,34,37,39,1,3,36,38,3,4,5,7,7,8,9,11,9,10,12,11,12,13,12,14,13,15,16,18,46,11,13,18,19,45,17,18,21,22,6,7,19,20,5,6,25,36,50,23,24,25,26,49,26,28,29,36,28,29,30,29,31,36,37;6,10.3,5.9,11.2,4.8,8.3,9.2,4.8,7.9,8.2,20.4,12.7,8.3,9.7,11.3,11.4,9.7,7.3,11.8,9.5,7.
20、3,15.1,7.2,14.5,20.4,8,7.8,5.6,10.8,14.2,6.8,13.2,12.2,7.8,10.2,8.6,8.6,16.4,9.8,8.6,15,9.9,15,8.8,6.8,11.8,6.8,6.7,9.8,8.2,8.2,9.2,9.3,8.1,7.2,9.3,7.9,6.5,5.5,7.9,9.1,7.8,4.1,6.7,10,10.1,9.1,10,8.9,7.9,8.9,18.8,13.2,6.5,7.8,12,8.8,7.8,10.5,10.5,18.8,7.8,7.9,7.9,12.1,8.3,15.2,7.2,7.9,10.3,7.7,8.1,7.
21、3,9.2,10.3,8.1,19,14.9,7.3,19,20.3,7.4,8.2,11.5,17.6,14.9,20.3,8.2,6,9.2,11.5,19.8,10.1,12.9,10.3,7.4,11.5,12.2,8.8,5.9,17.6,12.2,11,11.2,7.9,11.5,11,8.2,12.7,11.3,15.1,7.2,8,7.8,14.2,5.6,10.8,12.2,6.8,7.8,8.6,10.2,9.9,16.4,8.8,11.8,8.2,15.8,13.2,9.8,8.2,8.1,15.8,9.8,9.2,4.1,10.1,11.8,14.5,7.2,5.5,1
22、1.4,9.5,12,19.8,14.2,7.9,13.2,8.8,10.5,14.2,10.5,12.1,15.2,10.1,8.3,7.2,7.7,7.9,9.2,12.9,8.8;B,i=sortrows(b*,3);B=B;m=size(b,2);n=53;t=l:n;k=0;T=;c=0;fori=l:mift(B(l,i)=t(B(2,i)k=k+l;T(k,1:2)=B(1:2,i),c=c+B(3,i)tmin=min(t(B(l,i),t(B(2,i);tmax=max(t(B(l,i),t(B(2,i);forj=l:nift(j)=tmaxt(j)=tmin;endend
23、endifk=n-lbreak;endendT,c附录2：问题一及问题二的Lingo程序model:sets:city/1.19/:u;link(city,city):dist,!距离矩阵:endsetsn=size(city);data:!距离矩阵，它并不需要是对称的；dist=6O19.14040.34.540.523.327.8015.21531.421.432.836.845.442.231.215.17.220.628.24349.555.538.336.21515.8016.42217.834.237.957.246.230.17.85.625.62862.768.751.549.
24、428.22925.630.86.87.88.617.270.459.443.3212001877.583.566.364.24343.82833.224.810.218.59.985.274.258.135.822.4180；!随机产生，这里可改为你要解决的问题的数据；enddata!目标函数;min=SUm(link:dist*x);FOR(city(K):!进入城市K;sum(city(I)I#ne#K:x(I,K)=1;!离开城市K;sum(city(J)J#ne#K:x(K,J)=1;)；!保证不出现子圈：for(city(I)I#gt#1:for(city(J)J#gt#l#and
25、I#ne#J:u(I)-u(J)+n*x(I,J)=n-1);)；!限制U的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解；for(city(I)I#gt#1:u(I)36tl=2;elsetl=l;end%i0aftz66fid,p=Iujinf(36,i);tc=d*235+tl;c=l;forj=p(2:end-1)ifj=p(1)continue;endifsum(re=j,2)=0continue;endendifj36t2=2;elset2=l;end%-;yafJ2E6fiatc=tc+t2;iftc3tl=2;elsetl=l;endifj36t2=2;els
26、et2=l;endd(j)=(dfl+df2+df3)35+tl+t2;endmi,c=min(d);ifre(c)=0o=l;continue;endifmimaxtzh(m,l:2)=re(i)zre(c);re(i)=0;re(re=re(c)=0;tf(Tn)=mi;m=m+1;endendre(re=0)=;c=l;zj=re;zj(end+l:end+size(zd,2)=zd;fori=zj;dl,pl=lujinf(3,i)；d2,p2=lujinf(i,36);p(c,1:size(pl,2)=pl;p(c,size(pl,2):size(plf2)+size(p2,2)-1
27、)=p2;dd(c,l)=dl+d2;c=c+l;endfori=l:size(zh,1)dl,pl=lujinf(36,zh(i,l);d2,p2=Iujinf(zh(i,l),zh(ir2);d3,p3=lujinf(zh(i,2),36);p(c,1:size(pl,2)=pl;p(c,size(pl,2):size(pl,2)+size(p2,2)-1)=p2;p(c,size(pl,2)+size(p2,2)-1:size(pl,2)+size(p2,2)+size(p3,2)-2)=p3;dd(c,l)=dl+d2;c=c+l;end附录四：问题三的fun函数a=0InfInfIn
28、fInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInf10.35.911.2InfInfInfInfInfInfInfInfInfInfInfInfInfInfInf04.8Inf8.3InfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInf9.2InfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInf4.80InfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInf7.98.2InfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInfInf0InfInfInf20.4InfInfInfInfInfInfInfInfInfInfI
