全国大学生《数学建模》竞赛：1998B

最佳灾情巡视路线的数学模型 单8杨庭栋李哓涛郏长江页 (解放军后勤工学院,重庆400016) 指导教师赵静公()县某 编者按本文力求运用数学概念和方法来严格处理涉及的各种对象;力求借助于几何直 观和生活体验的启发作用,为计算机搜索制定行之有效的操作规则:在数值结果方面,粗估与细 节化相结合,从而提供较为完备的数值描述本文第四部分定理证明中有误,为版面计从删欲 全豹,试索原文 摘要本文将求最佳巡视路线间题转化为图论中求最佳推销员回路的问题,并用近似 算法去寻求近似最优解对分组问题定义了均衡度用以衡量分组的均衡性,对问题1和问题2先 定出几个分组的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均 衡度进行微调,得到较优的均衡分组和每组的近似最佳推销员回路,对问题1得出总路程较短 且各组尽可能均衡的路线,各组的巡视路程分别为216.4公里,191.1公里,192.3公里,总路程 为599.8公里对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线各 组的巡视时间分别为2274小时,22.59小时,21.69小时,22,54小时,对间题3,求出完成巡视的 最短时间为6,43小时,并用较为合理的分组的准则,分成22个组对问题4研究了在不影响分 组的均衡条件下,T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组 的情况进行了具体讨论 、问题重述(略) 二、模型的假设与符号说明(略 三、模型的建立与分析 本问题要求在某县的乡(镇)村公路网中,寻找从县政府所在地(图中O点)出发,走遍 各乡(镇)村,又回到县政府所在地,使总路程或时间最少将公路网图中,每个乡(镇)或村 看为图中的一个节点,各乡(镇)村之间的公路看作图中对应节点间的边,各条公路的长度 (或行驶时间)看作对应边上的权,所给公路网就转化为图论中的加权网络图,问题就转化 为一个图论问题,即在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次 再回到O点,使得总权(路程或时间)最小,同(,苦是,男宝是 为了讨论方便,先给出图论中相关的一些定义 定义1经过图G的每个顶点正好一次的圈,称为G的哈米尔顿圈,简称H圈 定义2在加权图G=(V,E)中 的可1,平关主的 (1)权最小的哈米顿圈称为最佳H圈; 发弃 (2)经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路. 由定义2可知,本问题是一个寻求最佳推销员回路的问题最佳推销员回路的间题可转 化为最佳H圈的问题.方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G =(,E),E中每条边(x,y)的权等于顶点x与y在图G中最短路径的权,即

最佳灾情巡视路统的数学模型 371 V(x,y)∈E',o(x,y)= min d o(x,y).甲二 在图论中有以下定理 已的时量 定理1加权图G的最佳推销员回路的权和G′的最佳H圈的权相同 定理2在加权完备图中求最佳H圈的问题是NP一完全问题 我们采用一种近似算法求出该问題的一个近似最优解,来代替最优解,算法如下: 算法一求加权图G(V,E)的最佳推销员回路的近似算法:一 1.用图论软件包求出G中任意两个顶点间的最短路,构造出完备图G(V,E) 其长断由(x,y)∈E,0(x,y)= min dal(x,y),即个 2.输入图G的一个初始H圈; 3.用对角线完全算法2产生一个初始H圈; 4.随机搜索出G′中若干个H圈,例如2000个; 5.对2、3、4步所得的每个H圈,用二边逐次修正法进行优化得到近似最佳H圈; 6.在第5步求出的所有H圈中,找出权最小的一个,此即要找的最佳H圈的近似解 此算法程序见附录(略)(由于二边逐次修正法的结果与初始圈有关,故本算法第2、3、4 步分别用三种方法产生初始圈,以保证能得到较优的计算结果) 问题一,若分为三组巡视,设计总路程最短且各组尽可能均衡的巡视路线 此问题是多个推销员的最佳推销员回路问题即在加权图G中求顶点集V的划分V 2…,Vn,将G分成n个生成子图Gv1,Gv21,,GIVJ使得 (1)顶点O∈V,i=1,2,3,…,n G). max a(C)-a(C )I (3)-mxa(C)≤a,其中C为V的导出子图Gw1]中的最佳H圈 a(G1)为C的权,i,j=1,2,3,…,n (4)∑a(C)=mn max o(C))-o(C)I 定义3称a axa(C)为该分组的实际路程均衡度a为最大容许 均衡度,显然0≤a0≤1,a越小,说明分组的均衡性越好取定一个a后,a与a满足条件 (3)的分组是一个均衡分组条件(4)表示总巡视路程最短 此问题包含两方面:第一,对顶点分组;第二,在每组中求最佳推销员回路,即为单个推销 员的最佳推销员问题我们只能去寻求一种较合理的划分准则,对图1进行初步划分后,求出 各部分的近似最佳推销员回路的权,再进一步进行调整,使得各部分满足均衡性条件(3) 从O点出发去其它点,要使路程较小应尽量走O点到该点的最短路.故用图论软件包 求出O点到其余顶点的最短路,这些最短路构成一棵O为树根的树,将从O点出发的树枝 称为干枝,见图1,从图中可以看出,人O点出发到其它点共有6条干枝,它们的名称分别为 ①,②,③,④,⑤,⑥.,,,立高 根据实际工作的经验及上述分析,在分组时应遵从以下准则: 准则一尽量使同一干枝上及其分枝上的点分在同一组;

372 全国大学生数学建模竞赛优秀论文汇编 准则二应将相邻的干枝上的点分在同一组;3 准则三尽量将长的干枝与短的干枝分在同一组 平以中 由上述分组准则,我们找到两种分组形式如下:亲最0图对1三 分组一:(⑥,①),(②,③),(⑤,④);同中名 分组二:(①,②),(③,④),(⑤,⑥); 出同出束氧路将一且国 显然分组一的方法极不均衡,故考虑分组二 对分组二中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线使用算 法一时在每个子图所构造的完备图中取一个尽量包含图1中树上的边的H圈作为其第2 步输入的初始圈 ⑤ 全 Q ① ② 图1O点到任意的最短路线图 9分组二的近似解见表1出的2中其 表1(单位:公里) 小组名称 总路线长度路线的总长度 10-P-28=27-26=N-24-23-22-17-16-1-15 1-18-K-21-20-25-M 191.1 Ⅱ0-2-5-6-L-19-J-11-G-13-14-H-12 10=F-9E-7-E-8-4-D-3-C=o 241.9 Ⅲ0-R-29-0-30-32-31-33-35-34-A-B=1 558,5 因为该分级的均衡度 a(C1)-(C2)241.9-125.5 去出边C a(C;) 241.9 2% 东其点O 所以此分法的均衡性很差. 为改善均衡性,将第Ⅱ组中的顶点C,2,3,D,4划归第Ⅲ组,重新分组后的近似最优解 见表2,各组的近似最优巡视路线见图2

最佳灾情巡视路线的数学模型 373 表2(单位:公里 编号 路线 路线长度路线总长度 I|o-P-28-27-26-N-24-23-22-17-16=1-15 K-21-20-25-M-O 191.1 Ⅱo-2-5-6-7-E-8-E-9-F-10-F-12-H-14 13-G-11-J-19-L-6-5-2-0 216.4 599.8 O-R-29-Q-30-32-31-33-35-34-A-1-B 人印, B 一图2分为3组时各组的巡视路线图 注:图中粗线部分为Ⅱ组与Ⅲ组共同经过的路线 下面对此结果进行分析因该分组的均衡度 a(C1)-o(C2)=2164-191,11 m3(C) 216.4 1.69% 所以这种分法的均衡性较好.若取最大容许的均衡度a=12%,则这是一个均衡分组 用算法一算出整个网络图的近似最佳推销员巡回为O-C-3-2-5-D-4-8- E-9-F-10-F-12-H-12-G-11-J-19-L-7-6-M-N-25-20 21-K-18-J-13-14-15-1-16-17-22-23-24-27-26-P-28-Q 30-Q-29-R-31-33-31-32-35-34-AB-O 总路长为588.6公里.而表2中三组巡回的总路线长为599.8公里可以认为这样设计 的分组方法和巡回路线能使总路线近似最短 问题二当巡视人员在各乡(镇)、村的停留时间一定,汽车的行驶速度一定,要在 小时内完成巡视,至少要分几组及最佳的巡视路线 由于T=2小时,t=1小时,V=35公里/小时,需访问的乡镇共有17个,村共有35 个,计算出在乡(镇)及村的总停留时间为17×2+35=69小时,要在24小时内完成巡回, 考虑行走时间,故至少要分4组 由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的分组,当分 4组时各组停留时间大约为=17.25小时,则每组分配在路途上的时间大约为24-17.25 =6.75小时.而前面讨论过,分三组时有个总路599.8公里的巡视路线,分4组时的总路程

374 全国大学生数学建模竞赛优秀论文汇编 不会比5998公里大太多,不妨以5998公里来计算路上时间约为 17小时,若平均 分配给4个组,每个组约需=425小时<65小时,故分成4组是可能办到的 现在尝试将顶点分为4组分组的原则:除遵从前面准则一、二、三外,还应遵从以下准 准则四尽量使各组的停留时间相等 用上述原则在图1上将图分为4组,同时计算各组的停留时间,然后用算法一算出各组 的近似最佳推销员巡回得出路线长度及行走时间,从而得出完成巡视的近似最佳时间用 算法一计算时,初始圈的输入与分三组时同样处理 注1.图中粗线表示其中两组都要经过的路段,2,方框中的点表示其中两组都经过的地 主3.方框中有两字符,罗马字符表示要停留于此地的巡视组另一字符表示此地点的代号 这4组的近似最优解见表3,各组的近似最优巡视路线见图3 表2(单位:公里 组名 路线 路线停留行走完成巡视 总长度时间时间的总时间 10-2-5-6-7-E-8-E-11-G-12-H-12 10-F-9-E-7-6 1995.8175.5922.59 ∥O-R-29-Q-30-Q-28-27-26-N-24 23-22-17-16-17-K-22-23-N-26 165.6921.69 ⅢO=M=25=20-21-K-18=1-15-14-13 J-19-L-6-M-O 1591184 Ⅳ|O-R-A-33-31-32-35-34-B+1-C D-4D-3-2-0阴 :166-184.74 22.74 Ⅳ 总是()出 H 的所 一图3分为4组时各组的巡视路线图

最佳灾情巡视路线的数学模型 375 表中符号说明:黑体表示前面经过并停留过,此次只经过不需停留;上加横线的表示此 点只经过不停留该分组实际均衡度 22.7-21.69 =4.62% 可以看出,表3分组的均衡度很好,且完全满足24小时完成巡视的要求 问题三在T,t,V的假定下,巡视人员足够多,完成巡视的最短时间为多少,并给出 此条件下的最佳路线 我们发现从O点巡视H点的最短时间是所有最短时间中最长的,其距离为77.5公里 算出时间为 77.5 35 ×2+2=6.43小时 因此,T=2小时,t=1小时,V=35公里/小时时,若巡视人员足够多,完成巡视的 最短时间为6.43小时 在最短时间的限定下,完成巡视的最优路线应满足如下条件: (1)每个组巡视的总时间不能超过最短时间t=6,43小时; (2)所有的点都必须访问到,不能漏点 (3)所需巡视组数要尽量少 在寻求最优路线时,从距离O点较远的一些点(如12,10,15,22等点)开始搜索比较容 易,因为到这些点的路线比较少 具体方法如下: 第一步依据图1算出从O点到每一个点的最短距离; 第二步找出其中最大的一个,算出从O点沿最短路巡视所需的时间t,并求△t=tH 第三步若△1<1,则这一组只能访问这一点 若△t<1,则在余下的点中找到距离O点最远的点,根据条件看这一组能否巡视这一 点 第四步若能巡视则算出△t,转到第三步; 第五步若不能,则依次判断次远点第三远点…,满足总巡视时间不超过tH,就让这 组巡视这一点,直到Mt<1,然后再从第二步开始 通过以上的方法,最后我们找到的最优解是22个组,如表4 问题四巡视组数已定,要求尽快完成巡视讨论T,t和V的改变对最佳巡视路线的 要尽快完成巡视,就得要求每组完成巡视时间尽量均衡,因为总的完成巡视时间按最长 的完成巡视时间计算现在讨论在在均衡允许的范围内已分成n组后,改变T,,V对最佳 巡视路线的影响,显然在分组不变的情况下,无论T,t,V如何改变,对每组内的最佳巡视 路线是没有影响的,但可能会影响各组间的均衡性因此该问题实际上是讨论T,t,V对分 组的影响,即在不破坏原来分组均衡的条件下,T,t,V允许的最大变化范围 在分n组的情况下,设 S;:表示第i组的最佳推销员回路路线总长度;

376 全国大学生数学建模竞赛优秀论文汇编 表4(时间单位:小时 编号 巡视路径 停留地点所需时间时间差 3,14 6.1 I-15-|-16-17 15,16 0.12 0-2-5-6-7-E-9-F-12-G-1 5 5-6-7-E-8-E-9-F-10-F-9 220.21 60 5.58 o-2-5-6-7-E-9-F-9=E-7-6=5-20|9,F 14 0-2-5-6-1-19-J-18-K-21-25M-oJ,18 0·9 90=M-=25-21-K18-1-18-K-21-25+M=O1 100-M-25-21-K-17-22-23N-26-P-O17,2,236.120.31 110=2-5-6-1-19 L,19 12o-M-25-20-21-23-24-N-26-P=O 130=M-25=21-K-21-25=M=0 20.2246.100.33 14o-2-5-6-7-E-7-6-5-2-0 . K 67,E 0.05 150-R=31-32=35-34-A-1-0 31,32.35346.320 160-R-29-Q-30=0-28=P-O Q.30,286.10.32 P-26-27-26-N-26-P-O 27N 20 1so-=2=32D.4,D下2=R= 3,D,45.990.44 200-2-5-MO A,3295.970.46 210-1-B-C-O 1,B,C 220-P-O-R=O P.r 1.1 X:表示第i组所要停留的乡镇的数目;,出 Y:表示第i组所要停留的村的数目; i=1,2,3,……,n 显然,当x=x,Y1=y,S1=S;i,j=1,2,3,…,n时,即每组的乡(镇)数、村数 最佳巡回的长度均相等,因而分组绝对均衡时,即a0=0,无论T,t,V如何改变都不会改变 原来分组的均衡 (一)不影响分组的均衡时,T,t,V的最大允许变化范围的讨论: 年对任意一个组,其完成巡视的时间 S Ti=XT+ Yt V·=1, 设均衡分组的最大允许时间均衡度为a,即 每中, Dax

最佳灾情巡视路线的数学模型 377 则有 1T-T≤a·maxT 记E=a·maxT,则c表示均衡分组所允许的最大时间误差,称为最大允许时间误 差.则 (X-X)·T+(Y-1)·t+S-S≤c的 同≤(X1-x)·7+(y,-y),+5少组 由式(1)我们得到 E 代(2) 式(2)可推出以下结果 1.当X-X>0时,要保持原均衡分组不变,T必须满足的条件为 S-S ≤T≤ (3) X-X 2.当Y=Y>0时,要保持原均衡分组不变,t必须满足的条件为 (X-X)·T 学x∈-(X;x)·T-5S (4) 3.当S1-S>0时,由(2)式得 (X-X)·T+(Y1):≤y系E(Xx)T-(Y1=Y) ①当0≤(X-X)·T+(Y1-Y)·t≤c时,有 (x-x5=5(x.-Y),; ②当(X-X)·T+(Y1-￥)·t>c时,有 ne(XX)·T(Ya-Y) ≤V(x,-x),+( (6) 由(3)-(6)式,当T,t,V三个变量中任意两个变量无论如何变化,都可计算出为保持均衡 分组不变,三个变量所允许的最大变化范围.的助,国彩 (二)分三组的实例讨论 现对分三组的情况进行讨论对问题一中所得的三个分组,若考虑停留时间和行驶 间,且取T=T0=2小时,=t0=1小时,V=V=35公里/小时时,结果如表5

378 全国大学生数学建模竞赛优秀论文汇编 表5(路程单位:公里;时间单位:小时) 编号 X S行驶时间总时间 13 546 92.3 549 28.49 4 216 实际均衡度为a0= 29,18-28.46 9.18 =2.5% 实际时间误差为0=2.5%×29.18=0.72小时 现分别规定均衡分组的最大允许均衡度a=2.5%和a=5%,即最大容许的时间误差 分别为E=0.72小时和E=1.44小时,计算出T,t,V三个参量中固定任意两个时,要不破 坏原均衡分组,另一个参量所容许的变化范围结果如下表: 表6 t,V不变 T,t不变 a=2.5%,=0.72小时1.25≤T≤2 1≤t≤1.38 V≥35 a=5%,=14小时051≤T≤2740.63≤t≤1:75 V≥17.3 表上表可以看出: (1)当实际均衡度-2.5%刚好等于最大容许均衡度a=2.5%时,要保持原均衡分 组,当 1,V不变时,T只能减小且下界为1,25小时;T的上界为T0=2小时; T,V不变时,只能增大,且上界为1.38小时;t的下界为to=1 T,t不变时,V只能增大,且无上界V的下界为Vo=35 (2)当实际均衡度a=2.5%小于最大容许均衡度a=2.5时,即e0<c时要保持原 均衡分组,当 t,V不变时,T变化的下界为0.51小时,上界为2.74小时; T,V不变时,变化的下界为0.63小时,上界为1.75小时; T,t不变时,V可以增大但无上界,也可减小,且下界为173公里/小时,0 (三)对实例结果的分析 上述实例的均衡分组有一个特点:各组的停留时间相等,即取T=Tn=2小时,=o 1小时,V=V0=35公里/小时时,在表5的分组中 (X2-X)·T+(Y-Y)·t0=0,i,j=1,2,3 (7) 定义4各组的停留时间相等的均衡分组称为停留时间相等的均衡分组,由(7)式得 T 考’,X-X≠0,i,=1,2,3 (8) 现讨论对停留时间相等的均衡分组,T,t,V的变化规律,岂 对停留时间相等的均衡分组,分组的实际时间误差:量量 =max(x-X,). To+(Y-Y)to+ S-S

最佳灾情巡视路线的数学模型 其中,为使S最大的组的标号;j为使S最小的组的标号 当T,不变时,即T=T,54时因(X=X),To+(Y1-Y1)·t0=0eo时,由(9)式得 年弘,直深 根景文本、厘0,B,算总 V0一下 故有以下定理 定理当取V=V,TT,t10时,对图进行停留时间相等的均衡分组后,设该 分组的实际时间误差为e0 (1)若取最大允许时间误差e=co,当T,t不变时,要使该均衡分组保持不变,V的下 界为V0,即V只能增加不能减少 (2)若取最大允许时间误差e>e0,当T,t不变时,要使该均衡分组保持不变,V的变 化范围的下界小于Va 四、模型的推广(略) 五、优缺点分析 原簧为一宗世量很脚 优点 :一厘人好,关的理点平 1.本文提出的分组准则简便易行,可操作性强,且可逐步调整使分组达到均衡 2.用均衡度的概念定量的刻画了分组的均衡性 3.在用近似算法求近似最佳推销员回路时,采取了三种不同的方法产生初始圈,使得 算法比较完善,得到了误差很小的近似最优解 4.从理论上定量地讨论了V,T,t的变化对均衡分组灵敏度的影响得到了得好的结果 缺点(略) 由,别 只5阶,量界总来是,BH m考立人只,海回到线国 持,量 舒贤林,余志才编著,图论基础及应用 5的量另回的, [2]龚劬编,图论与网络最优算法 3)费培之编著,图和网络及其应用.时同 小一,其神一出口 一的 语的一一厘进,去